Editing Open Problems:88

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 2: Line 2:
 
|source=focs17
 
|source=focs17
 
|who=Clément Canonne
 
|who=Clément Canonne
 +
|title=Separating PDF and CDF query models
 
}}
 
}}
 
Recall that in the ''dual'' and ''cumulative dual'' models of distribution testing {{cite|CanonneR-14}}, the testing is provided with two types of access to the unknown probability distribution $p$ (for the sake of the cumulative dual, over a totally ordered domain $[n]=\{1,\dots,n\}$): the first is the usual sampling oracle, which returns i.i.d. samples from $p$; and the second is an evaluation oracle, which on query $i\in[n]$ returns $p(i)$ (or, for the cumulative dual model, returns $p([1,i])=\sum_{j=1}^i p(j)$). In other words, the algorithm has sample access to $p$ ''and'' query access to its probability mass function (resp. cumulative distribution function).
 
Recall that in the ''dual'' and ''cumulative dual'' models of distribution testing {{cite|CanonneR-14}}, the testing is provided with two types of access to the unknown probability distribution $p$ (for the sake of the cumulative dual, over a totally ordered domain $[n]=\{1,\dots,n\}$): the first is the usual sampling oracle, which returns i.i.d. samples from $p$; and the second is an evaluation oracle, which on query $i\in[n]$ returns $p(i)$ (or, for the cumulative dual model, returns $p([1,i])=\sum_{j=1}^i p(j)$). In other words, the algorithm has sample access to $p$ ''and'' query access to its probability mass function (resp. cumulative distribution function).
  
It is immediate to see that the cumulative dual model is at least as powerful as the dual model, since any query to the pmf of $p$ can be simulated from 2 queries to its cdf. However, currently there is no strict separation known between dual and cumulative dual models for natural properties, i.e., a property $\mathcal{P}$ (or functional $\Phi$) of distributions for which testing (resp. estimation) requires asymptotically significantly more samples in the dual model than in the cumulative dual.
+
It is immediate to see that the cumulative dual model is at least as powerful as the dual model, since any query to the pmf of $p$ can be simulated from 2 queries to its cdf. However, currently there is no strict separation known between dual and cumulative dual models for natural properties, i.e. a property $\mathcal{P}$ (or functional $\Phi$) of distributions for which testing (resp. estimation) requires asymptotically significantly more samples in the dual model than in the cumulative dual.
  
 
Does there exist such a separation?
 
Does there exist such a separation?
  
Canonne and Rubinfeld show in {{cite|CanonneR-14}} a somewhat contrived separation, for estimating the entropy of distributions promised to be close to monotone. A natural conjecture would be that such a separation would exist for a property of functional where the total order (and thus the cumulative access) is essential, e.g., testing monotonicity or estimating distance to it. (The best currently known upper bounds for testing monotonicity are respectively $O((\log n)/\varepsilon)$ in the dual model, and $\tilde{O}(1/\varepsilon^4)$ in the cumulative dual {{cite|Canonne-15}}.)
+
Canonne and Rubinfeld show in {{cite|CanonneR-14}} a somewhat contrived separation, for estimating the entropy of distributions promised to be close to monotone. A natural conjecture would be that such a separation would exist for a property of functional where the total order (and thus the cumulative access) is essential, e.g. testing monotonicity or estimating distance to it. (The best currently known upper bounds for testing monotonicity are respectively $O((\log n)/\varepsilon)$ in the dual model, and $\tilde{O}(1/\varepsilon^4)$ in the cumulative dual {{cite|Canonne-15}}.)

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)