Conference Publications


The Complexity of Infinite-Horizon General-Sum Stochastic Games


Optimal and Adaptive Monteiro-Svaiter Acceleration

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

Improved Lower Bounds for Submodular Function Minimization 

RECAPP: Crafting a More Efficient Catalyst for Convex Optimization 

Efficient Convex Optimization Requires Superlinear Memory

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

Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space

Algorithmic trade-offs for girth approximation in undirected graphs 

Computing Lewis Weights to High Precision


Stochastic Bias-Reduced Gradient Methods

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

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

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

Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration


Acceleration with a Ball Optimization Oracle

Instance Based Approximations to Profile Maximum Likelihood

Large-Scale Methods for Distributionally Robust Optimization

High-precision Estimation of Random Walks in Small Space

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs 

Coordinate Methods for Matrix Games

Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time

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

Efficiently Solving MDPs with Stochastic Mirror Descent

Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond

Solving Tall Dense Linear Programs in Nearly Linear Time

Faster energy maximization for faster maximum flow.

Constant Girth Approximation for Directed Graphs in Subquadratic Time

Leverage Score Sampling for Faster Accelerated Regression and ERM

Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

Fast and Space Efficient Spectral Sparsification in Dynamic Streams


Variance Reduction for Matrix Games

Complexity of Highly Parallel Non-Smooth Convex Optimization

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

A Direct Õ(1/ϵ) Iteration Parallel Algorithm for Optimal Transport

A General Framework for Efficient Symmetric Property Estimation

Parallel Reachability in Almost Linear Work and Square Root Depth

Faster Matroid Intersection

Deterministic Approximation of Random Walks in Small Space

A Rank-1 Sketch for Matrix Multiplicative Weights

Near-optimal method for highly smooth convex optimization

Efficient profile maximum likelihood for universal symmetric property estimation

Memory-sample tradeoffs for linear regression with small error

Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications


Exploiting Numerical Sparsity for Efficient Learning: Faster Eigenvector Computation and Regression

Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model 

Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow

Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations

Efficient Convex Optimization with Membership Oracles

Accelerating Stochastic Gradient Descent for Least Squares Regression

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

Efficient Õ(n/ϵ) Spectral Sketches for the Laplacian and its Pseudoinverse

Stability of the Lanczos Method for Matrix Function Approximation

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness


Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs

Subquadratic Submodular Function Minimization


Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

Geometric Median in Nearly Linear Time

Routing Under Balance

Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm

Principal Component Projection Without Principal Component Analysis

Faster Eigenvector Computation via Shift-and-Invert Preconditioning 

Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis


A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

Efficient Inverse Maintenance and Faster Algorithms for Linear Programming

Competing with the Empirical Risk Minimizer in a Single Pass

Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

Uniform Sampling for Matrix Approximation


Path-Finding Methods for Linear Programming : Solving Linear Programs in Õ(√rank) Iterations and Faster Algorithms for Maximum Flow

Single Pass Spectral Sparsification in Dynamic Streams

An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations


Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time

Journal and Book Publications

Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

Deterministic Approximation of Random Walks in Small Space

Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

Efficient Convex Optimization with Membership Oracles

Lower Bounds for Finding Stationary Points II: First-Order Methods

Lower bounds for finding stationary points I 

Accelerated Methods for NonConvex Optimization 

Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification

Single Pass Spectral Sparsification in Dynamic Streams