6 citations · 10 across the 4 of their papers we have counts for
4 papers
Generalized Preconditioning and Network Flow Problems
Jonah Sherman
We consider approximation algorithms for the problem of finding of minimal norm satisfying a linear system , where the norm is a…
Improved bounds for the randomized decision tree complexity of recursive majority
Frederic Magniez, Ashwin Nayak, Miklos Santha +3
We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of for the two-sided-error randomized dec…
Nearly Maximum Flows in Nearly Linear Time
Jonah Sherman
We introduce a new approach to the maximum flow problem in undirected, capacitated graphs using -\emph{congestion-approximators}: easy-to-compute functions that approximate the…
Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut
Jonah Sherman
This paper ties the line of work on algorithms that find an O(sqrt(log(n)))-approximation to the sparsest cut together with the line of work on algorithms that run in sub-quadratic…