Yaron Singer, Harvard University

Abstract

I'll describe a novel approach that yields algorithms whose parallel running time is exponentially faster than any previously known ones for submodular maximization. These algorithms reduce the number of parallel runtime from Omega(n) to O(log n) while retaining optimal approximation guarantees. Time permitting I'll discuss parallelization for convex optimization. In contrast to the submodular case, we show information theoretic lower bounds indicating that parallelization cannot accelerate (non-smooth) convex optimization.

Based on joint work with Eric Balkanski, Adam Breuer, and Aviad Rubinstein