Testing versus estimation of graph properties, revisited
From MaRDI portal
Publication:6623575
DOI10.1002/rsa.21221MaRDI QIDQ6623575
Lior Gishboliner, Asaf Shapira, Nick Kushnir
Publication date: 24 October 2024
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Szemerédi's lemma for the analyst
- Generalizations of the removal lemma
- On graphs with small subgraphs of large chromatic number
- Quick approximation to matrices and applications
- Bounds for graph regularity and removal lemmas
- Tolerant property testing and distance approximation
- Local Reconstructors and Tolerant Testers for Connectivity and Diameter
- Graph limits and parameter testing
- Property testing and its connection to learning and approximation
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- A sublinear algorithm for weakly approximating edit distance
- Tolerant Linearity Testing and Locally Testable Codes
- Three theorems regarding testing graph properties
- Testing Bounded Arboricity
- A sparse regular approximation lemma
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Removal lemmas with polynomial bounds
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Estimating parameters associated with monotone properties
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
- Easily Testable Graph Properties
- Introduction to Property Testing
- Testing versus Estimation of Graph Properties
- Testing Closeness of Discrete Distributions
- Estimating the distance to a monotone function
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Efficient testing of large graphs
- Tolerant Testers of Image Properties
This page was built for publication: Testing versus estimation of graph properties, revisited
