no. 7 · Tuesday 3 November 2026
Get Permanent Results Faster by Counting Stars
Abstract
We show that $n \times n$ permanents can be computed with $O^*{(2-\varepsilon)^n}$ arithmetic operations over every commutative ring, for $\varepsilon = 10^{-40}$. This solves a problem stated in Knuth's The Art of Computer Programming. Our algorithm implements the classical Binet–Minc identity with dynamic programming and careful bookkeeping. It also gives algebraic branching programs of size $O^*{(2-\varepsilon)^n}$.
- comments
- 16 pages
- fields
- Combinatorics