Krzysztof Onak: updated header

2013-03-07T01:51:08Z

updated header

Krzysztof Onak at 05:25, 16 November 2012

2012-11-16T05:25:09Z

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 30: Universal Sketching}} {{Infobox |label1 = Proposed by |data1 = Jelani Nelson |label2 = Source |data2 = Kanpur 2009 |label3..."

2012-11-13T01:02:27Z

Created page with "{{DISPLAYTITLE:Problem 30: Universal Sketching}} {{Infobox |label1 = Proposed by |data1 = Jelani Nelson |label2 = Source |data2 = Kanpur 2009 |label3..."

New page

{{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.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Jelani Nelson

@@ 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
 }}
 Rather than designing different sketching algorithms for every

Open Problems:30 - Revision history

Krzysztof Onak: updated header

Krzysztof Onak at 05:25, 16 November 2012

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 30: Universal Sketching}} {{Infobox |label1 = Proposed by |data1 = Jelani Nelson |label2 = Source |data2 = Kanpur 2009 |label3..."