The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments

DOI10.1007/978-3-319-13524-3_28zbMath1341.68067arXiv1208.2561OpenAlexW2378875912MaRDI QIDQ2946032

Patrick Traxler

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.2561

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

This page was built for publication: The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments