57 citations · 57 across the 1 of their papers we have counts for
10 papers · 1 filter
A near-optimal algorithm for approximating the John Ellipsoid
Michael B. Cohen, Ben Cousins, Yin Tat Lee +1
We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matche…
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an Eulerian directed Laplacian with nonzero entries, we show how to…
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, Zhao Song
This paper shows how to solve linear programs of the form with variables in time where is the e…
Constant Arboricity Spectral Sparsifiers
Timothy Chu, Michael B. Cohen, Jakub W. Pachocki +1
We show that every graph is spectrally similar to the union of a constant number of forests. Moreover, we show that Spielman-Srivastava sparsifiers are the union of O(logn) forests…
Metrical task systems on trees via mirror descent and unfair gluing
Sébastien Bubeck, Michael B. Cohen, James R. Lee +1
We consider metrical task systems on tree metrics, and present an -competitive randomized algorithm based on the mirror descent framework introduce…
A Nearly-Linear Bound for Chasing Nested Convex Bodies
C. J. Argue, Sébastien Bubeck, Michael B. Cohen +2
Friedman and Linial introduced the convex body chasing problem to explore the interplay between geometry and competitive ratio in metrical task systems. In convex body chasing, at…