Open Lecture — Lower Bounds on the Size of Linear Programs

For half a century, proving that certain computational problems cannot be solved efficiently by a computer has turned out to be one of the hardest mathematical questions, with very little to no progress at all.  However, in many scenarios it is very natural to consider restricted computational models, and here the situation is more promising.  For example, a very standard approach in Operations Research is to model a computational problem as a linear program; this has the natural geometric interpretation of writing the solution space as projection of a higher dimensional polytope with few facets.  There has been remarkable progress in the last few years in understanding this model, leading to almost tight lower bounds that we will describe in this talk.

Light refreshments will be served before the lecture at 3:30 p.m.