A combinatorial characterization of the testable graph properties, it's all about regularity
DOI10.1145/1132516.1132555zbMATH Open1301.05354OpenAlexW2069200876MaRDI QIDQ2931390FDOQ2931390
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Extremal combinatorics (05D99)
Cited In (42)
- Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs
- 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
- Testing graph blow-up
- Efficient testing without efficient regularity
- Every monotone graph property is testable
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Title not available (Why is that?)
- Contemplations on Testing Graph Properties
- Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
- Every Monotone Graph Property Is Testable
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Hierarchy theorems for property testing
- Hierarchy theorems for property testing
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- On one test for the switching separability of graphs modulo \(q\)
- Proximity Oblivious Testing and the Role of Invariances
- Testable and untestable classes of first-order formulae
- 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
- Proximity oblivious testing and the role of invariances
- Testing properties of graphs and functions
- Testing graph blow-up
- Hierarchy theorems for testing properties in size-oblivious query complexity
- Characterizations of locally testable linear- and affine-invariant families
- 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
- A note on permutation regularity
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- Sparse affine-invariant linear codes are locally testable
- Lower bounds for testing triangle-freeness in Boolean functions
- Predicting winner and estimating margin of victory in elections using sampling
- On Sums of Locally Testable Affine Invariant Properties
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)
