24 citations · 151 across the 43 of their papers we have counts for
5 papers · 1 filter
Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach
Sanjeev Arora, Rong Ge, Sushant Sachdeva +1
A "community" in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is an important concep…
Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator
Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi
We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter γ, either finds an Ω(b)…
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…
Cuts in Cartesian Products of Graphs
Sushant Sachdeva, Madhur Tulsiani
The k-fold Cartesian product of a graph G is defined as a graph on k-tuples of vertices, where two tuples are connected if they form an edge in one of the positions and are equal i…
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…