A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
From MaRDI portal
Publication:3549321
DOI10.1137/06064888XzbMATH Open1152.05055OpenAlexW1985538939WikidataQ105584134 ScholiaQ105584134MaRDI QIDQ3549321FDOQ3549321
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Extremal combinatorics (05D99)
Cited In (51)
- Testing versus estimation of graph properties, revisited
- Local Property Reconstruction and Monotonicity
- Title not available (Why is that?)
- Hypergraph regularity and random sampling
- On 3‐graphs with no four vertices spanning exactly two edges
- Sublinear-time Algorithms
- Fast distributed algorithms for testing graph properties
- On the Effect of the Proximity Parameter on Property Testers
- Quasi-random words and limits of word sequences
- Efficient Removal Lemmas for Matrices
- Contemplations on Testing Graph Properties
- Estimating parameters associated with monotone properties
- Testing graphs against an unknown distribution
- Testing Eulerianity and connectivity in directed sparse graphs
- Earthmover Resilience and Testing in Ordered Structures
- Sublinear Graph Approximation Algorithms
- A characterization of easily testable induced digraphs and \(k\)-colored graphs
- Testable and untestable classes of first-order formulae
- Title not available (Why is that?)
- Induced arithmetic removal: complexity 1 patterns over finite fields
- Additive approximation for edge-deletion problems
- A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing
- A separation theorem in property testing
- Easily Testable Graph Properties
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Parameter testing in bounded degree graphs of subexponential growth
- Local-vs-global combinatorics
- Non-Deterministic Graph Property Testing
- A unified framework for testing linear‐invariant properties
- Testing Expansion in Bounded-Degree Graphs
- Testing permutation properties through subpermutations
- Efficient Testing without Efficient Regularity
- An Algebraic Characterization of Testable Boolean CSPs
- Title not available (Why is that?)
- Polynomial removal lemmas for ordered graphs
- Minimum Number of Monotone Subsequences of Length 4 in Permutations
- A note on permutation regularity
- Fast Property Testing and Metrics for Permutations
- Estimating the distance to a hereditary graph property
- Efficient removal lemmas for matrices
- Lower bounds for testing triangle-freeness in Boolean functions
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- Every minor-closed property of sparse graphs is testable
- Title not available (Why is that?)
- Forbidding induced even cycles in a graph: typical structure and counting
- Inflatable Graph Properties and Natural Property Tests
- Degenerate Turán densities of sparse hypergraphs
- Testing Odd-Cycle-Freeness in Boolean Functions
- Testing Linear-Invariant Properties
- Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition
- Perfect graphs of fixed density: counting and homogeneous sets
This page was built for publication: A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549321)
