4 ms·

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

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]. [0] https://en.wikipedia.org/wiki/Bareiss_algorithm https://en.wikipedia.org/wiki/Bareiss_algorithm

steppi 4y ago
From my read of the paper. This new formula also gives an exponential time algorithm. It’s not of interest as a practical method for computing determinants. It does however have interesting geometric and combinatorial properties and they used it to give new bounds for the tensor rank and Waring rank of a determinant respectively. You can think of these ranks loosely as measures of the “complexity” of a determinant (but not in the sense of computational complexity). These ranks are of interest in pure mathematics but I can’t really say more about them because it’s been too many years since I’ve studied related math.