The diameter of a polytope P is the maximum length of a shortest path between a pair of vertices on the 1-skeleton of P, which is the graph where the vertices correspond to the 0-dimensional faces of P, and the edges are given by the 1-dimensional faces of P.

In this talk, I will discuss some hardness results regarding the complexity of computing the diameter of a polytope. These results are obtained by exploiting the structure of a well-known polytope in the optimization community: the fractional matching polytope. Eventually, I will also show that the structure of the fractional matching polytope can be used to derive some hardness results concerning the performance of the Simplex method.