Advanced

Computing the permanent modulo a prime power

Björklund, Andreas LU ; Husfeldt, Thore LU and Lyckberg, Isak (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/plog⁡p)} 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:
author
organization
publishing date
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
2018-01-07 12:05:27
@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/plog⁡p)} if p is an odd prime with kp&lt;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 δ&gt;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},
  keyword      = {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},
  volume       = {125},
  year         = {2017},
}