07 April 2016
Time: April 4, 2016, 11.00-11.45
Place: 4A09, ITU.
Speaker: Thomas Dueholm Hansen

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.