A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
From MaRDI portal
Publication:3549321
DOI10.1137/06064888XzbMATH Open1152.05055OpenAlexW1985538939WikidataQ105584134 ScholiaQ105584134MaRDI QIDQ3549321FDOQ3549321
Authors: Noga Alon, Asaf Shapira 
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 (52)
- Testing versus estimation of graph properties, revisited
- Local-vs-global combinatorics
- An algebraic characterization of testable Boolean CSPs
- A unified framework for testing linear-invariant properties
- Hypergraph regularity and random sampling
- On 3‐graphs with no four vertices spanning exactly two edges
- Sublinear-time Algorithms
- Efficient testing without efficient regularity
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- On the Effect of the Proximity Parameter on Property Testers
- Testability and repair of hereditary hypergraph properties
- Quasi-random words and limits of word sequences
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Contemplations on Testing Graph Properties
- Estimating parameters associated with monotone properties
- On the testability of graph partition properties
- Testing Eulerianity and connectivity in directed sparse graphs
- Earthmover Resilience and Testing in Ordered Structures
- A characterization of easily testable induced digraphs and \(k\)-colored graphs
- Testable and untestable classes of first-order formulae
- Testing odd-cycle-freeness in Boolean functions
- Induced arithmetic removal: complexity 1 patterns over finite fields
- Two-sided error proximity oblivious testing
- Local property reconstruction and monotonicity
- Additive approximation for edge-deletion problems
- Two-sided error proximity oblivious testing (extended abstract)
- Fast property testing and metrics for permutations
- A separation theorem in property testing
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Parameter testing in bounded degree graphs of subexponential growth
- Inflatable graph properties and natural property tests
- Testing Expansion in Bounded-Degree Graphs
- Testing permutation properties through subpermutations
- Efficient removal lemmas for matrices
- Title not available (Why is that?)
- Polynomial removal lemmas for ordered graphs
- Minimum Number of Monotone Subsequences of Length 4 in Permutations
- Sublinear graph approximation algorithms
- A note on permutation regularity
- Estimating the distance to a hereditary graph property
- Testing hereditary properties of sequences
- Efficient removal lemmas for matrices
- Easily testable graph properties
- 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
- Forbidding induced even cycles in a graph: typical structure and counting
- Non-deterministic graph property testing
- Degenerate Turán densities of sparse hypergraphs
- Testing Odd-Cycle-Freeness in Boolean Functions
- Testing Linear-Invariant Properties
- 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)
