research
∙
05/15/2023
Sparsifying Sums of Norms
For any norms N_1,…,N_m on ℝ^n and N(x) := N_1(x)+⋯+N_m(x), we show ther...
share
research
∙
12/13/2022
Dynamic Maxflow via Dynamic Interior Point Methods
In this paper we provide an algorithm for maintaining a (1-ϵ)-approximat...
research
∙
09/21/2022
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
We present an algorithm that given any n-vertex, m-edge, rank r hypergra...
research
∙
07/02/2022
Exponential Convergence of Sinkhorn Under Regularization Scheduling
The optimal transport (OT) problem or earth mover's distance has wide ap...
research
∙
04/06/2022
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
We design fast algorithms for repeatedly sampling from strongly Rayleigh...
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
∙
12/01/2021
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
We make several advances broadly related to the maintenance of electrica...
research
∙
11/02/2021
Improved Iteration Complexities for Overconstrained p-Norm Regression
In this paper we obtain improved iteration complexities for solving ℓ_p ...
research
∙
11/01/2021
Online Edge Coloring via Tree Recurrences and Correlation Decay
We give an online algorithm that with high probability computes a (e/e-1...
research
∙
04/14/2021
A Gaussian fixed point random walk
In this note, we design a discrete random walk on the real line which ta...
research
∙
01/18/2021
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
We give an algorithm for computing exact maximum flows on graphs with m ...
research
∙
01/14/2021
Minimum Cost Flows, MDPs, and ℓ_1-Regression in Nearly Linear Time for Dense Instances
In this paper we provide new randomized algorithms with improved runtime...
research
∙
12/31/2020
Minor Sparsifiers and the Distributed Laplacian Paradigm
We study distributed algorithms built around edge contraction based vert...
research
∙
11/30/2020
Vertex Sparsification for Edge Connectivity in Polynomial Time
An important open question in the area of vertex sparsification is wheth...
research
∙
07/15/2020
Vertex Sparsification for Edge Connectivity
Graph compression or sparsification is a basic information-theoretic and...
research
∙
06/24/2020
Discrepancy Minimization via a Self-Balancing Walk
We study discrepancy minimization for vectors in ℝ^n under various setti...
research
∙
03/19/2020
Faster Divergence Maximization for Faster Maximum Flow
In this paper we provide an algorithm which given any m-edge n-vertex di...
research
∙
10/31/2019
Faster Energy Maximization for Faster Maximum Flow
In this paper we provide an algorithm which given any m-edge n-vertex di...
research
∙
10/23/2019
Vertex Sparsifiers for c-Edge Connectivity
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve...
research
∙
08/31/2019
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
In this paper we provide improved running times and oracle complexities ...
research
∙
07/25/2019
Improved Girth Approximation and Roundtrip Spanners
In this paper we provide improved algorithms for approximating the girth...
research
∙
05/21/2019
Parallel Reachability in Almost Linear Work and Square Root Depth
In this paper we provide a parallel algorithm that given any n-node m-ed...
research
∙
10/11/2018
Short Cycles via Low-Diameter Decompositions
We present improved algorithms for short cycle decomposition of a graph....
research
∙
03/11/2018