Difference between revisions of "Open Problems:19"
(Created page with "{{DISPLAYTITLE:Problem 19: Sketching vs. Streaming}} {{Infobox |label1 = Proposed by |data1 = D. Sivakumar |label2 = Source |data2 = Kanpur 2006 |lab...") |
|||
| (3 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |source=kanpur06 | |
| − | | | + | |who=D. Sivakumar |
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
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 12: | Line 7: | ||
#''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 but cannot be computed in the simultaneous model. See {{cite|FeldmanMSSS-06}} for further details. |
Latest revision as of 05:21, 27 June 2022
| 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:
- One-Way Communication: The player knowing $x$ sends a single message to the player knowing $y$ 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 but cannot be computed in the simultaneous model. See [FeldmanMSSS-06] for further details.
