Michael B. Cohen

According to our database, Michael B. Cohen authored at least 33 papers between 2014 and 2021.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2021

Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing.

Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee

SIAM J. Comput., 2021

Solving Linear Programs in the Current Matrix Multiplication Time.

Michael B. Cohen, Yin Tat Lee, Zhao Song

J. ACM, 2021

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

Michael B. Cohen, Aaron Sidford, Kevin Tian

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

2020

Online Row Sampling.

Michael B. Cohen, Cameron Musco, Jakub Pachocki

Theory Comput., 2020

2019

A Nearly-Linear Bound for Chasing Nested Convex Bodies.

C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee

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

A near-optimal algorithm for approximating the John Ellipsoid.

Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang

Proceedings of the Conference on Learning Theory, 2019

2018

Sparse approximations, iterative methods, and faster algorithms for matrices and graphs.

Michael Benjamin Cohen

PhD thesis, 2018

Constant Arboricity Spectral Sparsifiers.

Timothy Chu, Michael B. Cohen, Jakub W. Pachocki, Richard Peng

CoRR, 2018

k-server via multiscale entropic regularization.

Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, Aleksander Madry

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

An homotopy method for l_p regression provably beyond self-concordance and in input-sparsity time.

Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Simple Analyses of the Sparse Johnson-Lindenstrauss Transform.

Michael B. Cohen, T. S. Jayram, Jelani Nelson

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

On Acceleration with Noise-Corrupted Gradients.

Michael Cohen, Jelena Diakonikolas, Lorenzo Orecchia

Proceedings of the 35th International Conference on Machine Learning, 2018

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

Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford

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

Sparsity, variance and curvature in multi-armed bandits.

Sébastien Bubeck, Michael B. Cohen, Yuanzhi Li

Proceedings of the Algorithmic Learning Theory, 2018

2017

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

Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu

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

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (<i>m</i>^10/7 log <i>W</i>) Time (Extended Abstract).

Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling.

Michael B. Cohen, Cameron Musco, Christopher Musco

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods.

Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ(m^10/7 log W) Time.

Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu

CoRR, 2016

Geometric median in nearly linear time.

Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford

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

Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities.

Michael B. Cohen

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Optimal Approximate Matrix Product in Terms of Stable Rank.

Michael B. Cohen, Jelani Nelson, David P. Woodruff

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

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

Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu

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

Ramanujan Graphs in Polynomial Time.

Michael B. Cohen

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

2015

Ridge Leverage Scores for Low-Rank Approximation.

Michael B. Cohen, Cameron Musco, Christopher Musco

CoRR, 2015

Approximating Nearest Neighbor Distances.

Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, Ameya Velingker

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

L_p Row Sampling by Lewis Weights.

Michael B. Cohen, Richard Peng

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation.

Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Uniform Sampling for Matrix Approximation.

Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford

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

2014

Stretching Stretch.

Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Shen Chen Xu

CoRR, 2014

Preconditioning in Expectation.

Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki, Richard Peng, Anup B. Rao

CoRR, 2014

Solving SDD linear systems in nearly <i>m</i>log^1/2<i>n</i> time.

Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, Shen Chen Xu

Proceedings of the Symposium on Theory of Computing, 2014

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball.

Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Richard Peng, Noel Walkington

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