Michael B. Cohen

activity

20152020

most citedSparsity, variance and curvature in multi-armed bandits

57 citations · 57 across the 1 of their papers we have counts for

collaborators

Showing 2018Show all

5 papers · 1 filter

cs.DS2018

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 $n \times n$ Eulerian directed Laplacian with $m$ nonzero entries, we show how to…

cs.DS2018

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 $min_{A x = b, x \geq 0} c^{⊤} x$ with $n$ variables in time $O^{*} ((n^{ω} + n^{2.5 - α /2} + n^{2 + 1/6}) lo g (n / δ))$ where $ω$ is the e…

cs.DS2018

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…

cs.DS2018

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 $O (depth \times lo g n)$ -competitive randomized algorithm based on the mirror descent framework introduce…

cs.DS2018

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…