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.