Abstract:

In this talk I give a basic introduction to linear programming and other closely related problems such as Markov decision processes and turn-based stochastic games. I present some recent algorithmic breakthroughs from the area, focusing in particular on my own work, and describe the future research directions that I find most promising.

My main focus will be on simplex algorithms; the classical combinatorial algorithm for linear programming. The Random-Facet algorithm is an elegant, randomized version of the simplex algorithm that was introduced independently by Kalai and by Matousek, Sharir, and Welzl in 1992. The expected running time of the Random-Facet algorithm is subexponential in the combinatorial size--the number of variables and inequalities--of the linear program. This gives the best known combinatorial bound for solving general linear programs, as well as the best known bound for turn-based stochastic games. I will present an improved version of the Random-Facet algorithm, and use this to illustrate the connection between linear programs and turn-based stochastic games.

I will also say a few words about other projects I have been involved in recently, including a paper that will appear in STOC 2016 where we show that solving edit distance in slightly faster than quadratic time implies that NEXP does not have non-uniform NC^1 circuits, which would be a major breakthrough in complexity theory.