Fine-grained reductions from approximate counting to decision

DOI10.1145/3188745.3188920zbMath1427.68117arXiv1707.04609OpenAlexW3100460727MaRDI QIDQ5230296

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)

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

zbMATH Keywords

satisfiabilityorthogonal vectorsapproximate countingisolation lemmafine-grained complexity

Mathematics Subject Classification ID

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

Related Items (6)

On triangle estimation using tripartite independent set queries ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Fine-Grained Complexity Theory (Tutorial)

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