Testing Expansion in Bounded-Degree Graphs
From MaRDI portal
Publication:4911108
DOI10.1017/S096354831000012XzbMath1260.05147MaRDI QIDQ4911108
Christian Sohler, Artur Czumaj
Publication date: 13 March 2013
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)
Related Items (8)
On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Zero-Knowledge Proofs of Proximity ⋮ On the characterization of 1-sided error strongly testable graph properties for 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 ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Dynamic complexity of expansion
Cites Work
- Unnamed Item
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Eigenvalues and expanders
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A sublinear bipartiteness tester for bounded degree graphs
- Expander graphs and their applications
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Testing the diameter of graphs
- Testing properties of directed graphs: acyclicity and connectivity*
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Abstract Combinatorial Programs and Efficient Property Testers
- Property testing in bounded degree graphs
This page was built for publication: Testing Expansion in Bounded-Degree Graphs
