A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization

Explore a conference talk examining the polynomial lower bound on adaptive complexity of submodular maximization. Delve into the adaptive complexity model, nonmonotone submodular functions, and one-half approximation algorithms. Investigate the hardness results presented and gain insights into this important area of theoretical computer science. Access accompanying slides and the full research paper for a deeper understanding of the concepts discussed.

Introduction
Background material
Adaptive complexity model
Nonmonotone
Onehalf approximation
Hardness
Questions