Sushant Sachdeva

According to our database, Sushant Sachdeva authored at least 65 papers between 2011 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Fast Algorithms for <i>ℓ_p</i>-Regression.

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

J. ACM, October, 2024

Eulerian Graph Sparsification by Effective Resistance Decomposition.

Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, Yibin Zhao

CoRR, 2024

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality.

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva

CoRR, 2024

Fast Algorithms for Separable Linear Programs.

Sally Dong, Gramoz Goranci, Lawrence Li, Sushant Sachdeva, Guanghao Ye

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Electrical Flows for Polylogarithmic Competitive Oblivious Routing.

Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra.

Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Better Sparsifiers for Directed Eulerian Graphs.

Sushant Sachdeva, Anvith Thudi, Yibin Zhao

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Optimal Electrical Oblivious Routing on Expanders.

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions.

Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang

SIAM J. Comput., December, 2023

Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow.

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Commun. ACM, December, 2023

A Simple and Efficient Parallel Laplacian Solver.

Sushant Sachdeva, Yibin Zhao

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

A Simple Framework for Finding Balanced Sparse Cuts via APSP.

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs.

Lawrence Li, Sushant Sachdeva

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.

Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Fast Algorithms for 𝓁_p-Regression.

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

CoRR, 2022

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities.

Deeksha Adil, Brian Bullins, Arun Jambulapati, Sushant Sachdeva

CoRR, 2022

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time.

Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Guanghao Ye

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A Convergent and Dimension-Independent Min-Max Optimization Algorithm.

Vijay Keswani, Oren Mangoubi, Sushant Sachdeva, Nisheeth K. Vishnoi

Proceedings of the International Conference on Machine Learning, 2022

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization.

Deeksha Adil, Brian Bullins, Sushant Sachdeva

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Almost-Linear-Time Weighted 𝓁_p-Norm Solvers in Slightly Dense Graphs via Sparsification.

Deeksha Adil, Brian Bullins, Rasmus Kyng, Sushant Sachdeva

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

A Provably Convergent and Practical Algorithm for Min-max Optimization with Applications to GANs.

Oren Mangoubi, Sushant Sachdeva, Nisheeth K. Vishnoi

CoRR, 2020

Faster <i>p</i>-norm minimizing flows, via smoothed <i>q</i>-norm problems.

Deeksha Adil, Sushant Sachdeva

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Regularized linear autoencoders recover the principal components, eventually.

Xuchan Bao, James Lucas, Sushant Sachdeva, Roger B. Grosse

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Faster Graph Embeddings via Coarsening.

Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, Chi Wang

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

Faster p-norm minimizing flows, via smoothed q-norm problems.

Deeksha Adil, Sushant Sachdeva

CoRR, 2019

Iterative Refinement for 𝓁_p-norm Regression.

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

CoRR, 2019

Flows in almost linear time via adaptive preconditioning.

Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Short Cycles via Low-Diameter Decompositions.

Yang P. Liu, Sushant Sachdeva, Zejun Yu

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Iterative Refinement for ℓp-norm Regression.

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model.

Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E. Dahl, Christopher J. Shallue, Roger B. Grosse

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression.

Deeksha Adil, Richard Peng, Sushant Sachdeva

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Improved Semi-Supervised Learning with Multiple Graphs.

Krishnamurthy Viswanathan, Sushant Sachdeva, Andrew Tomkins, Sujith Ravi

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Near-optimal approximation algorithm for simultaneous Max-Cut.

Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Convergence Results for Neural Networks via Electrodynamics.

Rina Panigrahy, Ali Rahimi, Sushant Sachdeva, Qiuyi Zhang

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Electron-Proton Dynamics in Deep Learning.

Qiuyi Zhang, Rina Panigrahy, Sushant Sachdeva

CoRR, 2017

Sampling random spanning trees faster than matrix multiplication.

David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A Framework for Analyzing Resparsification Algorithms.

Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

The mixing time of the Dikin walk in a polytope - A simple proof.

Sushant Sachdeva, Nisheeth K. Vishnoi

Oper. Res. Lett., 2016

Sparsified Cholesky and multigrid solvers for connection laplacians.

Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple.

Rasmus Kyng, Sushant Sachdeva

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

A Simple Analysis of the Dikin Walk.

Sushant Sachdeva, Nisheeth K. Vishnoi

CoRR, 2015

Fast, Provable Algorithms for Isotonic Regression in all ℓ_p-norms.

Rasmus Kyng, Anup Rao, Sushant Sachdeva

CoRR, 2015

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders.

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

Algorithmica, 2015

Fast, Provable Algorithms for Isotonic Regression in all L_p-norms.

Rasmus Kyng, Anup Rao, Sushant Sachdeva

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Algorithms for Lipschitz Learning on Graphs.

Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Faster Algorithms via Approximation Theory.

Sushant Sachdeva, Nisheeth K. Vishnoi

Found. Trends Theor. Comput. Sci., 2014

Simultaneous Approximation of Constraint Satisfaction Problems.

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Electron. Colloquium Comput. Complex., 2014

Greedy Geometric Algorithms for Collection of Balls, with Applications to Geometric Approximation and Molecular Coarse-Graining.

Frédéric Cazals, Tom Dreyfus, Sushant Sachdeva, N. Shah

Comput. Graph. Forum, 2014

2013

New Results in the Theory of Approximation: Fast Graph Algorithms and Inapproximability

Sushant Sachdeva

PhD thesis, 2013

Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs.

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

Electron. Colloquium Comput. Complex., 2013

Matrix Inversion Is As Easy As Exponentiation

Sushant Sachdeva, Nisheeth K. Vishnoi

CoRR, 2013

An Arithmetic Analogue of Fox's Triangle Removal Argument

Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani

CoRR, 2013

Approximation Theory and the Design of Fast Algorithms.

Sushant Sachdeva, Nisheeth K. Vishnoi

CoRR, 2013

Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover.

Sushant Sachdeva, Rishi Saket

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Testing Permanent Oracles - Revisited.

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Electron. Colloquium Comput. Complex., 2012

Approximating the exponential, the lanczos method and an Õ(<i>m</i>)-time spectral algorithm for balanced separator.

Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Finding overlapping communities in social networks: toward a rigorous approach.

Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

"Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders".

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012

2011

On the Characterization and Selection of Diverse Conformational Ensembles with Applications to Flexible Docking.

Sébastien Loriot, Sushant Sachdeva, Karine Bastard, Chantal Prévost, Frédéric Cazals

IEEE ACM Trans. Comput. Biol. Bioinform., 2011

Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi

CoRR, 2011

Cuts in Cartesian Products of Graphs

Sushant Sachdeva, Madhur Tulsiani

CoRR, 2011

A Reformulation of the Arora-Rao-Vazirani Structure Theorem

Sanjeev Arora, James R. Lee, Sushant Sachdeva

CoRR, 2011

Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs.

Sushant Sachdeva, Rishi Saket

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011