research
∙
03/01/2023
Robust and Practical Solution of Laplacian Equations by Approximate Elimination
We introduce a new algorithm and software for solving linear equations i...
share
research
∙
11/08/2022
Fast Algorithms for ℓ_p-Regression
The ℓ_p-norm regression problem is a classic problem in optimization wit...
research
∙
09/19/2022
A Simple Framework for Finding Balanced Sparse Cuts via APSP
We present a very simple and intuitive algorithm to find balanced sparse...
research
∙
08/23/2022
Derandomizing Directed Random Walks in Almost-Linear Time
In this article, we present the first deterministic directed Laplacian L...
research
∙
04/05/2022
Maintaining Expander Decompositions via Sparse Cuts
In this article, we show that the algorithm of maintaining expander deco...
research
∙
03/01/2022
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
We give an algorithm that computes exact maximum flows and minimum-cost ...
research
∙
02/10/2022
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
We study linear equations in combinatorial Laplacians of k-dimensional s...
research
∙
01/27/2022
Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions
We give a nearly-linear time reduction that encodes any linear program a...
research
∙
11/03/2021
Scalar and Matrix Chernoff Bounds from ℓ_∞-Independence
We present new scalar and matrix Chernoff-style concentration bounds for...
research
∙
10/22/2021
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Given a directed, weighted graph G=(V,E) undergoing edge insertions, the...
research
∙
06/17/2021
Faster Sparse Matrix Inversion and Rank Computation in Finite Fields
We improve the current best running time value to invert sparse matrices...
research
∙
03/08/2021
On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
We prove lower bounds for higher-order methods in smooth non-convex fini...
research
∙
02/13/2021
Almost-linear-time Weighted ℓ_p-norm Solvers in Slightly Dense Graphs via Sparsification
We give almost-linear-time algorithms for constructing sparsifiers with ...
research
∙
06/25/2019
Flows in Almost Linear Time via Adaptive Preconditioning
We present algorithms for solving a large class of flow and regression p...
research
∙
01/21/2019
Iterative Refinement for ℓ_p-norm Regression
We give improved algorithms for the ℓ_p-regression problem, _xx_p such t...
research
∙
01/20/2019
Four Deviations Suffice for Rank 1 Matrices
We prove a matrix discrepancy bound that strengthens the famous Kadison-...
research
∙
11/26/2018
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
We show how to solve directed Laplacian systems in nearly-linear time. G...
research
∙
10/19/2018
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
Strongly Rayleigh distributions are a class of negatively dependent dist...
research
∙
05/23/2018
Incomplete Nested Dissection
We present an asymptotically faster algorithm for solving linear systems...
research
∙
05/08/2017