All reports by Author Makrand Sinha:

__
TR15-057
| 13th April 2015
__

Anup Rao, Makrand Sinha#### Simplified Separation of Information and Communication

Revisions: 2

__
TR15-039
| 16th March 2015
__

Anup Rao, Makrand Sinha#### On Parallelizing Streaming Algorithms

__
TR14-022
| 19th February 2014
__

Shay Moran, Makrand Sinha, Amir Yehudayoff#### Fooling Pairs in Randomized Communication Complexity

Revisions: 1

Anup Rao, Makrand Sinha

We give an example of a boolean function whose information complexity is exponentially

smaller than its communication complexity. Our result simplifies recent work of Ganor, Kol and

Raz (FOCS'14, STOC'15).

Anup Rao, Makrand Sinha

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If $M(f)$ denotes the minimum average memory required to compute a function $f(x_1,x_2, \dots, x_n)$ how much memory is required to compute $f$ on $k$ independent streams that arrive in parallel? We show that when the inputs (updates) ... more >>>

Shay Moran, Makrand Sinha, Amir Yehudayoff

Fooling pairs are one of the standard methods for proving lower bounds for deterministic two-player communication complexity. We study fooling pairs in the context of randomized communication complexity.

We show that every fooling pair induces far away distributions on transcripts of private-coin protocols. We then conclude that the private-coin randomized ...
more >>>