Eric Balkanski, Columbia University

Abstract

The adaptive complexity model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization.

In this talk, I will discuss recent results that develop constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model. I will focus on the problem of maximizing a monotone submodular function under a matroid constraint, for which we develop an algorithm that achieves an approximation guarantee that is arbitrarily close to the optimal 1 − 1/e approximation and has O(log(n) log(k)) adaptivity. This result is obtained using a novel technique of adaptive sequencing which departs from previous techniques for submodular maximization in the adaptive complexity model. 

Joint work with Aviad Rubinstein and Yaron Singer.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home