Linear Programming - Bit Complexity - Lecture 17c of CS Theory Toolkit

Explore the bit complexity of Linear Programming in this graduate-level lecture from Carnegie Mellon University's "CS Theory Toolkit" course. Delve into the proof that feasible Linear Programs have solutions expressible with polynomial bits, and understand how this, combined with LP duality, places Linear Programming in NP ∩ coNP. Learn about converting linear programs, obtaining and writing K prime efficiently, and simplification techniques. Gain insights from recommended resources like Matoušek and Gärtner's "Understanding and Using Linear Programming" and Grötschel, Lovász, and Schrijver's "Geometric Algorithms and Combinatorial Optimization." Taught by Professor Ryan O'Donnell, this 25-minute lecture is part of a comprehensive semester-long course on mathematical and computer science fundamentals for theoretical computer science research.

Intro
Proof
Big box constraints
Converting a linear program to an equivalent
Obtaining K prime efficiently
Writing K prime
Simplification
Summary