Aaron Sidford

Maximilian Probst Gutenberg

CoRR, 2024

Sparsifying Generalized Linear Models.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.

[BibT_eX]

[DOI]

Sushant Sachdeva

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Entropy Regularization and Faster Decremental Matching in General Graphs.

[BibT_eX]

[DOI]

Jiale Chen

Ta-Wei Tu

CoRR, 2023

Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification.

[BibT_eX]

[DOI]

CoRR, 2023

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Dynamic Maxflow via Dynamic Interior Point Methods.

[BibT_eX]

[DOI]

Jan van den Brand

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Improved girth approximation in weighted undirected graphs.

[BibT_eX]

[DOI]

Avi Kadria

Liam Roditty

Virginia Vassilevska Williams

Uri Zwick

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Quantum speedups for stochastic optimization.

[BibT_eX]

[DOI]

Chenyi Zhang

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Structured Semidefinite Programming for Recovering Structured Preconditioners.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Towards Optimal Effective Resistance Estimation.

[BibT_eX]

[DOI]

Rajat Vadiraj Dwaraknath

Ishani Karmarkar

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Parallel Submodular Function Minimization.

[BibT_eX]

[DOI]

Andrei Graur

Haotian Jiang

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

The Complexity of Infinite-Horizon General-Sum Stochastic Games.

[BibT_eX]

[DOI]

Vidya Muthukumar

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

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

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Matrix Completion in Almost-Verification Time.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sparsifying Sums of Norms.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sparse Submodular Function Minimization.

[BibT_eX]

[DOI]

Andrei Graur

Haotian Jiang

Maximilian Probst Gutenberg

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

ReSQueing Parallel and Private Stochastic Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.

[BibT_eX]

[DOI]

Sushant Sachdeva

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Singular Value Approximation and Sparsifying Random Walks on Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Semi-Random Sparse Recovery in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Moments, Random Walks, and Limits for Spectrum Approximation.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Improved iteration complexities for overconstrained p-norm regression.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Faster maxflow via improved dynamic spectral vertex sparsifiers.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Algorithmic trade-offs for girth approximation in undirected graphs.

[BibT_eX]

[DOI]

Avi Kadria

Liam Roditty

Virginia Vassilevska Williams

Uri Zwick

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Computing Lewis Weights to High Precision.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

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

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Optimal and Adaptive Monteiro-Svaiter Acceleration.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

RECAPP: Crafting a More Efficient Catalyst for Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.

[BibT_eX]

[DOI]

Aaron Bernstein

Jan van den Brand

Maximilian Probst Gutenberg

Danupon Nanongkai

Thatchaphol Saranurak

He Sun

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Improved Lower Bounds for Submodular Function Minimization.

[BibT_eX]

[DOI]

Andrei Graur

Haotian Jiang

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Efficient Convex Optimization Requires Superlinear Memory.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

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

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

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

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Deterministic Approximation of Random Walks in Small Space.

[BibT_eX]

[DOI]

Adv. Math. Commun., 2021

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Lower bounds for finding stationary points II: first-order methods.

[BibT_eX]

[DOI]

Math. Program., 2021

Improved Iteration Complexities for Overconstrained p-Norm Regression.

[BibT_eX]

[DOI]

CoRR, 2021

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

[BibT_eX]

[DOI]

Jan van den Brand

Thatchaphol Saranurak

Zhao Song

Di Wang

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Stochastic Bias-Reduced Gradient Methods.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.

[BibT_eX]

[DOI]

Michael B. Cohen

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

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

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

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

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

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

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Lower bounds for finding stationary points I.

[BibT_eX]

[DOI]

Math. Program., 2020

Semi-Streaming Bipartite Matching in Fewer Passes and Less Space.

[BibT_eX]

[DOI]

CoRR, 2020

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

[BibT_eX]

[DOI]

CoRR, 2020

Faster Divergence Maximization for Faster Maximum Flow.

[BibT_eX]

[DOI]

CoRR, 2020

Faster energy maximization for faster maximum flow.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Constant girth approximation for directed graphs in subquadratic time.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Solving tall dense linear programs in nearly linear time.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Near-optimal Approximate Discrete and Continuous Submodular Function Minimization.

[BibT_eX]

[DOI]

Brian Axelrod

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Large-Scale Methods for Distributionally Robust Optimization.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Acceleration with a Ball Optimization Oracle.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Instance Based Approximations to Profile Maximum Likelihood.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Efficiently Solving MDPs with Stochastic Mirror Descent.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

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

[BibT_eX]

[DOI]

Tarun Kathuria

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Coordinate Methods for Matrix Games.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Zhao Song

Di Wang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

High-precision Estimation of Random Walks in Small Space.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

[BibT_eX]

[DOI]

Oliver Hinder

Nimit Sharad Sohoni

Proceedings of the Conference on Learning Theory, 2020

