A combinatorial characterization of the testable graph properties
From MaRDI portal
Publication:2931390
DOI10.1145/1132516.1132555zbMath1301.05354OpenAlexW2069200876MaRDI QIDQ2931390
Asaf Shapira, Ilan Newman, Noga Alon, Eldar Fischer
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
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Extremal combinatorics (05D99)
Related Items
On model selection for dense stochastic block models, An Algebraic Characterization of Testable Boolean CSPs, On the benefits of adaptivity in property testing of dense graphs, Testing properties of graphs and functions, Indistinguishability and First-Order Logic, Comparing the strength of query types in property testing: the case of \(k\)-colorability, Hierarchy theorems for property testing, Testable and untestable classes of first-order formulae, Algorithmic Aspects of Property Testing in the Dense Graphs Model, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Hierarchy Theorems for Property Testing, Predicting winner and estimating margin of victory in elections using sampling, A separation theorem in property testing, Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, Measuring instance difficulty for combinatorial optimization problems, Sparse affine-invariant linear codes are locally testable, Invariance in Property Testing, Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability, A note on permutation regularity, Hierarchy theorems for testing properties in size-oblivious query complexity, Testing Graph Blow-Up, Testing Graph Blow-Up, Proximity Oblivious Testing and the Role of Invariances, Proximity Oblivious Testing and the Role of Invariances, On Sums of Locally Testable Affine Invariant Properties, Limits on the Rate of Locally Testable Affine-Invariant Codes, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, Contemplations on Testing Graph Properties, Every Set in P Is Strongly Testable Under a Suitable Encoding, Relational Properties Expressible with One Universal Quantifier Are Testable, Characterizations of locally testable linear- and affine-invariant families, Lower bounds for testing triangle-freeness in Boolean functions
