Open Problems:100

2023-03-09T06:50:44Z

18.29.41.105: Update with reference resolving problem.

{{Header
|source=wola19
|who=Oded Goldreich
}}
For a probability distribution $p$ over a discrete domain $\Omega$, and a parameter $\varepsilon\in[0,1]$, denote by
\[
\operatorname{ess}_\varepsilon(p) \stackrel{\rm def}{=} \min\{ \operatorname{supp}(q) : \operatorname{d}_{\rm TV}(p,q) \leq \varepsilon \}
\]
the $\varepsilon$-effective suport size of $p$, i.e., the smallest possible support size of any distribution $\varepsilon$-close to $p$. This turns out to be a more robust and interesting measure in general than the support of $p$, which is $\operatorname{ess}_0(p) = \operatorname{supp}(p)$. In recent work, Goldreich {{Cite|Goldreich-19b}} focused on the query complexity of approximating the effective support size of a discrete distribution provided via two oracles: sampling ($\textsf{samp}_p$), and query access (to the probability mass function), $\textsf{eval}_p$. In particular, the goal is, given parameters $\varepsilon$ and $\beta>1$, to output an $f(\varepsilon,\beta,n)$-factor approximation of $\operatorname{ess}_{\varepsilon'}(p)$, for some $\varepsilon' \in [\varepsilon,\beta\varepsilon]$.

In the aforementioned work, algorithms are obtained achieving (for constant $\beta>1$)

* query complexity $\operatorname{poly}(1/\varepsilon)$ and approximation factor $f = O(\log\log\log\log(n/\varepsilon))$, that is, any constant number of iterated logarithms;

* query complexity $\operatorname{poly}(\log^\ast n, 1/\varepsilon)$ even for approximation factor $f = O(1)$;

where $n \stackrel{\rm def}{=} \operatorname{ess}_\varepsilon(p)$. (As well as several other results interpolating between the two extremes.)

'''Question:''' Can one get the best of both worlds, and get rid of the $\log^\ast n$ to obtain query complexity $\operatorname{poly}(1/\varepsilon)$ ''and'' constant approximation factor?

== Update ==
This problem has been resolved in the positive direction (https://arxiv.org/abs/2211.11344).

Open Problems in Sublinear Algorithms - User contributions [en]

Open Problems:100