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.)
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.
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.
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.
(Edit: ur-whale points out that the link to the Mathematica notebook no longer works. I have now republished it at [2].)
> Someone complained that there’s no code in the paper.
That was me, apparently much to the dislike of a number of HNers :)
Thank you very much for the pointer to the notebook although it is not easy to access, you seem to need a Wolfram account to get to it.
[EDIT]: "Sorry, you do not have permission to access this item." after I logged into Wolfram ...
> Since it isn’t really useful for practical computation, I didn’t think code would be useful
This is a very common misconception.
There is a large category of people out there (software engineers among other) that find it much easier to read code than reading abstract math formulas full of weird greek letters and which typically pre-suppose what the reader does and doesn't know (things that are considered "trivial" by the author and not worth mentioning in the paper is often a huge obstacle for the reader to proceed with understanding what goes on).
Code is explicit to the degree that a machine can execute it, and therefore often way easier as a path to understanding an idea.
Publishing code also has the minor benefits of actually exposing things that are claimed to work but often don't - again because a machine can execute it whereas a math formula in a PDF does not have that nice property.
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].
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.
[+] [-] robinhouston|3 years ago|reply
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.
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.
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.
(Edit: ur-whale points out that the link to the Mathematica notebook no longer works. I have now republished it at [2].)
[0] https://users.cs.duke.edu/~elk27/bibliography/04/KaVi04_2697...
[1] https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof...
[2] https://www.wolframcloud.com/obj/robin.houston/Published/det...
[+] [-] ur-whale|3 years ago|reply
That was me, apparently much to the dislike of a number of HNers :)
Thank you very much for the pointer to the notebook although it is not easy to access, you seem to need a Wolfram account to get to it.
[EDIT]: "Sorry, you do not have permission to access this item." after I logged into Wolfram ...
> Since it isn’t really useful for practical computation, I didn’t think code would be useful
This is a very common misconception.
There is a large category of people out there (software engineers among other) that find it much easier to read code than reading abstract math formulas full of weird greek letters and which typically pre-suppose what the reader does and doesn't know (things that are considered "trivial" by the author and not worth mentioning in the paper is often a huge obstacle for the reader to proceed with understanding what goes on).
Code is explicit to the degree that a machine can execute it, and therefore often way easier as a path to understanding an idea.
Publishing code also has the minor benefits of actually exposing things that are claimed to work but often don't - again because a machine can execute it whereas a math formula in a PDF does not have that nice property.
[+] [-] VyseofArcadia|3 years ago|reply
I'm just jazzed to see a math paper in my wheelhouse on the front page of HN.
[+] [-] abetusk|3 years ago|reply
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
[+] [-] steppi|3 years ago|reply
[+] [-] scentoni|3 years ago|reply
[+] [-] esperent|3 years ago|reply
[+] [-] zuzatm|3 years ago|reply
Their formula express det. with B_n = exp( n ln n - n lnln n - O(n)) terms.
The old formula had exp(n ln n - O(n)) terms.
It's a nice bound, but won't change much for non-theoretical results.
[+] [-] unknown|3 years ago|reply
[deleted]
[+] [-] ur-whale|3 years ago|reply
[+] [-] vore|3 years ago|reply
[+] [-] kzrdude|3 years ago|reply
Section titles are approachable and it has figures and graphics with geometric ideas.
[+] [-] beyondCritics|3 years ago|reply
[+] [-] zython|3 years ago|reply
[+] [-] zuzatm|3 years ago|reply