Problem 90: Dense Graph Property Testing “Tradeoffs”
| Suggested by | Clément Canonne |
|---|---|
| Source | Warwick 2018 |
| Short link | https://sublinear.info/90 |
In the dense graph model of property testing (where the testing algorithm is granted query access to the adjacency matrix of an unknown $n$-node graph, and the distance measure is the fraction of entries of this matrix that needs to be changed for the graph to satisfy the property), testability was originally defined as meaning “a number of queries depending only on the proximity parameter $\varepsilon$ (but not $n$).” Many properties, such as graph partition properties, triangle-freeness, and more generally $H$-freeness, are known to be testable with a constant number of queries in this sense. Moreover, we now have a full characterization of the graph properties that admit $O_\varepsilon(1)$-query testers [add citations?].
Yet, these results are typically obtained via regularity lemmata, such as Szemerédi's Regularity Lemma, and the “constant” query complexity if often superpolynomial in $1/\varepsilon$ (or, often, even a tower of 2's of height $\operatorname{poly}(1/\varepsilon)$). This is not an oversight: triangle freeness, for instance, provably does not have any tester with query complexity $\operatorname{poly}(1/\varepsilon)$ [add citation?]. See for instance Section 8.5 of Oded Goldreich's *Introduction to Property Testing* book [turn into a citation?] for a summary of the state-of-the-art in property testing in the dense graph model.
However, nothing a priori precludes these properties from having testers with query complexity $\sqrt{n}\operatorname{poly}(1/\varepsilon)$, $\operatorname{poly}(\log n, 1/\varepsilon)$, or even $\operatorname{poly}(\log^* n, 1/\varepsilon)$. What is the best possible tradeoff between $n$ and $\varepsilon$? Note that every property trivially has a tester with query complexity $O(n^2)$, so the question is how far down this dependence on $n$ can be brought while keeping a reasonable dependence on $\varepsilon$.
Concrete instance of the problem: Is there a $\operatorname{poly}(\log n, 1/\varepsilon)$-query tester for triangle freeness in the dense graph model?
