research
∙
07/19/2023
On Dynamic Graph Algorithms with Predictions
We study dynamic algorithms in the model of algorithms with predictions....
share
research
∙
04/25/2023
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques
Since the development of efficient linear program solvers in the 80s, al...
research
∙
04/14/2023
Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary
Algebraic data structures are the main subroutine for maintaining distan...
research
∙
04/05/2023
Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
Large language models (LLMs) have made fundamental changes in human life...
research
∙
12/13/2022
Dynamic Maxflow via Dynamic Interior Point Methods
In this paper we provide an algorithm for maintaining a (1-ϵ)-approximat...
research
∙
08/04/2022
Nearly Optimal Communication and Query Complexity of Bipartite Matching
We settle the complexities of the maximum-cardinality bipartite matching...
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/05/2021
Fast Deterministic Fully Dynamic Distance Approximation
In this paper, we develop deterministic fully dynamic algorithms for com...
research
∙
02/10/2021
Breaking the Quadratic Barrier for Matroid Intersection
The matroid intersection problem is a fundamental problem that has been ...
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
∙
10/26/2020
Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms
Many algorithms use data structures that maintain properties of matrices...
research
∙
09/03/2020
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...
research
∙
06/20/2020
Training (Overparametrized) Neural Networks in Near-Linear Time
The slow convergence rate and pathological curvature issues of first-ord...
research
∙
04/17/2020
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
research
∙
02/06/2020
Solving Tall Dense Linear Programs in Nearly Linear Time
In this paper we provide an Õ(nd+d^3) time randomized algorithm for solv...
research
∙
10/25/2019
A Deterministic Linear Program Solver in Current Matrix Multiplication Time
Interior point algorithms for solving linear programs have been studied ...
research
∙
09/24/2019
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
Consider the following distance query for an n-node graph G undergoing e...
research
∙
07/18/2019
Sensitive Distance and Reachability Oracles for Large Batch Updates
In the sensitive distance oracle problem, there are three phases. We fir...
research
∙
05/13/2019