b'Aaron Sidford'

research

∙ 09/08/2023

Parallel Submodular Function Minimization

We consider the parallel complexity of submodular function minimization ...

0 Deeparnab Chakrabarty, et al. ∙

research

∙ 08/07/2023

Matrix Completion in Almost-Verification Time

We give a new framework for solving the fundamental problem of low-rank ...

0 Jonathan A. Kelner, et al. ∙

research

∙ 08/03/2023

Quantum speedups for stochastic optimization

We consider the problem of minimizing a continuous function given quantu...

0 Aaron Sidford, et al. ∙

research

∙ 07/02/2023

Moments, Random Walks, and Limits for Spectrum Approximation

We study lower bounds for the problem of approximating a one dimensional...

0 Yujia Jin, et al. ∙

research

∙ 06/26/2023

Towards Optimal Effective Resistance Estimation

We provide new algorithms and conditional hardness for the problem of es...

0 Rajat Vadiraj Dwaraknath, et al. ∙

research

∙ 06/20/2023

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs

We study dynamic (1-ϵ)-approximate rounding of fractional matchings – a ...

0 Sayan Bhattacharya, et al. ∙

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...

0 Arun Jambulapati, et al. ∙

research

∙ 01/31/2023

Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification

In this paper, we introduce a new, spectral notion of approximation betw...

0 AmirMahdi Ahmadinejad, et al. ∙

research

∙ 01/10/2023

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling

We give a quantum algorithm for computing an ϵ-approximate Nash equilibr...

0 Adam Bouland, et al. ∙

research

∙ 01/01/2023

ReSQueing Parallel and Private Stochastic Convex Optimization

We introduce a new tool for stochastic convex optimization (SCO): a Rewe...

0 Yair Carmon, et al. ∙

research

∙ 12/13/2022

Dynamic Maxflow via Dynamic Interior Point Methods

In this paper we provide an algorithm for maintaining a (1-ϵ)-approximat...

0 Jan van den Brand, et al. ∙

research

∙ 10/13/2022

On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood

We provide an efficient unified plug-in approach for estimating symmetri...

0 Moses Charikar, et al. ∙

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...

0 Arun Jambulapati, et al. ∙

research

∙ 07/09/2022

Improved Lower Bounds for Submodular Function Minimization

We provide a generic technique for constructing families of submodular f...

0 Deeparnab Chakrabarty, et al. ∙

research

∙ 06/17/2022

RECAPP: Crafting a More Efficient Catalyst for Convex Optimization

The accelerated proximal point algorithm (APPA), also known as "Catalyst...

0 Yair Carmon, et al. ∙

research

∙ 05/30/2022

Optimal and Adaptive Monteiro-Svaiter Acceleration

We develop a variant of the Monteiro-Svaiter (MS) acceleration framework...

0 Yair Carmon, et al. ∙

research

∙ 04/27/2022

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Box-simplex games are a family of bilinear minimax objectives which enca...

0 Arun Jambulapati, et al. ∙

research

∙ 04/08/2022

The Complexity of Infinite-Horizon General-Sum Stochastic Games

We study the complexity of computing stationary Nash equilibrium (NE) in...

0 Yujia Jin, et al. ∙

research

∙ 03/29/2022

Efficient Convex Optimization Requires Superlinear Memory

We show that any memory-constrained, first-order algorithm which minimiz...

0 Annie Marsden, et al. ∙

research

∙ 03/08/2022

Semi-Random Sparse Recovery in Nearly-Linear Time

Sparse recovery is one of the most fundamental and well-studied inverse ...

0 Jonathan A. Kelner, et al. ∙

research

∙ 02/09/2022

Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

We design accelerated algorithms with improved rates for several fundame...

0 Yujia Jin, et al. ∙

research

∙ 12/01/2021

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers

We make several advances broadly related to the maintenance of electrica...

0 Jan van den Brand, et al. ∙

research

∙ 11/02/2021

Improved Iteration Complexities for Overconstrained p-Norm Regression

In this paper we obtain improved iteration complexities for solving ℓ_p ...

0 Arun Jambulapati, et al. ∙

research

∙ 10/29/2021

Computing Lewis Weights to High Precision

