A polynomial lower bound on adaptive complexity of submodular maximization.

Wenzheng Li, Paul Liu, Jan Vondrk

Browse the full STOC paper archive.