Fine-Grained Reductions from Approximate Counting to Decision

DOI10.1145/3442352zbMath1495.68098OpenAlexW3131687093MaRDI QIDQ5065630

John Lapinskas, Holger Dell

Publication date: 22 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:46e63536-2f78-4aeb-bf3f-19144809e770

zbMATH Keywords

satisfiabilityapproximate countingfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)

Related Items (1)

Almost optimal query algorithm for hitting set using a subset query

This page was built for publication: Fine-Grained Reductions from Approximate Counting to Decision