Fine-grained reductions from approximate counting to decision

Holger Dell; John A Lapinskas

doi:10.1145/3442352

Fine-grained reductions from approximate counting to decision

Holger Dell, John A Lapinskas

Department of Computer Science

Research output: Contribution to journal › Article (Academic Journal) › peer-review

9 Citations (Scopus)

Original language	English
Article number	8
Pages (from-to)	1
Number of pages	24
Journal	ACM Transactions on Computation Theory
Volume	13
Issue number	2
Early online date	10 Feb 2021
DOIs	https://doi.org/10.1145/3442352
Publication status	Published - 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: [email protected]; J. Lapinskas, University of Bristol, Department of Computer Science, BS8 1UB, Bristol, UK; email: [email protected]. 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 [email protected]. © 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.

Access to Document

10.1145/3442352

https://arxiv.org/abs/1707.04609

Handle.net

Persistent link

Cite this

@article{28b06f687ff645518bf536961bfdf00a,

title = "Fine-grained reductions from approximate counting to decision",

author = "Holger Dell and Lapinskas, {John A}",

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{\textquoteright}s Seventh Framework Programme (FP7/2007–2013) ERC grant agreement no. 334828. The article reflects only the authors{\textquoteright} 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{\textquoteright} addresses: H. Dell, Goethe University Frankfurt, Institut f{\"u}r Informatik, Robert-Mayer-Str. 11-15, 60325 Frankfurt am Main, Germany; email: [email protected]; J. Lapinskas, University of Bristol, Department of Computer Science, BS8 1UB, Bristol, UK; email: [email protected]. 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 [email protected]. {\textcopyright} 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: {\textcopyright} 2021 ACM.",

year = "2021",

month = jun,

doi = "10.1145/3442352",

language = "English",

volume = "13",

pages = "1",

journal = "ACM Transactions on Computation Theory",

number = "2",

}

TY - JOUR

T1 - Fine-grained reductions from approximate counting to decision

AU - Dell, Holger

AU - Lapinskas, John A

N1 - 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: [email protected]; J. Lapinskas, University of Bristol, Department of Computer Science, BS8 1UB, Bristol, UK; email: [email protected]. 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 [email protected]. © 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.

PY - 2021/6

Y1 - 2021/6

U2 - 10.1145/3442352

DO - 10.1145/3442352

M3 - Article (Academic Journal)

VL - 13

SP - 1

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

IS - 2

M1 - 8

ER -