Makrand Sinha

activity

20122023

most citedQuantum Cryptography in Algorithmica

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

collaborators

Showing 2017Show all

2 papers · 1 filter

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…

cs.DS2017

Edge Estimation with Independent Set Oracles

Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy +2

We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have ap…