Computing the permanent modulo a prime power

Andreas Björklund, Thore Husfeldt, Isak Lyckberg

Research output: Contribution to journalArticlepeer-review

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−δ.

Original languageEnglish
Pages (from-to)20-25
Number of pages6
JournalInformation Processing Letters
Volume125
DOIs
Publication statusPublished - 2017 Sept 1

Subject classification (UKÄ)

  • Computational Mathematics

Free keywords

  • Algorithms
  • Graph algorithms
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'Computing the permanent modulo a prime power'. Together they form a unique fingerprint.

Cite this