Editing Open Problems:30

{{DISPLAYTITLE:Problem 30: Universal Sketching}}
{{Infobox
|label1 = Proposed by
|data1 = Jelani Nelson
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/30
}}
Rather than designing different sketching algorithms for every
problem, it would be desirable to have algorithms that where
''universal'', in some sense, for a variety of problems.
Specifically, let $ {\mathcal F}$ be a family of functions mapping
frequency vector $[-M,M]^n$ to $\mathbb R$. We say could say a sketching
algorithm $A$ is $(\epsilon,\delta)$ universal for ${\mathcal F}$ if
for all $x\in [-M,M]^n$, $A$ can recover a $(1+\epsilon)$
approximation each $f(x)$ for any $f \in {\mathcal F}$ with
probability $1-\delta$.

An example would be when ${\mathcal F}$ is $\{F_p : 0\leq p\leq 2\}$.
A simple approach would be to discretize $p$ and to utilize the fact
that $\ell_p(x) \approx \ell_{p'}(x)$ if $p$ and $p'$ are sufficiently
close. Better yet would be to interpolate through a small set of
values, using ideas from Harvey, Nelson, and Onak {{cite|HarveyNO-08}}. Consequently it
should be possible to be universal for ${\mathcal F}=\{F_p : 0\leq
p\leq 2\}$ while using only slightly more space than that required to
estimate a specific $F_p$. For what other families are there efficient
universal algorithms?  It seems that the Indyk-Woodruff {{cite|IndykW-05}}
technique would be useful here, and that the work of
Braverman and Ostrovsky {{cite|BravermanO-10}} is also highly relevant.