ITU

Approximately counting and sampling small witnesses using a colourful decision oracle

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Standard

Approximately counting and sampling small witnesses using a colourful decision oracle. / Dell, Holger; Lapinskas, John; Meeks, Kitty.

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. ed. / Shuchi Chawla. Society for Industrial and Applied Mathematics, 2020. p. 2201-2211.

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Harvard

Dell, H, Lapinskas, J & Meeks, K 2020, Approximately counting and sampling small witnesses using a colourful decision oracle. in S Chawla (ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 2201-2211. https://doi.org/10.1137/1.9781611975994.135

APA

Dell, H., Lapinskas, J., & Meeks, K. (2020). Approximately counting and sampling small witnesses using a colourful decision oracle. In S. Chawla (Ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (pp. 2201-2211). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975994.135

Vancouver

Dell H, Lapinskas J, Meeks K. Approximately counting and sampling small witnesses using a colourful decision oracle. In Chawla S, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. 2020. p. 2201-2211 https://doi.org/10.1137/1.9781611975994.135

Author

Dell, Holger ; Lapinskas, John ; Meeks, Kitty. / Approximately counting and sampling small witnesses using a colourful decision oracle. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. editor / Shuchi Chawla. Society for Industrial and Applied Mathematics, 2020. pp. 2201-2211

Bibtex

@inproceedings{b5b5c17fc4e24969aa5dd99cf720266c,
title = "Approximately counting and sampling small witnesses using a colourful decision oracle",
abstract = "In this paper, we prove “black box” results for turning algorithms which decide whether or not a witness exists into algorithms to approximately count the number of witnesses, or to sample from the set of witnesses approximately uniformly, with essentially the same running time. We do so by extending the framework of Dell and Lapinskas (STOC 2018), which covers decision problems that can be expressed as edge detection in bipartite graphs given limited oracle access; our framework covers problems which can be expressed as edge detection in arbitrary k-hypergraphs given limited oracle access. (Simulating this oracle generally corresponds to invoking a decision algorithm.) This includes many key problems in both the fine-grained setting (such as k-SUM, k-OV and weighted k-Clique) and the parameterised setting (such as induced subgraphs of size k or weight-k solutions to CSPs). From an algorithmic standpoint, our results will make the development of new approximate counting algorithms substantially easier; indeed, it already yields a new state-of-the-art algorithm for approximately counting graph motifs, improving on Jerrum and Meeks (JCSS 2015) unless the input graph is very dense and the desired motif very small. Our k-hypergraph reduction framework generalises and strengthens results in the graph oracle literature due to Beame et al. (ITCS 2018) and Bhattacharya et al. (CoRR abs/1808.00691).Read More: https://epubs.siam.org/doi/10.1137/1.9781611975994.135",
author = "Holger Dell and John Lapinskas and Kitty Meeks",
year = "2020",
doi = "10.1137/1.9781611975994.135",
language = "English",
pages = "2201--2211",
editor = "Shuchi Chawla",
booktitle = "Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Society for Industrial and Applied Mathematics",
address = "United States",

}

RIS

TY - GEN

T1 - Approximately counting and sampling small witnesses using a colourful decision oracle

AU - Dell, Holger

AU - Lapinskas, John

AU - Meeks, Kitty

PY - 2020

Y1 - 2020

N2 - In this paper, we prove “black box” results for turning algorithms which decide whether or not a witness exists into algorithms to approximately count the number of witnesses, or to sample from the set of witnesses approximately uniformly, with essentially the same running time. We do so by extending the framework of Dell and Lapinskas (STOC 2018), which covers decision problems that can be expressed as edge detection in bipartite graphs given limited oracle access; our framework covers problems which can be expressed as edge detection in arbitrary k-hypergraphs given limited oracle access. (Simulating this oracle generally corresponds to invoking a decision algorithm.) This includes many key problems in both the fine-grained setting (such as k-SUM, k-OV and weighted k-Clique) and the parameterised setting (such as induced subgraphs of size k or weight-k solutions to CSPs). From an algorithmic standpoint, our results will make the development of new approximate counting algorithms substantially easier; indeed, it already yields a new state-of-the-art algorithm for approximately counting graph motifs, improving on Jerrum and Meeks (JCSS 2015) unless the input graph is very dense and the desired motif very small. Our k-hypergraph reduction framework generalises and strengthens results in the graph oracle literature due to Beame et al. (ITCS 2018) and Bhattacharya et al. (CoRR abs/1808.00691).Read More: https://epubs.siam.org/doi/10.1137/1.9781611975994.135

AB - In this paper, we prove “black box” results for turning algorithms which decide whether or not a witness exists into algorithms to approximately count the number of witnesses, or to sample from the set of witnesses approximately uniformly, with essentially the same running time. We do so by extending the framework of Dell and Lapinskas (STOC 2018), which covers decision problems that can be expressed as edge detection in bipartite graphs given limited oracle access; our framework covers problems which can be expressed as edge detection in arbitrary k-hypergraphs given limited oracle access. (Simulating this oracle generally corresponds to invoking a decision algorithm.) This includes many key problems in both the fine-grained setting (such as k-SUM, k-OV and weighted k-Clique) and the parameterised setting (such as induced subgraphs of size k or weight-k solutions to CSPs). From an algorithmic standpoint, our results will make the development of new approximate counting algorithms substantially easier; indeed, it already yields a new state-of-the-art algorithm for approximately counting graph motifs, improving on Jerrum and Meeks (JCSS 2015) unless the input graph is very dense and the desired motif very small. Our k-hypergraph reduction framework generalises and strengthens results in the graph oracle literature due to Beame et al. (ITCS 2018) and Bhattacharya et al. (CoRR abs/1808.00691).Read More: https://epubs.siam.org/doi/10.1137/1.9781611975994.135

U2 - 10.1137/1.9781611975994.135

DO - 10.1137/1.9781611975994.135

M3 - Article in proceedings

SP - 2201

EP - 2211

BT - Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms

A2 - Chawla, Shuchi

PB - Society for Industrial and Applied Mathematics

ER -

ID: 85513867