PreprintCC BY-SA 4.0arXiv
Get Permanent Results Faster by Counting Stars
Abstract
We show that n × n permanents can be computed with O*(2−ε)n arithmetic operations over every commutative ring, for ε = 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−ε)n.
Related
- Counting Lattice Points in Translations: Uniqueness and Existence Results
- A deterministic (1+ε)n approximation for the permanent of a nonnegative matrix
- An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix
- Faster high-accuracy multicommodity flow in dense graphs
- Constrained Capacity for Faster-than-Nyquist Signaling in Frequency-Selective Fading Channels
BibTeX
@misc{curticapean2026permanent,
title = {{Get Permanent Results Faster by Counting Stars}},
author = {Radu Curticapean},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03636},
eprint = {2611.03636},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03636},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Get Permanent Results Faster by Counting Stars
AU - Radu Curticapean
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03636
UR - https://arxiv.org/abs/2611.03636
AB - We show that n × n permanents can be computed with O^*(2−ε)^n arithmetic operations over every commutative ring, for ε = 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−ε)^n.
ER -