The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. The algorithmic issues are closely related to the combinatorial and geometric structure of the feasible region. Focusing on the analysis of worst-case constructions leading to computationally challenging instances, we discuss connections to the largest diameter of lattice polytopes, to the complexity of convex matroid optimization, and to the number of generalized retarded functions in quantum field theory.  Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. 

Based on joint works with Anna Deza (Toronto), Joe Guan (McMaster), Asaf Levin (Technion), George Manoussakis (Versailles), Syed Meesum (Wrocław), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII).