Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
From MaRDI portal
Publication:5091174
DOI10.4230/LIPIcs.ICALP.2019.25OpenAlexW2965527050MaRDI QIDQ5091174
Andreas Björklund, R. 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/
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Computing sparse permanents faster
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Faster exponential-time algorithms in graphs of bounded average degree
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Computing the permanent modulo a prime power
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- The Complexity of Enumeration and Reliability Problems
- Rapid Multiplication of Rectangular Matrices
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Faster Online Matrix-Vector Multiplication
- Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
- More Applications of the Polynomial Method to Algorithm Design
- Determinant Sums for Undirected Hamiltonicity
- A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)\) expected speedup for \(0-1\) matrices]
