Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Makrand Sinha:

TR17-185 | 28th November 2017
Makrand Sinha

Lower Bounds for Approximating the Matching Polytope

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\varepsilon)$ for any $\frac2n \le \varepsilon \le 1$ must have at least ${n}\choose{{\alpha}/{\varepsilon}}$ defining inequalities where $0<\alpha<1$ is an absolute constant. This is tight as exhibited by the $(1+\varepsilon)$ approximating linear ... more >>>

TR15-057 | 13th April 2015
Anup Rao, Makrand Sinha

Simplified Separation of Information and Communication

Revisions: 3

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).

more >>>

TR15-039 | 16th March 2015
Anup Rao, Makrand Sinha

On Parallelizing Streaming Algorithms

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 >>>

TR14-022 | 19th February 2014
Shay Moran, Makrand Sinha, Amir Yehudayoff

Fooling Pairs in Randomized Communication Complexity

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint