Difference between revisions of "Open Problems:30"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{DISPLAYTITLE:Problem 30: Universal Sketching}} {{Infobox |label1 = Proposed by |data1 = Jelani Nelson |label2 = Source |data2 = Kanpur 2009 |label3...")
 
Line 1: Line 1:
{{DISPLAYTITLE:Problem 30: Universal Sketching}}
+
{{Header
{{Infobox
+
|title=Universal Sketching
|label1 = Proposed by
+
|source=kanpur09
|data1 = Jelani Nelson
+
|who=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
 
Rather than designing different sketching algorithms for every

Revision as of 05:25, 16 November 2012

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.