Computing the permanent modulo a prime power

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

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

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • IT University of Copenhagen
  • Lund University
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Beräkningsmatematik

Nyckelord

Originalspråkengelska
Sidor (från-till)20-25
Antal sidor6
TidskriftInformation Processing Letters
Volym125
StatusPublished - 2017 sep 1
PublikationskategoriForskning
Peer review utfördJa