DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.33

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

Authors: Tomer Adar, Yahel Hotam, and Amit Levi

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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. We show that this model admits strictly more efficient edge estimation than either access type alone. Specifically, we give a randomized algorithm that outputs a (1±ε)-approximation of the number of edges using O(min(√m, √{n/√m})⋅(log n)/ε^{5/2}) queries, and prove a nearly matching lower bound. In contrast, prior work shows that in the local query model (Goldreich and Ron, Random Structures & Algorithms 2008) and in the independent set query model (Beame et al. ITCS 2018, Chen et al. SODA 2020), edge estimation requires Θ̃(n/√m) queries in the same parameter regimes. Our results therefore yield a quadratic improvement in the hybrid model, and no asymptotically better improvement is possible.

Cite as

Tomer Adar, Yahel Hotam, and Amit Levi. When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{adar_et_al:LIPIcs.APPROX/RANDOM.2026.33,
  author =	{Adar, Tomer and Hotam, Yahel and Levi, Amit},
  title =	{{When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.33},
  URN =		{urn:nbn:de:0030-drops-277509},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.33},
  annote =	{Keywords: Edge count estimation, Degree oracle, Neighbor oracle, Independent-set oracle}
}

Search Results

Documents authored by Hotam, Yahel

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

Abstract

Cite as

Thanks for your feedback!

Could not send message