A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
From MaRDI portal
Publication:3549321
DOI10.1137/06064888XzbMath1152.05055OpenAlexW1985538939WikidataQ105584134 ScholiaQ105584134MaRDI QIDQ3549321
Publication date: 22 December 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/06064888x
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Extremal combinatorics (05D99)
Related Items
Testing graphs against an unknown distribution, Testing Odd-Cycle-Freeness in Boolean Functions, A characterization of easily testable induced digraphs and \(k\)-colored graphs, Polynomial removal lemmas for ordered graphs, Induced arithmetic removal: complexity 1 patterns over finite fields, Fast Property Testing and Metrics for Permutations, Perfect Graphs of Fixed Density: Counting and Homogeneous Sets, Additive approximation for edge-deletion problems, An Algebraic Characterization of Testable Boolean CSPs, Efficient Removal Lemmas for Matrices, Efficient removal lemmas for matrices, Testing Linear-Invariant Properties, On the Effect of the Proximity Parameter on Property Testers, On 3‐graphs with no four vertices spanning exactly two edges, Hypergraph regularity and random sampling, Estimating the distance to a hereditary graph property, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Unnamed Item, Local-vs-global combinatorics, Minimum Number of Monotone Subsequences of Length 4 in Permutations, Easily Testable Graph Properties, Unnamed Item, Testable and untestable classes of first-order formulae, Unnamed Item, Testing Eulerianity and connectivity in directed sparse graphs, Efficient Testing without Efficient Regularity, Non-Deterministic Graph Property Testing, A separation theorem in property testing, Forbidding induced even cycles in a graph: typical structure and counting, Testing Expansion in Bounded-Degree Graphs, Every minor-closed property of sparse graphs is testable, Testing permutation properties through subpermutations, Sublinear-time Algorithms, Sublinear Graph Approximation Algorithms, Local Property Reconstruction and Monotonicity, Parameter testing in bounded degree graphs of subexponential growth, Fast distributed algorithms for testing graph properties, 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, Contemplations on Testing Graph Properties, Degenerate Turán densities of sparse hypergraphs, A unified framework for testing linear‐invariant properties, 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, Unnamed Item, Lower bounds for testing triangle-freeness in Boolean functions
