Sushant Sachdeva

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 65

Top Topics

Linear Regression

Provably Convergent

Top Venues

Publications

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
Optimal Electrical Oblivious Routing on Expanders. ICALP (2024)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality. CoRR (2024)
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. ITCS (2024)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. SODA (2024)
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
Optimal Electrical Oblivious Routing on Expanders. CoRR (2024)
Sushant Sachdeva, Anvith Thudi, Yibin Zhao
Better Sparsifiers for Directed Eulerian Graphs. ICALP (2024)
Sally Dong, Gramoz Goranci, Lawrence Li, Sushant Sachdeva, Guanghao Ye
Fast Algorithms for Separable Linear Programs. SODA (2024)
Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan
Electrical Flows for Polylogarithmic Competitive Oblivious Routing. ITCS (2024)
Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan
Electrical Flows for Polylogarithmic Competitive Oblivious Routing. CoRR (2023)
Sushant Sachdeva, Anvith Thudi, Yibin Zhao
Better Sparsifiers for Directed Eulerian Graphs. CoRR (2023)
Sushant Sachdeva, Yibin Zhao
A Simple and Efficient Parallel Laplacian Solver. SPAA (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. CoRR (2023)
Sushant Sachdeva, Yibin Zhao
A Simple and Efficient Parallel Laplacian Solver. CoRR (2023)
Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions. SIAM J. Comput. 52 (6) (2023)
Jan Van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. FOCS (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. CoRR (2023)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow. Commun. ACM 66 (12) (2023)
Sally Dong, Gramoz Goranci, Lawrence Li, Sushant Sachdeva, Guanghao Ye
Fast Algorithms for Separable Linear Programs. CoRR (2023)
Lawrence Li, Sushant Sachdeva
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs. SODA (2023)
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
A Simple Framework for Finding Balanced Sparse Cuts via APSP. SOSA (2023)
Lawrence Li, Sushant Sachdeva
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs. CoRR (2022)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. FOCS (2022)
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
A Simple Framework for Finding Balanced Sparse Cuts via APSP. CoRR (2022)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. CoRR (2022)
Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva
-Regression. CoRR (2022)
Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Guanghao Ye
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time. CoRR (2022)
Vijay Keswani, Oren Mangoubi, Sushant Sachdeva, Nisheeth K. Vishnoi
A Convergent and Dimension-Independent Min-Max Optimization Algorithm. ICML (2022)
Deeksha Adil, Brian Bullins, Arun Jambulapati, Sushant Sachdeva
Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities. CoRR (2022)
Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Guanghao Ye
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time. SODA (2022)
Deeksha Adil, Brian Bullins, Sushant Sachdeva
Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization. CoRR (2021)
Deeksha Adil, Brian Bullins, Rasmus Kyng, Sushant Sachdeva
-norm Solvers in Slightly Dense Graphs via Sparsification. CoRR (2021)
Deeksha Adil, Brian Bullins, Sushant Sachdeva
Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization. NeurIPS (2021)
Deeksha Adil, Brian Bullins, Rasmus Kyng, Sushant Sachdeva
-Norm Solvers in Slightly Dense Graphs via Sparsification. ICALP (2021)
Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, Chi Wang
Faster Graph Embeddings via Coarsening. ICML (2020)
Oren Mangoubi, Sushant Sachdeva, Nisheeth K. Vishnoi
A Provably Convergent and Practical Algorithm for Min-max Optimization with Applications to GANs. CoRR (2020)
Deeksha Adil, Sushant Sachdeva
-norm problems. SODA (2020)
Xuchan Bao, James Lucas, Sushant Sachdeva, Roger B. Grosse
Regularized linear autoencoders recover the principal components, eventually. CoRR (2020)
Xuchan Bao, James Lucas, Sushant Sachdeva, Roger B. Grosse
Regularized linear autoencoders recover the principal components, eventually. NeurIPS (2020)
Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, Chi Wang
Faster Graph Embeddings via Coarsening. CoRR (2020)
Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva
Iterative Refinement for ℓp-norm Regression. SODA (2019)
Krishnamurthy Viswanathan, Sushant Sachdeva, Andrew Tomkins, Sujith Ravi
Improved Semi-Supervised Learning with Multiple Graphs. AISTATS (2019)
Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang
Flows in almost linear time via adaptive preconditioning. STOC (2019)
Deeksha Adil, Richard Peng, Sushant Sachdeva
Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression. NeurIPS (2019)
Deeksha Adil, Richard Peng, Sushant Sachdeva
Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression. CoRR (2019)
Yang P. Liu, Sushant Sachdeva, Zejun Yu
Short Cycles via Low-Diameter Decompositions. SODA (2019)
Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang
Flows in Almost Linear Time via Adaptive Preconditioning. CoRR (2019)
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E. Dahl, Christopher J. Shallue, Roger B. Grosse
Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model. NeurIPS (2019)
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E. Dahl, Christopher J. Shallue, Roger B. Grosse
Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model. CoRR (2019)
Deeksha Adil, Sushant Sachdeva
Faster p-norm minimizing flows, via smoothed q-norm problems. CoRR (2019)
Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva
-norm Regression. CoRR (2019)
Rina Panigrahy, Ali Rahimi, Sushant Sachdeva, Qiuyi Zhang
Convergence Results for Neural Networks via Electrodynamics. ITCS (2018)
Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions. FOCS (2018)
Yang P. Liu, Sushant Sachdeva, Zejun Yu
Short Cycles via Low-Diameter Decompositions. CoRR (2018)
Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari
Near-optimal approximation algorithm for simultaneous Max-Cut. CoRR (2018)
Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions. CoRR (2018)
Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari
Near-optimal approximation algorithm for simultaneous Max-Cut. SODA (2018)
Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva
A Framework for Analyzing Resparsification Algorithms. SODA (2017)
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva
Sampling random spanning trees faster than matrix multiplication. STOC (2017)
Qiuyi Zhang, Rina Panigrahy, Sushant Sachdeva
Electron-Proton Dynamics in Deep Learning. CoRR (2017)
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva
Sampling Random Spanning Trees Faster than Matrix Multiplication. CoRR (2016)
Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva
A Framework for Analyzing Resparsification Algorithms. CoRR (2016)
Rasmus Kyng, Sushant Sachdeva
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple. CoRR (2016)
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman
Sparsified Cholesky and multigrid solvers for connection laplacians. STOC (2016)
Rasmus Kyng, Sushant Sachdeva
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. FOCS (2016)
Sushant Sachdeva, Nisheeth K. Vishnoi
The mixing time of the Dikin walk in a polytope - A simple proof. Oper. Res. Lett. 44 (5) (2016)
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket
Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs. SIAM J. Discret. Math. 29 (1) (2015)
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians. CoRR (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman
Algorithms for Lipschitz Learning on Graphs. CoRR (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva
-norms. CoRR (2015)
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva
Simultaneous Approximation of Constraint Satisfaction Problems. ICALP (1) (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva
Fast, Provable Algorithms for Isotonic Regression in all L_p-norms. NIPS (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman
Algorithms for Lipschitz Learning on Graphs. COLT (2015)
Sushant Sachdeva, Nisheeth K. Vishnoi
A Simple Analysis of the Dikin Walk. CoRR (2015)
Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. Algorithmica 72 (1) (2015)
Sushant Sachdeva, Nisheeth K. Vishnoi
Faster Algorithms via Approximation Theory. Found. Trends Theor. Comput. Sci. 9 (2) (2014)
Frédéric Cazals, Tom Dreyfus, Sushant Sachdeva, N. Shah
Greedy Geometric Algorithms for Collection of Balls, with Applications to Geometric Approximation and Molecular Coarse-Graining. Comput. Graph. Forum 33 (6) (2014)
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva
Simultaneous Approximation of Constraint Satisfaction Problems. CoRR (2014)
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva
Simultaneous Approximation of Constraint Satisfaction Problems. Electron. Colloquium Comput. Complex. 21 (2014)
Sushant Sachdeva, Nisheeth K. Vishnoi
Approximation Theory and the Design of Fast Algorithms. CoRR (2013)
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket
Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs. Electron. Colloquium Comput. Complex. 20 (2013)
Sushant Sachdeva, Nisheeth K. Vishnoi
Matrix Inversion Is As Easy As Exponentiation CoRR (2013)
Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani
An Arithmetic Analogue of Fox's Triangle Removal Argument CoRR (2013)
Sushant Sachdeva, Rishi Saket
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. Computational Complexity Conference (2013)
Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck
Finding overlapping communities in social networks: toward a rigorous approach. EC (2012)
Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders CoRR (2012)
Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva
"Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders". NIPS (2012)
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva
Testing Permanent Oracles -- Revisited CoRR (2012)
Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi
)-time spectral algorithm for balanced separator. STOC (2012)
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva
Testing Permanent Oracles - Revisited. APPROX-RANDOM (2012)
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva
Testing Permanent Oracles - Revisited. Electron. Colloquium Comput. Complex. 19 (2012)
Sushant Sachdeva, Madhur Tulsiani
Cuts in Cartesian Products of Graphs CoRR (2011)
Sébastien Loriot, Sushant Sachdeva, Karine Bastard, Chantal Prévost, Frédéric Cazals
On the Characterization and Selection of Diverse Conformational Ensembles with Applications to Flexible Docking. IEEE ACM Trans. Comput. Biol. Bioinform. 8 (2) (2011)
Sushant Sachdeva, Rishi Saket
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs CoRR (2011)
Sushant Sachdeva, Rishi Saket
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs. APPROX-RANDOM (2011)
Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck
Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach CoRR (2011)
Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi
Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator CoRR (2011)
Sanjeev Arora, James R. Lee, Sushant Sachdeva
A Reformulation of the Arora-Rao-Vazirani Structure Theorem CoRR (2011)