https://sublinear.info/index.php?title=Open_Problems:99&feed=atom&action=historyOpen Problems:99 - Revision history2024-03-29T07:55:46ZRevision history for this page on the wikiMediaWiki 1.31.10https://sublinear.info/index.php?title=Open_Problems:99&diff=1300&oldid=prevKrzysztof Onak: Krzysztof Onak moved page Waiting:Vertex-Distribution-Free Graph Testing to Open Problems:99 without leaving a redirect2019-08-26T18:26:50Z<p>Krzysztof Onak moved page <a href="/index.php?title=Waiting:Vertex-Distribution-Free_Graph_Testing&action=edit&redlink=1" class="new" title="Waiting:Vertex-Distribution-Free Graph Testing (page does not exist)">Waiting:Vertex-Distribution-Free Graph Testing</a> to <a href="/index.php?title=Open_Problems:99" title="Open Problems:99">Open Problems:99</a> without leaving a redirect</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 18:26, 26 August 2019</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>Krzysztof Onakhttps://sublinear.info/index.php?title=Open_Problems:99&diff=1299&oldid=prevKrzysztof Onak: Updating the header2019-08-26T18:26:36Z<p>Updating the header</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 18:26, 26 August 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Header</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Header</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|title=Vertex-Distribution-Free Graph Testing</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|source=wola19</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|source=wola19</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td></tr>
</table>Krzysztof Onakhttps://sublinear.info/index.php?title=Open_Problems:99&diff=1280&oldid=prevKrzysztof Onak at 02:20, 25 August 20192019-08-25T02:20:50Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 02:20, 25 August 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the <del class="diffchange diffchange-inline">"</del>distribution-free<del class="diffchange diffchange-inline">" </del>model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19a}} <del class="diffchange diffchange-inline">''(note: this </del>model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}}<del class="diffchange diffchange-inline">)''</del>, one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the <ins class="diffchange diffchange-inline">&ldquo;</ins>distribution-free<ins class="diffchange diffchange-inline">&rdquo; </ins>model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19a}}<ins class="diffchange diffchange-inline"><ref>This </ins>model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}}<ins class="diffchange diffchange-inline">.</ref></ins>, one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? <del class="diffchange diffchange-inline">''(Note: </del>This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.<del class="diffchange diffchange-inline">)''</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges?<ins class="diffchange diffchange-inline"><ref></ins>This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.<ins class="diffchange diffchange-inline"></ref></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">==Notes==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><references /></ins></div></td></tr>
</table>Krzysztof Onakhttps://sublinear.info/index.php?title=Open_Problems:99&diff=1232&oldid=prevCcanonne at 21:35, 7 August 20192019-08-07T21:35:07Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:35, 7 August 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the "distribution-free" model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-<del class="diffchange diffchange-inline">19</del>}} ''(note: this model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}})'', one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the "distribution-free" model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-<ins class="diffchange diffchange-inline">19a</ins>}} ''(note: this model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}})'', one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? ''(Note: This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.)''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? ''(Note: This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.)''</div></td></tr>
</table>Ccanonnehttps://sublinear.info/index.php?title=Open_Problems:99&diff=1230&oldid=prevCcanonne at 21:30, 7 August 20192019-08-07T21:30:06Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:30, 7 August 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l6" >Line 6:</td>
<td colspan="2" class="diff-lineno">Line 6:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the "distribution-free" model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19}} ''(note: this model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}})'', one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the "distribution-free" model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19}} ''(note: this model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}})'', one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>'''Question:'''Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? ''(Note: This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.)''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? ''(Note: This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.)''</div></td></tr>
</table>Ccanonnehttps://sublinear.info/index.php?title=Open_Problems:99&diff=1229&oldid=prevCcanonne at 21:29, 7 August 20192019-08-07T21:29:52Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 21:29, 7 August 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|who=Oded Goldreich</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random<del class="diffchange diffchange-inline">, as mentioned in the previous open problem, </del>may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the "distribution-free" model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19}} ''(note: this model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}})'', one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the "distribution-free" model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19}} ''(note: this model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}})'', one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:'''Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:'''Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? ''(Note: This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.)''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? ''(Note: This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.)''</div></td></tr>
</table>Ccanonnehttps://sublinear.info/index.php?title=Open_Problems:99&diff=1228&oldid=prevCcanonne: Created page with "{{Header |title=Vertex-Distribution-Free Graph Testing |source=wola19 |who=Oded Goldreich }} The graph query model where one gets to query vertices uniformly at random, as men..."2019-08-07T21:28:48Z<p>Created page with "{{Header |title=Vertex-Distribution-Free Graph Testing |source=wola19 |who=Oded Goldreich }} The graph query model where one gets to query vertices uniformly at random, as men..."</p>
<p><b>New page</b></p><div>{{Header<br />
|title=Vertex-Distribution-Free Graph Testing<br />
|source=wola19<br />
|who=Oded Goldreich<br />
}}<br />
The graph query model where one gets to query vertices uniformly at random, as mentioned in the previous open problem, may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the "distribution-free" model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19}} ''(note: this model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}})'', one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.<br />
<br />
'''Question:'''Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.<br />
<br />
'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges? ''(Note: This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.)''</div>Ccanonne