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 nearoptimal 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 NearlyLinear 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 multiarmed bandits
Sebastien Bubeck, Michael B. Cohen, Yuanzhi Li
ALT 2018 Best Student Paper Award

Solving Directed Laplacian Systems in NearlyLinear 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 NoiseCorrupted Gradients
Michael B. Cohen, Jelena Diakonikolas, Lorenzo Orecchia
ICML 2018

Simple Analyses of the Sparse JohnsonLindenstrauss Transform
Michael B. Cohen, T. S. Jayram, Jelani Nelson
SOSA 2018

kserver 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 selfconcordance and in inputsparsity 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

NegativeWeight 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 Lowrank Approximation via Ridge Leverage Score Sampling [arXiv]
Michael B. Cohen, Cameron Musco, Christopher Musco
SODA 2017

Almostlineartime 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
APPROXRANDOM 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 kMeans 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 1Laplacians 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