Editing Open Problems:90

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 5: Line 5:
 
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 {{Cite|AlonFNS-09}}.
 
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 {{Cite|AlonFNS-09}}.
  
These kinds of testers are, however, typically obtained via regularity lemmata, such as Szemerédi's Regularity Lemma, and the “constant” query complexity is often superpolynomial in $1/\varepsilon$ (more often than not, it is 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)$ {{Cite|Alon-02}}. See for instance Section 8.5 of Goldreich's book {{Cite|Goldreich-17}} for a summary of the state of the art in property testing in the dense graph model.
+
These kinds of testers are, however, typically obtained via regularity lemmata, such as Szemerédi's Regularity Lemma, and the “constant” query complexity if often superpolynomial in $1/\varepsilon$ (more often than not, it is 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)$ {{Cite|Alon-02}}. See for instance Section 8.5 of Goldreich's book {{Cite|Goldreich-17}} for a summary of the state of the art in property testing in the dense graph model.
  
 
Nevertheless, 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$.
 
Nevertheless, 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?
 
'''Concrete instance of the problem:''' Is there a $\operatorname{poly}(\log n, 1/\varepsilon)$-query tester for triangle freeness in the dense graph model?

Please note that all contributions to Open Problems in Sublinear Algorithms may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Open Problems in Sublinear Algorithms:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)