Fine-grained reductions from approximate counting to decision

Holger Dell, John A Lapinskas

Research output: Contribution to journalArticle (Academic Journal)peer-review

Original languageEnglish
Article number8
Pages (from-to)1
Number of pages24
JournalACM Transactions on Computation Theory
Volume13
Issue number2
Early online date10 Feb 2021
DOIs
Publication statusPublished - Jun 2021

Bibliographical note

Funding Information:
Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. The research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP7/2007–2013) ERC grant agreement no. 334828. The article reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. Authors’ addresses: H. Dell, Goethe University Frankfurt, Institut für Informatik, Robert-Mayer-Str. 11-15, 60325 Frankfurt am Main, Germany; email: dell@cs.uni-frankfurt.de; J. Lapinskas, University of Brisol, Department of Computer Science, BS8 1UB, Bristol, UK; email: john.lapinskas@bristol.ac.uk. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1942-3454/2021/02-ART8 $15.00 https://doi.org/10.1145/3442352

Funding Information:
Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Seventh Framework Programme (FP7/2007-2013) ERC grant agreement no. 334828. The article reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein

Publisher Copyright:
© 2021 ACM.

Cite this