I'm sorry, I'm having a hard time parsing this paper. It looks like even calculating "partial partitions" is exponential. Have they found a nice polynomial time algorithm to find determinants or is this just an exponential algorithm but with fewer components than what is "traditional"?
FYI, The Bareiss algorithm can calculate the determinant in polynomial time, including bounding the bit complexity to polynomial space [0].