Editing Open Problems:19
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | {{ | + | {{DISPLAYTITLE:Problem 19: Sketching vs. Streaming}} |
− | | | + | {{Infobox |
− | | | + | |label1 = Proposed by |
+ | |data1 = 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: | ||
Line 7: | Line 12: | ||
#''Simultaneous Communication:'' Both players send a message simultaneously to a third party who then has to compute $f(x,y)$. | #''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 | + | 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 {{cite|FeldmanMSSS-06}} for further details. |