A combinatorial characterization of the testable graph properties, it's all about regularity

DOI10.1145/1132516.1132555MaRDI QIDQ2931390zbMATH OpenOpenAlexFDO

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

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132555

zbMATH Keywords

regularity lemmacharacterizationproperty testing

Mathematics Subject Classification ID

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

Recommendations

• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• scientific article; zbMATH DE number 1241385
• Every monotone graph property is testable
• Every Monotone Graph Property Is Testable
• Efficient testing of large graphs

Cited in

(42)

• Testing whether a digraph contains H-free k-induced subgraphs
• On Sums of Locally Testable Affine Invariant Properties
• An algebraic characterization of testable Boolean CSPs
• Every Set in P Is Strongly Testable Under a Suitable Encoding
• Relational Properties Expressible with One Universal Quantifier Are Testable
• Every monotone graph property is testable
• Testing graph blow-up
• Efficient testing without efficient regularity
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• scientific article; zbMATH DE number 6846422 (Why is no real title available?)
• Contemplations on Testing Graph Properties
• Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
• Hierarchy theorems for property testing
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Every Monotone Graph Property Is Testable
• On one test for the switching separability of graphs modulo q
• Hierarchy theorems for property testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testable and untestable classes of first-order formulae
• Proximity Oblivious Testing and the Role of Invariances
• Indistinguishability and First-Order Logic
• A Brief Introduction to Property Testing
• A brief introduction to property testing
• On the benefits of adaptivity in property testing of dense graphs
• Introduction to testing graph properties
• A separation theorem in property testing
• Introduction to testing graph properties
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Testing properties of graphs and functions
• Proximity oblivious testing and the role of invariances
• Testing graph blow-up
• Characterizations of locally testable linear- and affine-invariant families
• Hierarchy theorems for testing properties in size-oblivious query complexity
• Measuring instance difficulty for combinatorial optimization problems
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Invariance in property testing
• On model selection for dense stochastic block models
• Comparing the strength of query types in property testing: the case of \(k\)-colorability
• Sparse affine-invariant linear codes are locally testable
• A note on permutation regularity
• Lower bounds for testing triangle-freeness in Boolean functions
• Predicting winner and estimating margin of victory in elections using sampling

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 Q2931390)