Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; and
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
  • wos:000403743400005
  • scopus:85019173018
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
2024-04-14 11:36:24
@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}},
  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}},
}