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