The relative exponential time complexity of approximate counting satisfying assignments

DOI10.1007/s00453-016-0134-yzbMath1344.68101OpenAlexW1514496467MaRDI QIDQ309794

Patrick Traxler

Publication date: 7 September 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0134-y

zbMATH Keywords

hashingapproximate countingexponential-time complexityrandomness extraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• NP is as easy as detecting unique solutions
• On the power of two-point based sampling
• Inequalities in Fourier analysis
• Which problems have strongly exponential complexity?
• On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• On Approximation Algorithms for # P
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item