Michael B. Cohen's Publications
-
Solving linear program in the current matrix multiplication time
Michael B. Cohen, Yin Tat Lee, and Zhao Song
JACM 2020 (Journal version of STOC 2019)
-
A near-optimal algorithm for approximating the John Ellipsoid [arXiv]
Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang
COLT 2019
-
Metrical task systems on trees via mirror descent and unfair gluing [arXiv]
Sebastian Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee
SODA 2019
-
A Nearly-Linear Bound for Chasing Nested Convex Bodies [arXiv]
C.J. Argue, Sebastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee
SODA 2019
-
Solving linear program in the current matrix multiplication time [arXiv] [ADSI's blog]
Michael B. Cohen, Yin Tat Lee, and Zhao Song
STOC 2019
-
Sparse approximations, iterative methods, and faster algorithms for matrices and graphs
Michael Benjamin Cohen
MIT Ph.D. Thesis 2018
Advisors : Jonathan A. Kelner and Aleksander Madry
-
Sparsity, variance and curvature in multi-armed bandits
Sebastien Bubeck, Michael B. Cohen, Yuanzhi Li
ALT 2018 Best Student Paper Award
-
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations [arXiv] [Rasmus's talk at Simons]
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
FOCS 2018
-
On Acceleration with Noise-Corrupted Gradients
Michael B. Cohen, Jelena Diakonikolas, Lorenzo Orecchia
ICML 2018
-
Simple Analyses of the Sparse Johnson-Lindenstrauss Transform
Michael B. Cohen, T. S. Jayram, Jelani Nelson
SOSA 2018
-
k-server via multiscale entropic regularization [arXiv] [James's talk at Simons] [Sebastien's blog]
Sebastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, Aleksander Madry
STOC 2018
-
An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time [arXiv] [Yin Tat's talk at Simons]
Sebastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li
STOC 2018
-
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods [arXiv]
Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu
FOCS 2017
-
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in O (m 10/7 log W) Time [arXiv]
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu
SODA 2017
-
Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling [arXiv]
Michael B. Cohen, Cameron Musco, Christopher Musco
SODA 2017
-
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs [arXiv]
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
STOC 2017
-
Online Row Sampling [arXiv]
Michael B. Cohen, Cameron Musco, Jakub W. Pachocki
APPROX-RANDOM 2016
-
Ramanujan Graphs in Polynomial Time [arXiv] [Lance's blog] [Luca's blog] [RJLipton+KERegan's blog] [Scott's blog]
Michael B. Cohen
FOCS 2016 Best Student Paper Award
-
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More [arXiv]
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu
FOCS 2016
-
Optimal Approximate Matrix Product in Terms of Stable Rank [arXiv]
Michael B. Cohen, Jelani Nelson, David P. Woodruff
ICALP 2016
-
Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
Michael B. Cohen
SODA 2016
-
Geometric median in nearly linear time [arXiv]
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford
STOC 2016
-
Uniform Sampling for Matrix Approximation [arXiv]
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford
ITCS 2015
-
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation [arXiv]
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu
STOC 2015
-
Lp Row Sampling by Lewis Weights [arXiv]
Michael B. Cohen, Richard Peng
STOC 2015
-
Approximating Nearest Neighbor Distances
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, Ameya Velingker
WADS 2015
-
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
SODA 2014
-
Solving SDD linear systems in nearly m log 1/2 n time
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, Shen Chen Xu
STOC 2014