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

__
TR18-204
| 30th November 2018
__

Makrand Sinha, Ronald de Wolf#### Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Comments: 1

__
TR17-185
| 28th November 2017
__

Makrand Sinha#### Lower Bounds for Approximating the Matching Polytope

__
TR15-057
| 13th April 2015
__

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

Revisions: 3

__
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

Nikhil Bansal, Makrand Sinha

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

Makrand Sinha, Ronald de Wolf

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

Makrand Sinha

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

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