We present an algorithm for computing approximate ℓ_p Lewis weights to h...

0 Maryam Fazel, et al. ∙

research

∙ 06/17/2021

Stochastic Bias-Reduced Gradient Methods

We develop a new primitive for stochastic optimization: a low-bias, low-...

0 Hilal Asi, et al. ∙

research

∙ 06/13/2021

Towards Tight Bounds on the Sample Complexity of Average-reward MDPs

We prove new upper and lower bounds for sample complexity of finding an ...

0 Yujia Jin, et al. ∙

research

∙ 05/04/2021

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

We characterize the complexity of minimizing max_i∈[N] f_i(x) for convex...

0 Yair Carmon, et al. ∙

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...

0 Jan van den Brand, et al. ∙

research

∙ 11/17/2020

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

In this paper we provide an O(m (loglog n)^O(1)log(1/ϵ))-expected time a...

0 Arun Jambulapati, et al. ∙

research

∙ 11/12/2020

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

We show that standard extragradient methods (i.e. mirror prox and dual e...

0 Michael B. Cohen, et al. ∙

research

∙ 11/06/2020

Semi-Streaming Bipartite Matching in Fewer Passes and Less Space

We provide algorithms with improved pass and space complexities for appr...

0 Yujia Jin, et al. ∙

research

∙ 11/05/2020

Instance Based Approximations to Profile Maximum Likelihood

In this paper we provide a new efficient algorithm for approximately com...

4 Nima Anari, et al. ∙

research

∙ 10/12/2020

Large-Scale Methods for Distributionally Robust Optimization

We propose and analyze algorithms for distributionally robust optimizati...

0 Daniel Lévy, et al. ∙

research

∙ 09/17/2020

Coordinate Methods for Matrix Games

We develop primal-dual coordinate methods for solving bilinear saddle-po...

0 Yair Carmon, et al. ∙

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...

0 Jan van den Brand, et al. ∙

research

∙ 08/28/2020

Efficiently Solving MDPs with Stochastic Mirror Descent

We present a unified framework based on primal-dual stochastic mirror de...

0 Yujia Jin, et al. ∙

research

∙ 08/04/2020

Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semi-Random Noise

Classical iterative algorithms for linear system solving and regression ...

0 Jerry Li, et al. ∙

research

∙ 04/17/2020

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Designing dynamic graph algorithms against an adaptive adversary is a ma...

0 Aaron Bernstein, et al. ∙

research

∙ 04/06/2020

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

In this paper we consider the problem of computing the likelihood of the...

8 Nima Anari, et al. ∙

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...

0 Yang P. Liu, et al. ∙

research

∙ 03/18/2020

Acceleration with a Ball Optimization Oracle

Consider an oracle which takes a point x and returns the minimizer of a ...

0 Yair Carmon, et al. ∙

research

∙ 03/02/2020

A General Framework for Symmetric Property Estimation

In this paper we provide a general framework for estimating symmetric pr...

0 Moses Charikar, et al. ∙

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...

0 Jan van den Brand, et al. ∙

research

∙ 12/10/2019

High-precision Estimation of Random Walks in Small Space

In this paper, we provide a deterministic Õ(log N)-space algorithm for e...

0 AmirMahdi Ahmadinejad, et al. ∙

research

∙ 11/25/2019

Faster Matroid Intersection

In this paper we consider the classic matroid intersection problem: give...

0 Deeparnab Chakrabarty, et al. ∙

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...

0 Yang P. Liu, et al. ∙

research

∙ 10/17/2019

Solving Linear Programs with Sqrt(rank) Linear System Solves

We present an algorithm that given a linear program with n variables, m ...

0 Yin Tat Lee, et al. ∙

research

∙ 10/15/2019

Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG

Given a data matrix A∈R^n × d, principal component projection (PCP) and ...

0 Yujia Jin, et al. ∙

research

∙ 08/31/2019

Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

In this paper we provide improved running times and oracle complexities ...

0 Brian Axelrod, et al. ∙

research

∙ 08/29/2019

Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity

In this paper, we settle the sampling complexity of solving discounted t...

12 Aaron Sidford, et al. ∙

Aaron Sidford

Featured Co-authors