Problem 30: Universal Sketching

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
Suggested by Jelani Nelson
Source Kanpur 2009
Short link

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.