Integral Geometry and the Polynomial Hirsch Conjecture

Jonathan Kelner
Massachusetts Institute of Technology

In this talk I will outline a geometric approach to the Polynomial Hirsch Conjecture, motivated by the integral geometry techniques that Daniel Spielman and I used in the polynomial simplex method that we set forth several years ago. I will argue that we cannot hope to prove diameter bounds for general polytopes before we understand the (probably much simpler) special case of polytopes determined by random linear constraints. This problem seems quite approachable but, to my knowledge, remains open. I will discuss why the existing techniques almost prove a diameter bound for many classes of random polytopes but fall slightly short. I will then describe several geometric and probabilistic conjectures that would give such a result. At the end, I will briefly speculate about how understanding random polytopes may inform the general case.

Presentation (PDF File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?