Michael B. Cohen

Publication Activity (10 Years)

Years Active: 2014-2021
Publications (10 Years): 41

Top Topics

Stationary Distribution

Matrix Multiplication

Top Venues

Publications

Michael B. Cohen, Yin Tat Lee, Zhao Song
Solving Linear Programs in the Current Matrix Multiplication Time. J. ACM 68 (1) (2021)
Michael B. Cohen, Aaron Sidford, Kevin Tian
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. ITCS (2021)
Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee
Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing. SIAM J. Comput. 50 (3) (2021)
Michael B. Cohen, Aaron Sidford, Kevin Tian
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. CoRR (2020)
Michael B. Cohen, Cameron Musco, Jakub Pachocki
Online Row Sampling. Theory Comput. 16 (2020)
Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang
A near-optimal algorithm for approximating the John Ellipsoid. COLT (2019)
Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee
Metrical task systems on trees via mirror descent and unfair gluing. SODA (2019)
Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang
A near-optimal algorithm for approximating the John Ellipsoid. CoRR (2019)
C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee
A Nearly-Linear Bound for Chasing Nested Convex Bodies. SODA (2019)
Michael B. Cohen, Yin Tat Lee, Zhao Song
Solving linear programs in the current matrix multiplication time. STOC (2019)
Michael B. Cohen, Yin Tat Lee, Zhao Song
Solving Linear Programs in the Current Matrix Multiplication Time. CoRR (2018)
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. FOCS (2018)
Timothy Chu, Michael B. Cohen, Jakub W. Pachocki, Richard Peng
Constant Arboricity Spectral Sparsifiers. CoRR (2018)
C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee
A Nearly-Linear Bound for Chasing Nested Convex Bodies. CoRR (2018)
Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee
Metrical task systems on trees via mirror descent and unfair gluing. CoRR (2018)
Michael B. Cohen, T. S. Jayram, Jelani Nelson
Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. SOSA (2018)
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li
regression provably beyond self-concordance and in input-sparsity time. STOC (2018)
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. CoRR (2018)
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, Aleksander Madry
k-server via multiscale entropic regularization. STOC (2018)
Michael B. Cohen, Jelena Diakonikolas, Lorenzo Orecchia
On Acceleration with Noise-Corrupted Gradients. CoRR (2018)
Sébastien Bubeck, Michael B. Cohen, Yuanzhi Li
Sparsity, variance and curvature in multi-armed bandits. ALT (2018)
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu
) Time (Extended Abstract). SODA (2017)
Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee, Aleksander Madry
k-server via multiscale entropic regularization. CoRR (2017)
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li
regression provably beyond self-concordance and in input-sparsity time. CoRR (2017)
Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods. CoRR (2017)
Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods. FOCS (2017)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. STOC (2017)
Michael B. Cohen, Cameron Musco, Christopher Musco
Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling. SODA (2017)
Sébastien Bubeck, Michael B. Cohen, Yuanzhi Li
Sparsity, variance and curvature in multi-armed bandits. CoRR (2017)
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub W. Pachocki, Aaron Sidford
Geometric Median in Nearly Linear Time. CoRR (2016)
Michael B. Cohen
Ramanujan Graphs in Polynomial Time. FOCS (2016)
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu
log W) Time. CoRR (2016)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs. CoRR (2016)
Michael B. Cohen, Jelani Nelson, David P. Woodruff
Optimal Approximate Matrix Product in Terms of Stable Rank. ICALP (2016)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. CoRR (2016)
Michael B. Cohen
Ramanujan Graphs in Polynomial Time. CoRR (2016)
Michael B. Cohen, Cameron Musco, Jakub W. Pachocki
Online Row Sampling. CoRR (2016)
Michael B. Cohen, Cameron Musco, Jakub W. Pachocki
Online Row Sampling. APPROX-RANDOM (2016)
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford
Geometric median in nearly linear time. STOC (2016)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. FOCS (2016)
Michael B. Cohen
Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities. SODA (2016)
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, Ameya Velingker
Approximating Nearest Neighbor Distances. CoRR (2015)
Michael B. Cohen, Jelani Nelson, David P. Woodruff
Optimal approximate matrix product in terms of stable rank. CoRR (2015)
Michael B. Cohen, Cameron Musco, Christopher Musco
Ridge Leverage Scores for Low-Rank Approximation. CoRR (2015)
Michael B. Cohen, Richard Peng
Row Sampling by Lewis Weights. STOC (2015)
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, Ameya Velingker
Approximating Nearest Neighbor Distances. WADS (2015)
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford
Uniform Sampling for Matrix Approximation. ITCS (2015)
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. STOC (2015)
Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki, Richard Peng, Anup B. Rao
Preconditioning in Expectation. CoRR (2014)
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. CoRR (2014)
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford
Uniform Sampling for Matrix Approximation. CoRR (2014)
Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Shen Chen Xu
Stretching Stretch. CoRR (2014)
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, Shen Chen Xu
time. STOC (2014)
Michael B. Cohen, Richard Peng
Row Sampling by Lewis Weights. CoRR (2014)
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Richard Peng, Noel Walkington
Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball. SODA (2014)