Michael B. Cohen

55 papers A* 20A 2B 2Journal 29Unranked 2

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