Paperlane

no. 7 · Tuesday 3 November 2026

Get Permanent Results Faster by Counting Stars

Radu Curticapean

math.CO · via cs.DS · 16 pp

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
pdf ↗ page arXiv:2611.03636 ↗