Polynomial Property Testing
Preprint
Abstract
Property testers are fast, randomized "election polling"-type algorithms that determine if an input (e.g., graph or hypergraph) has a certain property or is $\varepsilon$-far from the property. In the dense graph model of property testing, it is known that many properties can be tested with query complexity that depends only on the error parameter $\varepsilon$ (and not on the size of the input), but the current bounds on the query complexity grow extremely quickly as a function of $1/\varepsilon$. Which properties can be tested efficiently, i.e., with $\mathrm{poly}(1/\varepsilon)$ queries? This survey presents the state of knowledge on this general question, as well as some key open problems.
Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Testing versus estimation of graph properties, revisitedRandom Structures & Algorithms, 2024
- Regularity Partitions and The Topology of Graphons2010
- Applications of the regularity lemma for uniform hypergraphsRandom Structures & Algorithms, 2005
- Regularity Lemma for k‐uniform hypergraphsRandom Structures & Algorithms, 2004
- Three theorems regarding testing graph propertiesRandom Structures & Algorithms, 2003
- Testing subgraphs in large graphsRandom Structures & Algorithms, 2002
- Property testers for dense constraint satisfaction programs on finite domainsRandom Structures & Algorithms, 2002
- Efficient Testing of Large GraphsCombinatorica, 2000
- Quick Approximation to Matrices and ApplicationsCombinatorica, 1999
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964