Difference between revisions of "Open Problems:8"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (1 revision)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 8: Mixed Norms}}
+
{{Header
{{Infobox
+
|source=kanpur06
|label1 = Proposed by
+
|who=Piotr Indyk
|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
 
For any vector $x$, let $\|x\|_0$ be a norm-like function computing the number

Latest revision as of 01:39, 7 March 2013

Suggested by Piotr Indyk
Source Kanpur 2006
Short link https://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$ [CormodeM-05b]. There are no non-trivial lower bounds known.