Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors

DOI10.4230/LIPICS.ICALP.2019.25MaRDI QIDQ5091174zbMATH OpenOpenAlexFDO

Authors Andreas Björklund, Ryan Williams

Publication date 21 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10601/pdf/LIPIcs-ICALP-2019-25.pdf/

zbMATH Keywords

Hamiltonian cycleorthogonal vectorspermanent

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Below all subsets for some permutational counting problems
• Faster exponential-time algorithms in graphs of bounded average degree
• Computing the permanent of (some) complex matrices
• Computing sparse permanents faster
• Computing the permanent modulo a prime power

Cites work

• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
• Computing sparse permanents faster
• Computing the permanent modulo a prime power
• Determinant sums for undirected Hamiltonicity
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Faster exponential-time algorithms in graphs of bounded average degree
• Faster Online Matrix-Vector Multiplication
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3047763 (Why is no real title available?)
• More applications of the polynomial method to algorithm design
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Rapid Multiplication of Rectangular Matrices
• The complexity of computing the permanent
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• The Complexity of Enumeration and Reliability Problems

Cited in

(3)

• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• An asymptotically fast polynomial space algorithm for Hamiltonicity detection in sparse directed graphs
• Counting short vector pairs by inner product and relations to the permanent

This page was built for publication: Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors

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