What importance does the Hirsch conjecture have to Simplex Complexity? The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has proved that this fails in general.
Assume we know the diameter of a polytope on which we do Simplex Programming. 


*

*How does it affect the complexity of the algorithm?

*Can extended formulations reduce the complexity of Simplex algorithm?
In https://www.ems-ph.org/journals/newsletter/pdf/2012-12-86.pdf it is said

however connection is not clear.
Why is the Hirsch conjecture important to Simplex Complexity?
 A: The diameter of the graph of the feasible polytope for a linear programming problem is indeed a lower bound for the number of pivot steps for the simplex algorithm when you start from a vertex and follow pivots steps all the way to the maximum. So if you find a version of the simplex algorithm for which the number of steps is provably polynomial (in $n$ the number of inequalities, and $d$ the number of variables) or even liner in $d$ and $n$ this will simultaneously give a polynomial [linear] version of the simplex algorithm and a polynomial [linear] upper bound on the diameter. 
However in terms of what was proved so far the connections are not so clear.
1) The best upper bound on the diameter is of the type $n^{\log d}$. There is nothing as good (or even close) known for the algorithm (See 2)) .
2) The best version of the simplex algorithm requires (in expectation) $\exp (C \sqrt {d \log n})$ pivot steps. 
3) For many pivot rules including the best known ones that are randomized, the (expected) number of steps in the worse case is $\exp d$ or $\exp (d^{c})$ where $c>0$. 
4) The exponential lower bounds for 3) occur already for polytopes that are combinatorially equivalent to a $d$-cube, which have diameter $d$.
