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.
Copyright. All Rights Reserved.