Non-Deterministic Graph Property Testing

DOI10.1017/S0963548313000205zbMath1282.05198arXiv1202.5337WikidataQ106143888 ScholiaQ106143888MaRDI QIDQ5397730

László Lovász, Katalin Vesztergombi

Publication date: 24 February 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.5337

zbMATH Keywords

non-deterministically testable properties

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Limits of locally-globally convergent graph sequences, Deterministic vs non-deterministic graph property testing, Non-interactive proofs of proximity, Unnamed Item

Cites Work

• Testing properties of graphs and functions
• Property testing. Current research and surveys
• Limits of dense graph sequences
• Szemerédi's lemma for the analyst
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Quick approximation to matrices and applications
• Property testing and its connection to learning and approximation
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Robust Characterizations of Polynomials with Applications to Program Testing
• Efficient testing of large graphs