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.
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Introduction
Background material
Adaptive complexity model
Nonmonotone
Onehalf approximation
Hardness
Questions
Taught by
Association for Computing Machinery (ACM)
Related Courses
-
A Lower Bound for Parallel Submodular Minimization
-
Randomized Composable Core-Sets for Submodular Maximization
-
Complexity of Lattice Problems
-
Money, Circuits, Mythic Figures, and More - Theory in the Allen School
-
The Polynomial Method in Quantum Query Complexity - Part 2
-
Optimal Streaming Approximations for All Boolean Max 2-CSPs and Max k-SAT
