Metraipolis › archive › dc_05bb8d0d094d
Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds — arXiv:2611.04766
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04766
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T19:07:36.212Z
- SHA-256 of the archived text
86b2fee392d68fdf3b2a4f84bae9cc0acb9fc7abebaac9bdf913a660f9de6cb0- Stable URL of this page
https://metraipolis.com/documento/dc_05bb8d0d094d
How to cite
Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds — arXiv:2611.04766 — arXiv (en), https://arxiv.org/abs/2611.04766 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_05bb8d0d094d (Metraipolis archive dc_05bb8d0d094d, sha256 86b2fee392d68fdf3b2a4f84bae9cc0acb9fc7abebaac9bdf913a660f9de6cb0)
BibTeX
@misc{dc05bb8d0d094d,
title = {Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds — arXiv:2611.04766},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04766},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_05bb8d0d094d; sha256 86b2fee392d68fdf3b2a4f84bae9cc0acb9fc7abebaac9bdf913a660f9de6cb0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04766. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance. We study a relaxation in which only part of the graph is required to expand: does an $n$-vertex graph of bounded degree contain an induced expander on a constant fraction of its vertices, when the rest of the graph, including the edges leaving the expander, is arbitrary? Let $P_{\alpha,\phi}$ denote the property of containing an induced subgraph on at least $\alpha n$ vertices with inner conductance at least $\phi$. For every constant $\kappa\in(0,1)$, we give a tester that accepts graphs in $P_{\alpha,\phi}$ and rejects graphs outside $P_{\kappa\alpha,\mu\phi^2}$, where $\mu=\Theta_{\alpha,\kappa}(1/\log n)$, using $O_{\alpha,\kappa}(\sqrt n\,\phi^{-2}\log n)$ queries. For fixed $\alpha\in(0,1]$, $\kappa\in(0,1)$, and $0<\phi\le9/20$, we further show that distinguishing these two classes requires $\Omega_{\alpha,\kappa,\phi}(n^{1/2+c_{\kappa,\phi}\mu})$ queries for every sufficiently large $n$ and every $0<\mu\le1$, where $c_{\kappa,\phi}>0$. The bound holds for adaptive algorithms, uniformly in $\mu$. Hence, for testers with $\sqrt n\,\mathrm{polylog}(n)$ queries, the logarithmic loss in conductance is necessary up to a $\log\log n$ factor. The same tester also permits distance-based rejection at a weaker conductance while retaining the original core size. Our tester compares the endpoint distributions of random walks from different vertices with each other, rather than with the uniform distribution. Its analysis uses the trace chain, which observes the walk only at its visits to the unknown expanding core. Our lower bound builds on the noisy-parity construction of [CKK+18], using vector-valued parity labels in $\mathbb F_2^r$ to create many hidden classes, each too small to contain a qualifying induced expander.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.04766 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:40:52.459Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).