# Problem 30: Universal Sketching

Suggested by | Jelani Nelson |
---|---|

Source | Kanpur 2009 |

Short link | https://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.