Oh wow! I wasn’t expecting to see this on HN. I’m one of the authors of the paper, and I’m happy to answer any questions. (I’m sorry I didn’t see it earlier, it was posted in the middle of my night.)<p>First of all, to clear up a possible misunderstanding: this new formula will not help you to compute determinants more quickly. The number of terms still grows a lot faster than polynomial, and if you just want to compute the determinant, there are polynomial-time algorithms for that.<p>The best theoretical results on the complexity of computing determinants, that I know of, are in [0]. In practice you'd probably use Gaussian elimination, or maybe Bareiss for integers.<p>Someone complained that there’s no code in the paper. Since it isn’t really useful for practical computation, I didn’t think code would be useful, but in fact it did start as a Mathematica program when I first discovered it. Adam Goucher (one of my co-authors) wrote a blog post on it [1] within a few days of its discovery, which links to my original Mathematica notebook.<p>(Edit: ur-whale points out that the link to the Mathematica notebook no longer works. I have now republished it at [2].)<p>[0] <a href="https://users.cs.duke.edu/~elk27/bibliography/04/KaVi04_2697263.pdf" rel="nofollow">https://users.cs.duke.edu/~elk27/bibliography/04/KaVi04_2697...</a><p>[1] <a href="https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof-of-houstons-identity/" rel="nofollow">https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof...</a><p>[2] <a href="https://www.wolframcloud.com/obj/robin.houston/Published/determinants.nb" rel="nofollow">https://www.wolframcloud.com/obj/robin.houston/Published/det...</a>
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"?<p>FYI, The Bareiss algorithm can calculate the determinant in polynomial time, including bounding the bit complexity to polynomial space [0].<p>[0] <a href="https://en.wikipedia.org/wiki/Bareiss_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Bareiss_algorithm</a>
Minor comment: the improvement over the state-of-the-art is in the second order term of the exponent.<p>Their formula express det. with B_n = exp( n ln n - n lnln n - O(n)) terms.<p>The old formula had exp(n ln n - O(n)) terms.<p>It's a nice bound, but won't change much for non-theoretical results.