Difference between revisions of "Open Problems:19"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (1 revision)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 19: Sketching vs. Streaming}}
+
{{Header
{{Infobox
+
|title=Sketching vs. Streaming
|label1 = Proposed by
+
|source=kanpur06
|data1 = D. Sivakumar
+
|who=D. Sivakumar
|label2 = Source
 
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
 
|label3 = Short link
 
|data3 = http://sublinear.info/19
 
 
}}
 
}}
 
Show that any symmetric function that admits a good streaming algorithm also admits a sketching algorithm. In terms of communication complexity, consider trying to evaluate a symmetric function $f(x,y)$ in each of the following models:
 
Show that any symmetric function that admits a good streaming algorithm also admits a sketching algorithm. In terms of communication complexity, consider trying to evaluate a symmetric function $f(x,y)$ in each of the following models:

Revision as of 05:12, 16 November 2012

Suggested by D. Sivakumar
Source Kanpur 2006
Short link https://sublinear.info/19

Show that any symmetric function that admits a good streaming algorithm also admits a sketching algorithm. In terms of communication complexity, consider trying to evaluate a symmetric function $f(x,y)$ in each of the following models:

  1. One-Way Communication: The player knowing $x$ sends a single message to the player knowing $y$ who then has to compute $f(x,y)$.
  2. Simultaneous Communication: Both players send a message simultaneously to a third party who then has to compute $f(x,y)$.

Obviously any function that can be evaluated with $B$ bits of communication in the simultaneous model can be evaluated in the one-way model with $B$ bits of communication. Are there natural functions that require significantly more communication in the simultaneous model than in the one-way model? It is known that any total, permutation-invariant function that can be computed in the one-way model can be computed in the simultaneous model. See [FeldmanMSSS-06] for further details.