A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

DOI10.1137/060667177MaRDI QIDQ5189542zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira

Publication date 17 March 2010

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

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

zbMATH Keywords

characterizationproperty testingregularity Lemmatestable graph properties

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal combinatorics (05D99) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• A combinatorial characterization of the testable graph properties, it's all about regularity
• On testable properties in bounded degree graphs
• On the testability of graph partition properties
• scientific article; zbMATH DE number 7758318
• Property testing on \(k\)-vertex-connectivity of graphs
• Property Testing on k-Vertex-Connectivity of Graphs
• Every property of outerplanar graphs is testable
• Every property of hyperfinite graphs is testable
• Every property of hyperfinite graphs is testable
• Testing the \((s,t)\) connectivity of graphs and digraphs

Cited in

(51)

• The Bradley-Terry condition is \(L_1\)-testable
• Non-interactive proofs of proximity
• 2-transitivity is insufficient for local testability
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• A combinatorial characterization of the testable graph properties, it's all about regularity
• On one test for the switching separability of graphs modulo q
• Inflatable graph properties and natural property tests
• Densities in large permutations and parameter testing
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• Testing list H-homomorphisms
• Every monotone graph property is testable
• Every Monotone Graph Property Is Testable
• scientific article; zbMATH DE number 6846422 (Why is no real title available?)
• Deterministic vs non-deterministic graph property testing
• Testing Expansion in Bounded-Degree Graphs
• Sublinear-time Algorithms
• Testing Euclidean Spanners
• Local property reconstruction and monotonicity
• A unified framework for testing linear-invariant properties
• On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
• Estimating parameters associated with monotone properties
• Efficient testing without efficient regularity
• Sublinear algorithms for MAXCUT and correlation clustering
• On the testability of graph partition properties
• Seeding with costly network information
• Earthmover Resilience and Testing in Ordered Structures
• A characterization of constant-sample testable properties
• Planar graphs: random walks and bipartiteness testing
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• Partially symmetric functions are efficiently isomorphism testable
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• Testing permutation properties through subpermutations
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• A note on permutation regularity
• Quasi-random words and limits of word sequences
• Efficient testing of large graphs
• A unified view of graph regularity via matrix decompositions
• Hypergraph regularity and random sampling
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• Local-vs-global combinatorics
• Testing Eulerianity and connectivity in directed sparse graphs
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Testing versus estimation of graph properties, revisited
• The power and limitations of uniform samples in testing properties of figures
• A characterization of testable hypergraph properties
• Ordered graph limits and their applications
• Testing depth first search numbering
• Every minor-closed property of sparse graphs is testable

This page was built for publication: A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5189542)