Get Permanent Results Faster by Counting Stars
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 and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.03636
curl -X POST /api/v1/records/arxiv/2611.03636/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.03636/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'