Computing the permanent modulo a prime power

DOI10.1016/J.IPL.2017.04.015MaRDI QIDQ2628281zbMATH OpenOpenAlexFDO

Authors Andreas Björklund, Thore Husfeldt, Isak Lyckberg

Publication date 13 June 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2017.04.015

zbMATH Keywords

integer matrixpermanentrandomized algorithms

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Matrices of integers (15B36) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 3540868
• scientific article; zbMATH DE number 1215135
• Modular arithmetic of iterated powers
• scientific article; zbMATH DE number 3297290
• Computation of the modular equation
• Some notes about power residues modulo prime
• Computations concerning primes and powers of two
• Computing Modular Polynomials
• Exponential sums modulo prime powers
• On the computation of the modular equation

Cites work

• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Below all subsets for some permutational counting problems
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Faster exponential-time algorithms in graphs of bounded average degree
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 473229 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• The complexity of computing the permanent

Cited in

(13)

• Computing sparse permanents faster
• On the hardness of computing the permanent of random matrices
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• On the linear classification of even and odd permutation matrices and the complexity of computing the permanent
• Computation of matrix permanent with automatic differentiation
• Computing the permanent of (some) complex matrices
• The parity of set systems under random restrictions with applications to exponential time problems
• Correcting noisy exponentiation black-boxes modulo a prime
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• Below all subsets for some permutational counting problems
• Enumerative and structural aspects of anagrams without fixed letters
• Counting short vector pairs by inner product and relations to the permanent

This page was built for publication: Computing the permanent modulo a prime power

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628281)