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


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
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
ISSN (Print)1868-8969


Other9th Innovations in Theoretical Computer Science, ITCS 2018
Country/TerritoryUnited States


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

ASJC Scopus subject areas

  • Software


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

Cite this