Computing the permanent modulo a prime power

DOI10.1016/j.ipl.2017.04.015zbMath1409.68325OpenAlexW2611808961MaRDI QIDQ2628281

Thore Husfeldt, Isak Lyckberg, Andreas Björklund

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

permanentinteger matrixrandomized algorithms

Mathematics Subject Classification ID

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

Related Items

The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems ⋮ Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants ⋮ Unnamed Item ⋮ Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• Faster exponential-time algorithms in graphs of bounded average degree
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)\) expected speedup for \(0-1\) matrices]