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. Simplex algorithms are defined by their pivoting rules, and I present an improved version of the pivoting rule with the best known (combinatorial) bound. I then use this result 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.
Thomas Dueholm Hansen is currently assistant professor at the department of computer science at Aarhus University, where he is funded by a grant from the Carlsberg foundation. He received his Ph.D. from Aarhus University in 2012, and later worked as a postdoc at Tel Aviv University and Stanford University. His main research interests involve the design and analysis of algorithms for problems in optimization and game theory. He was a co-winner of the STOC 2011 best paper award.