Edge Estimation with Independent Set Oracles

Paul Beame, Sariel Har-Peled, S. N. Ramamoorthy, Cyrus Rashtchian, Makrand Sinha

Research output: Contribution to journalArticlepeer-review


We study the task of estimating the number of edges in a graph, where the access to the graph is provided via 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, using (i) polylog(n) bipartite independent set queries or (ii) n2/3 polylog(n) independent set queries.

Original languageEnglish (US)
Article number3404867
JournalACM Transactions on Algorithms
Issue number4
StatePublished - Sep 2020


  • Independent set queries
  • graph parameter estimation

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Edge Estimation with Independent Set Oracles'. Together they form a unique fingerprint.

Cite this