On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
DOI10.1137/19M1283951zbMath1462.68238arXiv1912.01081OpenAlexW3166885009MaRDI QIDQ4992842
Richard Lang, Yoshiharu Kohayakawa, Henrique Stagni, Hanno Lefmann, Carlos Hoppen
Publication date: 10 June 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.01081
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- A new proof of the graph removal lemma
- Szemerédi's lemma for the analyst
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Quick approximation to matrices and applications
- Estimating the distance to a hereditary graph property
- Bounds for graph regularity and removal lemmas
- Efficient removal without efficient regularity
- Additive approximation for edge-deletion problems
- Contemplations on Testing Graph Properties
- Property testing and its connection to learning and approximation
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Every Monotone Graph Property Is Testable
- Three theorems regarding testing graph properties
- Estimating parameters associated with monotone properties
- Removal lemmas with polynomial bounds
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Easily Testable Graph Properties
- Introduction to Property Testing
- Testing versus Estimation of Graph Properties
- Efficient testing of large graphs
This page was built for publication: On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
