Computing the permanent modulo a prime power
(2017) In Information Processing Letters 125. p.20-25- 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−δ.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/9b4f0ecf-aebf-4943-8269-ddc7491dfef0
- author
- Björklund, Andreas LU ; Husfeldt, Thore LU and Lyckberg, Isak
- organization
- publishing date
- 2017-09-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Algorithms, Graph algorithms, Randomized algorithms
- in
- Information Processing Letters
- volume
- 125
- pages
- 6 pages
- publisher
- Elsevier
- external identifiers
-
- scopus:85019173018
- wos:000403743400005
- ISSN
- 0020-0190
- DOI
- 10.1016/j.ipl.2017.04.015
- language
- English
- LU publication?
- yes
- id
- 9b4f0ecf-aebf-4943-8269-ddc7491dfef0
- date added to LUP
- 2017-05-29 11:01:12
- date last changed
- 2025-01-07 14:20:38
@article{9b4f0ecf-aebf-4943-8269-ddc7491dfef0, abstract = {{<p>We sPRThow how to compute the permanent of an n×n integer matrix modulo p<sup>k</sup> in time n<sup>k+O(1)</sup> if p=2 and in time 2<sup>n</sup>/exp{Ω(γ<sup>2</sup>n/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 2<sup>n</sup>/exp{Ω(δ<sup>2</sup>n/β<sup>1/(1−δ)</sup>logβ)}, provided there exists a real number β such that |perA|≤β<sup>n</sup> and β≤(144δn)<sup>1−δ</sup>.</p>}}, author = {{Björklund, Andreas and Husfeldt, Thore and Lyckberg, Isak}}, issn = {{0020-0190}}, keywords = {{Algorithms; Graph algorithms; Randomized algorithms}}, language = {{eng}}, month = {{09}}, pages = {{20--25}}, publisher = {{Elsevier}}, series = {{Information Processing Letters}}, title = {{Computing the permanent modulo a prime power}}, url = {{http://dx.doi.org/10.1016/j.ipl.2017.04.015}}, doi = {{10.1016/j.ipl.2017.04.015}}, volume = {{125}}, year = {{2017}}, }