Makrand Sinha

activity

20122023

most citedQuantum Cryptography in Algorithmica

50 citations · 56 across the 9 of their papers we have counts for

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2023

Fourier Growth of Communication Protocols for XOR Functions

Uma Girish, Makrand Sinha, Avishay Tal +1

The level- $k$ $ℓ_{1}$ -Fourier weight of a Boolean function refers to the sum of absolute values of its level- $k$ Fourier coefficients. Fourier growth refers to the growth of these…

cs.CC2017

Lower Bounds for Approximating the Matching Polytope

Makrand Sinha

We prove that any extended formulation that approximates the matching polytope on $n$ -vertex graphs up to a factor of $(1 + ε)$ for any $\frac{2}{n} \leq ε \leq 1$ must…