Open Problems:8 - Revision history

Krzysztof Onak at 01:39, 7 March 2013

2013-03-07T01:39:14Z

Krzysztof Onak at 05:01, 16 November 2012

2012-11-16T05:01:14Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 8: Mixed Norms}} {{Infobox |label1 = Proposed by |data1 = Piotr Indyk |label2 = Source |data2 = Kanpur 2006 |label3 = Short li..."

2012-10-01T09:45:45Z

Created page with "{{DISPLAYTITLE:Problem 8: Mixed Norms}} {{Infobox |label1 = Proposed by |data1 = Piotr Indyk |label2 = Source |data2 = Kanpur 2006 |label3 = Short li..."

New page

{{DISPLAYTITLE:Problem 8: Mixed Norms}}
{{Infobox
|label1 = Proposed by
|data1 = Piotr Indyk
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/8
}}
For any vector $x$, let $\|x\|_0$ be a norm-like function computing the number
of non-zero elements in $x$.
Consider the following norm-like function $\|\cdot\|_{2,0}$ over $n \times n$
matrices $A = [a_1 \ldots a_n]$:
\[ \|A\|_{2,0} = \left ( \sum_{i=1}^n (\|a_i\|_0)^2 \right )^{1/2}. \]

Assume we are given a stream of $m$ updates $(i,j,\delta)$ to $A$, interpreted
as $A[i,j]:=A[i,j]+\delta$, starting from $A=0$.
What is the smallest space needed by a streaming algorithm estimating
$\|A\|_{2,0}$ up to a factor of $1 \pm \epsilon$?
An upper bound of $O(\operatorname{poly}(\epsilon^{-1})\cdot\sqrt{n}\cdot\operatorname{polylog}(n))$ is known as long
as $A \ge 0$ {{cite|CormodeM-05b}}. There are no non-trivial lower bounds known.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Piotr Indyk

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 8: Mixed Norms}}
+{{Header
-{{Infobox
+|title=Mixed Norms
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Piotr Indyk
+|who=Piotr Indyk
 }}
 For any vector $x$, let $\|x\|_0$ be a norm-like function computing the number

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)