Difference between revisions of "Open Problems:99"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (Krzysztof Onak moved page Waiting:Vertex-Distribution-Free Graph Testing to Open Problems:99 without leaving a redirect)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Vertex-Distribution-Free Graph Testing
 
 
|source=wola19
 
|source=wola19
 
|who=Oded Goldreich
 
|who=Oded Goldreich
 
}}
 
}}
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}$.
+
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 &ldquo;distribution-free&rdquo; 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}}<ref>This model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}}.</ref>, 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}$.
  
 
'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.
 
'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.
  
'''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.)''
+
'''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?<ref>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.</ref>
 +
 
 +
==Notes==
 +
<references />

Latest revision as of 18:26, 26 August 2019

Suggested by Oded Goldreich
Source WOLA 2019
Short link https://sublinear.info/99

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 [Goldreich-19a][1], 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}$.

Question: Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.

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?[2]

Notes[edit]

  1. This model was also briefly discussed in Section 10.1 of [GoldreichGR-98].
  2. This type of variant was also briefly evoked in Section 10.1.4 of [GoldreichGR-98], where it was shown that Bipartiteness is not testable in such an EDF model.