Publications (21)
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
Rasmus Kyng, Sushant Sachdeva
Convergence Results for Neural Networks via Electrodynamics
Rina Panigrahy, Sushant Sachdeva, Qiuyi Zhang
Fast, Provable Algorithms for Isotonic Regression in all $\ell_{p}$-norms
Rasmus Kyng, Anup Rao, Sushant Sachdeva
Algorithms for Lipschitz Learning on Graphs
Rasmus Kyng, Anup Rao, Sushant Sachdeva +1
Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach
Sanjeev Arora, Rong Ge, Sushant Sachdeva +1
Sampling Random Spanning Trees Faster than Matrix Multiplication
David Durfee, Rasmus Kyng, John Peebles +2
Cuts in Cartesian Products of Graphs
Sushant Sachdeva, Madhur Tulsiani
A Reformulation of the Arora-Rao-Vazirani Structure Theorem
Sanjeev Arora, James Lee, Sushant Sachdeva
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, Richard Peng +3
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
Sushant Sachdeva, Rishi Saket
Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva +1
An Arithmetic Analogue of Fox's Triangle Removal Argument
Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani
Testing Permanent Oracles -- Revisited
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran +1
The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof
Sushant Sachdeva, Nisheeth K. Vishnoi
Simultaneous Approximation of Constraint Satisfaction Problems
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva
Short Cycles via Low-Diameter Decompositions
Yang P. Liu, Sushant Sachdeva, Zejun Yu
Near-optimal approximation algorithm for simultaneous Max-Cut
Amey Bhangale, Subhash Khot, Swastik Kopparty +2
A Framework for Analyzing Resparsification Algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng +1
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
Sanjeev Arora, Rong Ge, Ankur Moitra +1
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng +2
Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator
Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi