Abstract
We sPRThow how to compute the permanent of an n×n integer matrix modulo pk in time nk+O(1) if p=2 and in time 2n/exp{Ω(γ2n/plogp)} if p is an odd prime with kp<n, where γ=1−kp/n. Our algorithms are based on Ryser's formula, a randomized algorithm of Bax and Franklin, and exponential-space tabulation. Using the Chinese remainder theorem, we conclude that for each δ>0 we can compute the permanent of an n×n integer matrix in time 2n/exp{Ω(δ2n/β1/(1−δ)logβ)}, provided there exists a real number β such that |perA|≤βn and β≤(144δn)1−δ.
Original language | English |
---|---|
Pages (from-to) | 20-25 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 125 |
DOIs | |
Publication status | Published - 2017 Sept 1 |
Subject classification (UKÄ)
- Computational Mathematics
Free keywords
- Algorithms
- Graph algorithms
- Randomized algorithms