# Problem 19: Sketching vs. Streaming

From Open Problems in Sublinear Algorithms

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 can be computed in the simultaneous model. See [FeldmanMSSS-06] for further details.