Faster ways to calculate permanents in mathematics and computing
Get Permanent Results Faster by Counting Stars
Data Structures and AlgorithmsComputational Complexity
Summary
Calculating the permanent of a big grid of numbers is very hard and usually takes a lot of time. The authors found a method to do this calculation a tiny bit faster than before for any kind of number system where you can add and multiply. They use an old math formula combined with smart steps to keep track of the work. This solves a longstanding problem about how quickly we can get these results.
What this means in practice
- •For algorithm engineers: Create more efficient algorithms when computing matrix permanents in various mathematical software and toolkits.
- •For cryptography developers: Evaluate and optimize cryptographic protocols that rely on properties related to permanents in algebraic structures.
A theory result. No direct application yet.
Authors
Radu Curticapean
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}$.