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:

TR20-127 | 21st August 2020
Nikhil Bansal, Makrand Sinha

$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity

Revisions: 2

Aaronson and Ambainis (SICOMP '18) showed that any partial function on $N$ bits that can be computed with an advantage $\delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $\delta/2$ by a randomized decision tree making ${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured ... more >>>

TR18-204 | 30th November 2018
Makrand Sinha, Ronald de Wolf

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Comments: 1

Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total
Boolean function, the sink function, that has polynomial approximate rank and
polynomial randomized communication complexity. This gives an exponential
separation between randomized communication complexity and logarithm of the
approximate rank, refuting the log-approximate-rank conjecture. We show that ... more >>>

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