Edge estimation with independent set oracles

Paul Beame, Sariel Har-Peled, Sivaramakrishnan NatarajanRamamoorthy, Cyrus Rashtchian, Makrand Sinha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the problem of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an n-vertex graph: one that uses only polylog(n) bipartite independent set queries, and another one that uses n2/3 · polylog(n) independent set queries.

Original languageEnglish (US)
Title of host publication9th Innovations in Theoretical Computer Science, ITCS 2018
EditorsAnna R. Karlin
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770606
DOIs
StatePublished - Jan 1 2018
Event9th Innovations in Theoretical Computer Science, ITCS 2018 - Cambridge, United States
Duration: Jan 11 2018Jan 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume94
ISSN (Print)1868-8969

Other

Other9th Innovations in Theoretical Computer Science, ITCS 2018
CountryUnited States
CityCambridge
Period1/11/181/14/18

Keywords

  • Approximate Counting
  • Importance Sampling
  • Independent Set Queries
  • Sparsification

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Edge estimation with independent set oracles'. Together they form a unique fingerprint.

  • Cite this

    Beame, P., Har-Peled, S., NatarajanRamamoorthy, S., Rashtchian, C., & Sinha, M. (2018). Edge estimation with independent set oracles. In A. R. Karlin (Ed.), 9th Innovations in Theoretical Computer Science, ITCS 2018 [38] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 94). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2018.38