Subexponential LPs Approximate Max-Cut

Explore a groundbreaking approach to approximating the Max-Cut problem using subexponential linear programs in this 26-minute IEEE conference talk. Delve into combinatorial optimization, linear and semidefinite programming, and their comparative analysis. Learn how LPs can effectively approximate Max Cut and examine additional discrete optimization problems. Follow the speakers through an engaging narrative, including a plot twist involving refutation in pseudorandom graphs, before reaching the conclusion of LP approximation in any graph. Gain insights from a high-level proof overview and walk away with a deeper understanding of this innovative solution in graph theory and optimization.

Intro
Combinatorial Optimization
Linear & Semidefinite Programs
Comparing LPs and SDPS
Case Study: Max Cut
LPs Can Approximate Max Cut!
Additional Discrete Optimization Problems
Story Time
Plot Twist: refutation in pseudorandom graphs
Conclusion: LP Approximation in any graph
High-level Proof Overview
Concluding