Noise Tolerance of Expanders and Sublinear Expansion Reconstruction

DOI10.1137/110837863zbMath1286.68237OpenAlexW1974544894MaRDI QIDQ2839180

Satyen Kale, Yuval Peres, C. Seshadhri

Publication date: 4 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110837863

zbMATH Keywords

random walkssublinear algorithmsgraph expansionsublinear reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (6)

Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ Can we locally compute sparse connected subgraphs? ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Local algorithms for sparse spanning graphs ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs

This page was built for publication: Noise Tolerance of Expanders and Sublinear Expansion Reconstruction