A polynomial lower bound on adaptive complexity of submodular maximization

Wenzheng Li, Paul Liu, Jan Vondrak

In large-data applications, it is desirable to design algorithms with a high degree of parallelization. In the context of submodular optimization, adaptive complexity has become a…