The Library
On the complexity of triangle counting using emptiness queries
Tools
Bishnu, Arijit, Ghosh, Arijit and Mishra, Gopinath (2023) On the complexity of triangle counting using emptiness queries. In: International Conference on Randomization and Computation (RANDOM), GA, USA, 11-13 Sep 2023. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 275 48:1-48:22. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.48 ISSN 1868-8969.
|
PDF
WRAP-On-the-complexity-triangle-counting-using-emptiness-queries-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (997Kb) | Preview |
|
PDF
dcs-010723-wrap--random-final.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (868Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023....
Abstract
Beame et al. [ITCS'18 & TALG'20] introduced and used the Bipartite Independent Set (BIS) and Independent Set (IS) oracle access to an unknown, simple, unweighted and undirected graph and solved the edge estimation problem. The introduction of this oracle set forth a series of works in a short time that either solved open questions mentioned by Beame et al. or were generalizations of their work as in Dell and Lapinskas [STOC'18 and TOCT'21], Dell, Lapinskas, and Meeks [SODA'20 and SICOMP'22], Bhattacharya et al. [ISAAC'19 & TOCS'21], and Chen et al. [SODA'20]. Edge estimation using BIS can be done using polylogarithmic queries, while IS queries need sub-linear but more than polylogarithmic queries. Chen et al. improved Beame et al.’s upper bound result for edge estimation using IS and also showed an almost matching lower bound. Beame et al. in their introductory work asked a few open questions out of which one was on estimating structures of higher order than edges, like triangles and cliques, using BIS queries. In this work, we almost resolve the query complexity of estimating triangles using BIS oracle. While doing so, we prove a lower bound for an even stronger query oracle called Edge Emptiness (EE) oracle, recently introduced by Assadi, Chakrabarty, and Khanna [ESA'21] to test graph connectivity.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 4 September 2023 | ||||||
Dates: |
|
||||||
Volume: | 275 | ||||||
Page Range: | 48:1-48:22 | ||||||
DOI: | 10.4230/LIPIcs.APPROX/RANDOM.2023.48 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 4 July 2023 | ||||||
Date of first compliant Open Access: | 13 December 2023 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | International Conference on Randomization and Computation (RANDOM) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | GA, USA | ||||||
Date(s) of Event: | 11-13 Sep 2023 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year