Leverage Score Sampling for Faster Accelerated Regression and ERM.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Solving Linear Programs with Sqrt(rank) Linear System Solves.

[BibT_eX]

[DOI]

CoRR, 2019

Improved Girth Approximation and Roundtrip Spanners.

[BibT_eX]

[DOI]

CoRR, 2019

A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport.

[BibT_eX]

[DOI]

CoRR, 2019

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space.

[BibT_eX]

[DOI]

CoRR, 2019

Memory-sample tradeoffs for linear regression with small error.

[BibT_eX]

[DOI]

Vatsal Sharan

Gregory Valiant

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Efficient profile maximum likelihood for universal symmetric property estimation.

[BibT_eX]

[DOI]

Moses Charikar

Kirankumar Shiragur

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

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

[BibT_eX]

[DOI]

Amin Saberi

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

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

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A General Framework for Symmetric Property Estimation.

[BibT_eX]

[DOI]

Moses Charikar

Kirankumar Shiragur

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Variance Reduction for Matrix Games.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Complexity of Highly Parallel Non-Smooth Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Parallel Reachability in Almost Linear Work and Square Root Depth.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Faster Matroid Intersection.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives.

[BibT_eX]

[DOI]

Alexander V. Gasnikov

Pavel E. Dvurechensky

Eduard Gorbunov

Evgeniya A. Vorontsova

Proceedings of the Conference on Learning Theory, 2019

A Rank-1 Sketch for Matrix Multiplicative Weights.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Near-optimal method for highly smooth convex optimization.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Accelerated Methods for NonConvex Optimization.

[BibT_eX]

[DOI]

SIAM J. Optim., 2018

Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices.

[BibT_eX]

[DOI]

Kirankumar Shiragur

CoRR, 2018

Towards Optimal Running Times for Optimal Transport.

[BibT_eX]

[DOI]

CoRR, 2018

Coordinate Methods for Accelerating 𝓁∞ Regression and Faster Approximate Maximum Flow.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

CoRR, 2018

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Stability of the Lanczos Method for Matrix Function Approximation.

[BibT_eX]

[DOI]

Cameron Musco

Christopher Musco

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

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

[BibT_eX]

[DOI]

Neha Gupta

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

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

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

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

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Efficient Convex Optimization with Membership Oracles.

[BibT_eX]

[DOI]

Santosh S. Vempala

Proceedings of the Conference On Learning Theory, 2018

Accelerating Stochastic Gradient Descent for Least Squares Regression.

[BibT_eX]

[DOI]

Proceedings of the Conference On Learning Theory, 2018

2017

Single Pass Spectral Sparsification in Dynamic Streams.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

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

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2017

Arboral satisfaction: Recognition and LP approximation.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2017

Efficient Õ(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse.

[BibT_eX]

[DOI]

CoRR, 2017

Accelerating Stochastic Gradient Descent.

[BibT_eX]

[DOI]

CoRR, 2017

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Subquadratic submodular function minimization.

[BibT_eX]

[DOI]

Sam Chiu-wai Wong

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

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

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares).

[BibT_eX]

[DOI]

Venkata Krishna Pillutla

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Accelerated Methods for Non-Convex Optimization.

[BibT_eX]

[DOI]

CoRR, 2016

Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging.

[BibT_eX]

[DOI]

CoRR, 2016

Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm.

[BibT_eX]

[DOI]

CoRR, 2016

Routing under balance.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Geometric median in nearly linear time.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

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

[BibT_eX]

[DOI]

Proceedings of the 33nd International Conference on Machine Learning, 2016

Faster Eigenvector Computation via Shift-and-Invert Preconditioning.

[BibT_eX]

[DOI]

Proceedings of the 33nd International Conference on Machine Learning, 2016

Principal Component Projection Without Principal Component Analysis.

[BibT_eX]

[DOI]

Proceedings of the 33nd International Conference on Machine Learning, 2016

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

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

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

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Iterative methods, combinatorial optimization, and linear programming beyond the universal barrier.

[BibT_eX]

[DOI]

PhD thesis, 2015

Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation.

[BibT_eX]

[DOI]

CoRR, 2015

Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Uniform Sampling for Matrix Approximation.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

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

[BibT_eX]

[DOI]

Proceedings of the 32nd International Conference on Machine Learning, 2015

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

[BibT_eX]

[DOI]

Sam Chiu-wai Wong

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Competing with the Empirical Risk Minimizer in a Single Pass.

[BibT_eX]

[DOI]

Proceedings of The 28th Conference on Learning Theory, 2015

2014

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Following the Path of Least Resistance : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem.

[BibT_eX]

[DOI]

CoRR, 2013

Matching the Universal Barrier Without Paying the Costs : Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves.

[BibT_eX]

[DOI]

CoRR, 2013

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

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

[BibT_eX]

[DOI]