When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries

Tomer Adar, Yahel Hotam, Amit Levi

We study the problem of estimating the number of edges in an unknown graph. We consider a hybrid model in which an algorithm may issue independent set, degree, and neighbor queries…