Open Problems:90 - Revision history

Ccanonne at 04:31, 20 August 2019

2019-08-20T04:31:24Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Dense Graph Property Testing Tradeoffs to Open Problems:90 without leaving a redirect

2019-08-20T03:39:09Z

Krzysztof Onak moved page Waiting:Dense Graph Property Testing Tradeoffs to Open Problems:90 without leaving a redirect

Krzysztof Onak: Editing the header

2019-08-20T03:38:32Z

Editing the header

Krzysztof Onak: Further edits, adding another citation

2018-07-19T01:46:17Z

Further edits, adding another citation

Krzysztof Onak: Adding some citations

2018-07-19T01:24:14Z

Adding some citations

Krzysztof Onak at 01:07, 19 July 2018

2018-07-19T01:07:53Z

Ccanonne at 20:04, 27 March 2018

2018-03-27T20:04:08Z

Ccanonne: Created page with "{{Header |title=Dense Graph Property Testing "Tradeoffs" |source=online |who=Clement Canonne }} In the dense graph model of property testing (where the testing algorithm is g..."

2018-03-27T20:03:42Z

Created page with "{{Header |title=Dense Graph Property Testing "Tradeoffs" |source=online |who=Clement Canonne }} In the dense graph model of property testing (where the testing algorithm is g..."

New page

{{Header
|title=Dense Graph Property Testing "Tradeoffs"
|source=online
|who=Clement Canonne
}}

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 the above sense). Moreover, we now have a full characterization of the graph properties which admit such $O_\varepsilon(1)$-query testers.

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 exponent size $\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)$. (
See for instance Section 8.5 of Oded Goldreich's *Introduction to Property Testing* book for a summary of the state-of-the-art in property testing in the dense graph model.)

However, nothing ''a priori'' precludes these properties to have testers with query complexity $\sqrt{n}\operatorname{poly}(\log n, 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$ one can achieve? (Note that ''every'' property trivially has a tester with query complexity $O(n^2)$, so it's only a question of how far down this dependence on $n$ can be brought while keeping a reasonable dependence on $\varepsilon$)

As a concrete instance of the problem:

'''Open problem.''' Is there a $\operatorname{poly}(\log n, 1/\varepsilon)$-query tester for triangle freeness in the dense graph model?

@@ 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 &ldquo;a number of queries depending only on the proximity parameter $\varepsilon$ (but not $n$).&rdquo; 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 &ldquo;constant&rdquo; 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.
+These kinds of testers are, however, typically obtained via regularity lemmata, such as Szemerédi's Regularity Lemma, and the &ldquo;constant&rdquo; 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.
 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?

@@ Line 1: / Line 1: @@
 {{Header
 |source=warwick18
 |who=Clément Canonne

@@ Line 4: / Line 4: @@
 |who=Clément Canonne
 }}
-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 &ldquo;a number of queries depending only on the proximity parameter $\varepsilon$ (but not $n$).&rdquo; 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?]'''.
+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 &ldquo;a number of queries depending only on the proximity parameter $\varepsilon$ (but not $n$).&rdquo; 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}}.
-Yet, these results are typically obtained via regularity lemmata, such as Szemerédi's Regularity Lemma, and the &ldquo;constant&rdquo; 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)$ {{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 &ldquo;constant&rdquo; 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.
-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$.
+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?

@@ Line 6: / Line 6: @@
 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 &ldquo;a number of queries depending only on the proximity parameter $\varepsilon$ (but not $n$).&rdquo; 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 &ldquo;constant&rdquo; 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.
+Yet, these results are typically obtained via regularity lemmata, such as Szemerédi's Regularity Lemma, and the &ldquo;constant&rdquo; 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)$ {{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.
 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?

← Older revision	Revision as of 03:39, 20 August 2019
(No difference)

@@ Line 12: / Line 12: @@
 See for instance Section 8.5 of Oded Goldreich's *Introduction to Property Testing* book for a summary of the state-of-the-art in property testing in the dense graph model.)
-However, nothing ''a priori'' precludes these properties to have testers with query complexity $\sqrt{n}\operatorname{poly}(\log n, 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$ one can achieve? (Note that ''every'' property trivially has a tester with query complexity $O(n^2)$, so it's only a question of how far down this dependence on $n$ can be brought while keeping a reasonable dependence on $\varepsilon$)
+However, nothing ''a priori'' precludes these properties to have 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$ one can achieve? (Note that ''every'' property trivially has a tester with query complexity $O(n^2)$, so it's only a question of how far down this dependence on $n$ can be brought while keeping a reasonable dependence on $\varepsilon$)
 As a concrete instance of the problem:
 '''Open problem.''' Is there a $\operatorname{poly}(\log n, 1/\varepsilon)$-query tester for triangle freeness in the dense graph model?