The Library
Faster counting and sampling algorithms using colorful decision oracle
Tools
Tools
Tools
Bhattachrya, Anup, Bishnu, Arijit, Ghosh, Arijit and Mishra, Gopinath (2022) Faster counting and sampling algorithms using colorful decision oracle. In: The 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) , Marseille, France ; Online, 15-18 Mar 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 219 ISBN 9783959772228. doi:10.4230/LIPIcs.STACS.2022.10 ISSN 1868-8969.
|
PDF
WRAP-faster-counting-sampling-algorithms-using-colorful-decision-oracle-Mishra-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (810Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.STACS.2022.10
Abstract
In this work, we consider $d$-{\sc Hyperedge Estimation} and $d$-{\sc Hyperedge Sample} problem in a hypergraph $\mathcal{H}(U(\mathcal{H}),\mathcal{F}(\mathcal{H}))$ in the query complexity framework, where $U(\mathcal{H})$ denotes the set of vertices and $\mathcal{F}(\mathcal{H})$ denotes the set of hyperedges. The oracle access to the hypergraph is called {\sc Colorful Independence Oracle} ({\sc CID}), which takes $d$ (non-empty) pairwise disjoint subsets of vertices $A_1,\ldots,A_d \subseteq U(\mathcal{H})$ as input, and answers whether there exists a hyperedge in $\mathcal{H}$ having (exactly) one vertex in each $A_i, i \in \{1,2,\ldots,d\}$. The problem of $d$-{\sc Hyperedge Estimation} and $d$-{\sc Hyperedge Sample} with {\sc CID} oracle access is important in its own right as a combinatorial problem. Also, Dell {\it{et al.}}~[SODA '20] established that {\em decision} vs {\em counting} complexities of a number of combinatorial optimization problems can be abstracted out as $d$-{\sc Hyperedge Estimation} problems with a {\sc CID} oracle access.
The main technical contribution of the paper is an algorithm that estimates $m= \lvert {\mathcal{F}(\mathcal{H})}\rvert$ with $\widehat{m}$ such that { $$
\frac{1}{C_{d}\log^{d-1} n} \;\leq\; \frac{\widehat{m}}{m} \;\leq\; C_{d} \log ^{d-1} n . $$ by using at most $C_{d}\log ^{d+2} n$ many {\sc CID} queries, where $n$ denotes the number of vertices in the hypergraph $\mathcal{H}$ and $C_{d}$ is a constant that depends only on $d$}. Our result coupled with the framework of Dell {\it{et al.}}~[SODA '21] implies improved bounds for a number of fundamental problems.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Computer algorithms, Data structures (Computer science) , Data structures (Computer science) -- Mathematical models | ||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
| ISBN: | 9783959772228 | ||||||
| ISSN: | 1868-8969 | ||||||
| Official Date: | 9 March 2022 | ||||||
| Dates: |
|
||||||
| Volume: | 219 | ||||||
| Article Number: | 10 | ||||||
| DOI: | 10.4230/LIPIcs.STACS.2022.10 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||
| Date of first compliant deposit: | 21 March 2022 | ||||||
| Date of first compliant Open Access: | 21 March 2022 | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | The 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Marseille, France ; Online | ||||||
| Date(s) of Event: | 15-18 Mar 2022 | ||||||
| Related URLs: | |||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
