When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910004471136256 |
|---|---|
| author | Adar, Tomer Hotam, Yahel Levi, Amit |
| author_facet | Adar, Tomer Hotam, Yahel Levi, Amit |
| contents | 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\pm\varepsilon)$-approximation of the number of edges using $O\left(\min\left(\sqrt{m}, \sqrt{\frac{n}{\sqrt{m}}}\right)\cdot\frac{\log n}{\varepsilon^{5/2}}\right)$ queries, and prove a nearly matching lower bound.
In contrast, prior work shows that in the local query model (Goldreich and Ron, \textit{Random Structures \& Algorithms} 2008) and in the independent set query model (Beame \emph{et al.} ITCS 2018, Chen \emph{et al.} SODA 2020), edge estimation requires $\widetildeΘ(n/\sqrt{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21457 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries Adar, Tomer Hotam, Yahel Levi, Amit Data Structures and Algorithms 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\pm\varepsilon)$-approximation of the number of edges using $O\left(\min\left(\sqrt{m}, \sqrt{\frac{n}{\sqrt{m}}}\right)\cdot\frac{\log n}{\varepsilon^{5/2}}\right)$ queries, and prove a nearly matching lower bound. In contrast, prior work shows that in the local query model (Goldreich and Ron, \textit{Random Structures \& Algorithms} 2008) and in the independent set query model (Beame \emph{et al.} ITCS 2018, Chen \emph{et al.} SODA 2020), edge estimation requires $\widetildeΘ(n/\sqrt{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. |
| title | When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.21457 |