research
∙
04/27/2023
A Simple and Efficient Parallel Laplacian Solver
A symmetric matrix is called a Laplacian if it has nonpositive off-diago...
share
research
∙
03/04/2023
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Oblivious routing is a well-studied distributed paradigm that uses stati...
research
∙
11/08/2022
Fast Algorithms for ℓ_p-Regression
The ℓ_p-norm regression problem is a classic problem in optimization wit...
research
∙
11/02/2022
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
We demonstrate that for expander graphs, for all ϵ > 0, there exists a d...
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
∙
05/12/2022
Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities
In this work, we present new simple and optimal algorithms for solving t...
research
∙
05/03/2022
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
We present a nearly-linear time algorithm for finding a minimum-cost flo...
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
∙
07/06/2021
Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization
We provide several algorithms for constrained optimization of a large cl...
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
∙
07/13/2020
Regularized linear autoencoders recover the principal components, eventually
Our understanding of learning input-output relationships with neural net...
research
∙
07/06/2020
Faster Graph Embeddings via Coarsening
Graph embeddings are a ubiquitous tool for machine learning tasks, such ...
research
∙
06/22/2020
A Provably Convergent and Practical Algorithm for Min-max Optimization with Applications to GANs
We present a new algorithm for optimizing min-max loss functions that ar...
research
∙
10/23/2019
Faster p-norm minimizing flows, via smoothed q-norm problems
We present faster high-accuracy algorithms for computing ℓ_p-norm minimi...
research
∙
07/16/2019
Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
Linear regression in ℓ_p-norm is a canonical optimization problem that a...
research
∙
07/09/2019
Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model
Increasing the batch size is a popular way to speed up neural network tr...
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
∙
10/11/2018
Short Cycles via Low-Diameter Decompositions
We present improved algorithms for short cycle decomposition of a graph....
research
∙
05/30/2018
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
We develop a framework for graph sparsification and sketching, based on ...
research
∙
01/14/2018
