3 papers
cs.DS2012
Testing Permanent Oracles -- Revisited
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran +1
Suppose we are given an oracle that claims to approximate the permanent for most matrices X, where X is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate…
cs.CC2011
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
Sushant Sachdeva, Rishi Saket
We study the problem of computing the minimum vertex cover on k-uniform k-partite hypergraphs when the k-partition is given. On bipartite graphs (k = 2), the minimum vertex cover c…
cs.DM2011
A Reformulation of the Arora-Rao-Vazirani Structure Theorem
Sanjeev Arora, James Lee, Sushant Sachdeva
In a well-known paper[ARV], Arora, Rao and Vazirani obtained an O(sqrt(log n)) approximation to the Balanced Separator problem and Uniform Sparsest Cut. At the heart of their resul…