Sushant Sachdeva

Matrix Inversion Is As Easy As Exponentiation

Sushant Sachdeva, Nisheeth K. Vishnoi

We prove that the inverse of a positive-definite matrix can be approximated by a weighted-sum of a small number of matrix exponentials. Combining this with a previous result [OSV12…

Eulerian Graph Sparsification by Effective Resistance Decomposition

Arun Jambulapati, Sushant Sachdeva, Aaron Sidford +2

We provide an algorithm that, given an $n$ -vertex $m$ -edge Eulerian graph with polynomially bounded weights, computes an $O ˘ (n lo g^{2} n \cdot ε^{- 2})$ -edge $\vare…

Electrical Flows for Polylogarithmic Competitive Oblivious Routing

Gramoz Goranci, Monika Henzinger, Harald RÃ¤cke +2

Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polyl…

cs.DM2011

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…

cs.CC2011

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…

cs.DS2019

Flows in Almost Linear Time via Adaptive Preconditioning

Rasmus Kyng, Richard Peng, Sushant Sachdeva +1

We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to $(1 + 1/ p o l y (n))$ accuracy in almost-linear time. These problems includ…

math.CO2016

An Arithmetic Analogue of Fox's Triangle Removal Argument

Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani

We give an arithmetic version of the recent proof of the triangle removal lemma by Fox [Fox11], for the group $F_{2}^{n}$ . A triangle in $F_{2}^{n}$ is a triple $(x, y, z)$ …

A Simple Framework for Finding Balanced Sparse Cuts via APSP

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg +1

We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solvi…

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

Sally Dong, Yu Gao, Gramoz Goranci +4

We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm fo…

cs.DS2012

Testing Permanent Oracles -- Revisited

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran +1

Suppose we are given an oracle that claims to approximate the permanent for most matrices X, where X is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate…

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

Jan van den Brand, Li Chen, Rasmus Kyng +4

We give the first almost-linear total time algorithm for deciding if a flow of cost at most $F$ still exists in a directed graph, with edge costs and capacities, undergoing decreme…

cs.LG2022

A Convergent and Dimension-Independent Min-Max Optimization Algorithm

Vijay Keswani, Oren Mangoubi, Sushant Sachdeva +1

We study a variant of a recently introduced min-max optimization framework where the max-player is constrained to update its parameters in a greedy manner until it reaches a first-…

cs.DS2019

Short Cycles via Low-Diameter Decompositions

Yang P. Liu, Sushant Sachdeva, Zejun Yu

We present improved algorithms for short cycle decomposition of a graph. Short cycle decompositions were introduced in the recent work of Chu et al, and were used to make progress…

A Framework for Analyzing Resparsification Algorithms

Rasmus Kyng, Jakub Pachocki, Richard Peng +1

A spectral sparsifier of a graph $G$ is a sparser graph $H$ that approximately preserves the quadratic form of $G$ , i.e. for all vectors $x$ , $x^{T} L_{G} x \approx x^{T} L_{H} x$ , where $…

cs.LG2012

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

Sanjeev Arora, Rong Ge, Ankur Moitra +1

We present a new algorithm for Independent Component Analysis (ICA) which has provable performance guarantees. In particular, suppose we are given samples of the form $y = A x + I^\cdot$ …

cs.DS2018

Convergence Results for Neural Networks via Electrodynamics

Rina Panigrahy, Sushant Sachdeva, Qiuyi Zhang

We study whether a depth two neural network can learn another depth two network using gradient descent. Assuming a linear output node, we show that the question of whether gradient…

cs.DS2013

Approximation Theory and the Design of Fast Algorithms

Sushant Sachdeva, Nisheeth Vishnoi

We survey key techniques and results from approximation theory in the context of uniform approximations to real functions such as e^{-x}, 1/x, and x^k. We then present a selection…

cs.LG2015

Algorithms for Lipschitz Learning on Graphs

Rasmus Kyng, Anup Rao, Sushant Sachdeva +1

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to…

cs.SI2011

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…

cs.DS2017

Sampling Random Spanning Trees Faster than Matrix Multiplication

David Durfee, Rasmus Kyng, John Peebles +2

We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in $O ~ (n^{4/3} m^{1/2} + n^{2})$ time (The $\tilde{…

cs.DM2013

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…

Optimal Electrical Oblivious Routing on Expanders

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg +1

In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an $m$ -edge graph $G = (V, E)$ that is a $I^¦$ -expander, i.e.…

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

Jan van den Brand, Li Chen, Rasmus Kyng +5

We provide an algorithm which, with high probability, maintains a $(1 - I^µ)$ -approximate maximum flow on an undirected graph undergoing $m$ -edge additions in amortized $m^{o(1)} Îµ^{…

math.OC2022

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

Deeksha Adil, Brian Bullins, Arun Jambulapati +1

In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for $p^{t h}$ -order smooth, monotone operators -- a problem that gener…

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

Jan van den Brand, Li Chen, Rasmus Kyng +5

We give a deterministic $m^{1 + o (1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral dem…

cs.DS2018

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

Timothy Chu, Yu Gao, Richard Peng +3

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…

cs.LG2019

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

Guodong Zhang, Lala Li, Zachary Nado +5

Increasing the batch size is a popular way to speed up neural network training, but beyond some critical batch size, larger batch sizes yield diminishing returns. In this work, we…

Better Sparsifiers for Directed Eulerian Graphs

Sushant Sachdeva, Anvith Thudi, Yibin Zhao

Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems. Directed Laplacian linear sy…

cs.DS2026

A Tight Bound on Localization of Electrical Flows

Ori Gurel-Gurevich, Asaf Nachmias, Sushant Sachdeva

We prove that for any unweighted graph on n vertices the L1 norm of a unit electric current between the endpoints of a random edge is at most 2 log n. Furthermore, we show that on…

Fast Algorithms for $ℓ_{p}$ -Regression

Deeksha Adil, Rasmus Kyng, Richard Peng +1

The $ℓ_{p}$ -norm regression problem is a classic problem in optimization with wide ranging applications in machine learning and theoretical computer science. The goal is to comput…

The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof

Sushant Sachdeva, Nisheeth K. Vishnoi

We study the mixing time of the Dikin walk in a polytope - a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were st…

cs.DS2014

Simultaneous Approximation of Constraint Satisfaction Problems

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Given $k$ collections of 2SAT clauses on the same set of variables $V$ , can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such…

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

Lawrence Li, Sushant Sachdeva

We demonstrate that for expander graphs, for all $I^µ > 0,$ there exists a data structure of size $O (n I^µ^{- 1})$ which can be used to return $(1 + I^µ)$ -approximations to e…

cs.LG2020

Faster Graph Embeddings via Coarsening

Matthew Fahrbach, Gramoz Goranci, Richard Peng +2

Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for…

cs.LG2021

Regularized linear autoencoders recover the principal components, eventually

Xuchan Bao, James Lucas, Sushant Sachdeva +1

Our understanding of learning input-output relationships with neural nets has improved rapidly in recent years, but little is known about the convergence of the underlying represen…

cs.DS2020

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

Deeksha Adil, Sushant Sachdeva

We present faster high-accuracy algorithms for computing $ℓ_{p}$ -norm minimizing flows. On a graph with $m$ edges, our algorithm can compute a $(1 + 1/ poly (m))$ -approximate u…

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

Li Chen, Rasmus Kyng, Yang P. Liu +3

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities in…

math.OC2021

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

Deeksha Adil, Brian Bullins, Sushant Sachdeva

We provide several algorithms for constrained optimization of a large class of convex problems, including softmax, $ℓ_{p}$ regression, and logistic regression. Central to our appr…

cs.DS2020

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

Deeksha Adil, Richard Peng, Sushant Sachdeva

Linear regression in $ℓ_{p}$ -norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processi…

cs.CC2018

Near-optimal approximation algorithm for simultaneous Max-Cut

Amey Bhangale, Subhash Khot, Swastik Kopparty +2

In the simultaneous Max-Cut problem, we are given $k$ weighted graphs on the same set of $n$ vertices, and the goal is to find a cut of the vertex set so that the minimum, over the…

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra

Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco +3

Let $S \in R^{n \times n}$ satisfy $∥ 1 - S ∥_{2} \leq I^µ n$ , where $1$ is the all ones matrix and $∥ \cdot ∥_{2}$ is the spectral norm. It is well-kn…

cs.DS2015

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

Rasmus Kyng, Yin Tat Lee, Richard Peng +2

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying th…

A Simple and Efficient Parallel Laplacian Solver

Sushant Sachdeva, Yibin Zhao

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linea…

cs.DS2011

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 Î©(…

cs.DS2021

Almost-linear-time Weighted $ℓ_{p}$ -norm Solvers in Slightly Dense Graphs via Sparsification

Deeksha Adil, Brian Bullins, Rasmus Kyng +1

We give almost-linear-time algorithms for constructing sparsifiers with $n p o l y (lo g n)$ edges that approximately preserve weighted $(ℓ_{2}^{2} + ℓ_{p}^{p})$ flow or voltage obj…

cs.LG2025

PREM: Privately Answering Statistical Queries with Relative Error

Badih Ghazi, CristÃ³bal GuzmÃ¡n, Pritish Kamath +4

We introduce $PREM$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that achieves a relative error guarantee for stati…

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

Rasmus Kyng, Sushant Sachdeva

We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix w…

cs.DS2019

Iterative Refinement for $ℓ_{p}$ -norm Regression

Deeksha Adil, Rasmus Kyng, Richard Peng +1

We give improved algorithms for the $ℓ_{p}$ -regression problem, $min_{x} ∥ x ∥_{p}$ such that $A x = b,$ for all $p \in (1, 2) \cup (2, \infty) .$ Our algorithms obtain a high accur…