Lower Bounds on the Size of Linear Programs

Explore the intricacies of computational complexity and linear programming in this 52-minute Simons Institute Open Lecture delivered by Thomas Rothvoß from the University of Washington. Delve into the fundamental concepts of computational complexity before transitioning to an in-depth examination of linear programming and extended formulations. Discover the application of linear programming to the Hamiltonian Circuit problem and gain insights into the geometric perspective of these mathematical constructs. Investigate the slack-matrix and rectangle covering lower bound, and uncover the properties of the correlation polytope. Conclude with an introduction to matchings and semi-definite programming, providing a comprehensive overview of advanced topics in theoretical computer science and optimization.

Intro
What is Computational Complexity?
Computational Complexity (2)
Computational Complexity (3)
Linear programming
Extended formulations
An LP for Hamiltonian Circuit Subtour elimination LP
Geometric view
Slack-matrix
Rectangle covering lower bound
Correlation polytope (1) The correlation polytope is
Correlation polytope (4)
Matchings
Semi-definite programming