Opening Linear Programming: Bit Complexity
Linear Programming: Bit Complexity
- Length
- 25 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Rational solutions of linear programs
Linear programming bit complexity rests on one claim: a feasible system of linear inequalities with bit size has a rational solution of polynomial size. O'Donnell first converts standard form into equational form, writing free variables as differences of non-negative ones and adding slack variables. Unbounded programs may have no vertices, so he proves by induction on the dimension of affine subspaces that big box constraints leave feasibility unchanged. A full-rank subsystem is then solved by Gaussian elimination, which Edmonds (1967) showed runs in polynomial time, and this bounds every coordinate. Combined with linear programming duality, the bound places the problem in NP intersect coNP. The session, from CMU 15-750: A Theorist's Toolkit, assumes matrix rank and basic complexity classes.

Your comment is kept while you sign up.Sign in
Bounds the bits of a feasible LP solution via equational form and Gaussian elimination, putting LP in NP ∩ coNP.
Linear programming bit complexity rests on one claim: a feasible system of linear inequalities with bit size has a rational solution of polynomial size. O'Donnell first converts standard form into equational form, writing free variables as differences of non-negative ones and adding slack variables. Unbounded programs may have no vertices, so he proves by induction on the dimension of affine subspaces that big box constraints leave feasibility unchanged. A full-rank subsystem is then solved by Gaussian elimination, which Edmonds (1967) showed runs in polynomial time, and this bounds every coordinate. Combined with linear programming duality, the bound places the problem in NP intersect coNP. The session, from CMU 15-750: A Theorist's Toolkit, assumes matrix rank and basic complexity classes.
This lecture
Lecture 54 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.