A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
From MaRDI portal
Publication:5189542
DOI10.1137/060667177zbMath1197.05159OpenAlexW2016987856WikidataQ105584121 ScholiaQ105584121MaRDI QIDQ5189542
Ilan Newman, Noga Alon, Eldar Fischer, 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
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Extremal combinatorics (05D99)
Related Items (41)
Testing graphs against an unknown distribution ⋮ Densities in large permutations and parameter testing ⋮ Testing list \(H\)-homomorphisms ⋮ Sunflowers and testing triangle-freeness of functions ⋮ A unified view of graph regularity via matrix decompositions ⋮ Hypergraph regularity and random sampling ⋮ Seeding with Costly Network Information ⋮ The Bradley-Terry condition is \(L_1\)-testable ⋮ Local-vs-global combinatorics ⋮ 2-transitivity is insufficient for local testability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Efficient Testing without Efficient Regularity ⋮ Deterministic vs non-deterministic graph property testing ⋮ Testing Euclidean Spanners ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ Non-interactive proofs of proximity ⋮ Testing Expansion in Bounded-Degree Graphs ⋮ Every minor-closed property of sparse graphs is testable ⋮ Testing permutation properties through subpermutations ⋮ Sublinear-time Algorithms ⋮ Local Property Reconstruction and Monotonicity ⋮ A note on permutation regularity ⋮ Earthmover Resilience and Testing in Ordered Structures ⋮ Quasi-random words and limits of word sequences ⋮ On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs ⋮ Inflatable Graph Properties and Natural Property Tests ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ 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 proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time ⋮ A unified framework for testing linear‐invariant properties ⋮ 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 ⋮ On the Query Complexity of Estimating the Distance to Hereditary Graph Properties ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Estimating parameters associated with monotone properties ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian
This page was built for publication: A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
