Problem 30: Universal Sketching

Proposed by	Jelani Nelson
Source	Kanpur 2009
Short link	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 [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 [IndykW-05] technique would be useful here, and that the work of Braverman and Ostrovsky [BravermanO-10] is also highly relevant.