Sushant Sachdeva

109 papers A* 31A 5B 1Journal 65Unranked 6

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