Fine-grained reductions from approximate counting to decision

DOI10.1145/3188745.3188920zbMATH Open1427.68117arXiv1707.04609OpenAlexW3100460727MaRDI QIDQ5230296FDOQ5230296

Authors: Holger Dell, John Lapinskas 

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: In this paper, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witnesses with minimal overhead.) This mirrors a foundational result of Sipser (STOC 1983) and Stockmeyer (SICOMP 1985) in the polynomial-time setting, and a similar result of M"uller (IWPEC 2006) in the FPT setting. Using our framework, we obtain such reductions for some of the most important problems in fine-grained complexity: the Orthogonal Vectors problem, 3SUM, and the Negative-Weight Triangle problem (which is closely related to All-Pairs Shortest Path). We also provide a fine-grained reduction from approximate #SAT to SAT. Suppose the Strong Exponential Time Hypothesis (SETH) is false, so that for some $1<c<2$ and all $k$ there is an $O(c^n)$-time algorithm for k-SAT. Then we prove that for all $k$, there is an $O((c+o(1){)}^n)$-time algorithm for approximate #$k$-SAT. In particular, our result implies that the Exponential Time Hypothesis (ETH) is equivalent to the seemingly-weaker statement that there is no algorithm to approximate #3-SAT to within a factor of $1+epsilon$ in time $2^{o(n)}/epsilo{n}^2$ (taking $epsilon>0$ as part of the input).

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

Recommendations

• Fine-Grained Reductions from Approximate Counting to Decision
• Counting solutions to polynomial systems via reductions
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• On some fine-grained questions in algorithms and complexity
• The relative exponential time complexity of approximate counting satisfying assignments

zbMATH Keywords

approximate countingsatisfiabilityisolation lemmaorthogonal vectorsfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Cited In (8)

• On triangle estimation using tripartite independent set queries
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Fast exact algorithms using Hadamard product of polynomials
• Fine-Grained Complexity Theory (Tutorial)
• Fine-Grained Reductions from Approximate Counting to Decision
• Counting solutions to polynomial systems via reductions
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
• On some fine-grained questions in algorithms and complexity

This page was built for publication: Fine-grained reductions from approximate counting to decision

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