Thomas Dueholm Hansen



Assistant professor at the Department of Computer Science, Aarhus University. Supported by The Carlsberg Foundation.

My main research interests involve the design and analysis of algorithms for problems in optimization and game theory.

Email: {initials}@cs.au.dk

DBLP and Google Scholar.

List of publications:

Random-Edge is slower than Random-Facet on abstract cubes (pdf)
Thomas Dueholm Hansen and Uri Zwick
To appear in ICALP 2016.

Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made (pdf, slides)
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams
To appear in STOC 2016.

Subtree Isomorphism Revisited (pdf)
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Or Zamir
SODA 2016.

Hollow Heaps (pdf, slides)
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, and Uri Zwick
ICALP 2015.

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm (pdf, slides)
Thomas Dueholm Hansen and Uri Zwick
STOC 2015.

Random-Facet and Random-Bland require subexponential time even for shortest paths (pdf)
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick
Manuscript, 2014.

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles (pdf, slides)
Thomas Dueholm Hansen, Haim Kaplan, and Uri Zwick
SODA 2014.

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes (pdf, slides)
Thomas Dueholm Hansen, Mike Paterson, and Uri Zwick
SODA 2014.

A faster algorithm for solving one-clock priced timed games (pdf)
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, and Peter Bro Miltersen
CONCUR 2013.

The complexity of interior point methods for solving discounted turn-based stochastic games (pdf, slides)
Thomas Dueholm Hansen and Rasmus Ibsen-Jensen
CiE 2013.

Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor (pdf, slides)
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick
Journal of the ACM, 60(1):1-16, 2013.

Worst-case Analysis of Strategy Iteration and the Simplex Method (pdf)
Thomas Dueholm Hansen
PhD Dissertation, Aarhus University, 2012.

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm (pdf, older version with full proofs, slides)
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick
STOC 2011, co-winner of the best paper award.

A subexponential lower bound for the Random Facet algorithm for Parity Games (pdf, slides, errata)
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick
SODA 2011.

Lower bounds for Howard's algorithm for finding Minimum Mean-Cost Cycles (pdf, slides)
Thomas Dueholm Hansen and Uri Zwick
ISAAC 2010.

On Acyclicity of Games with Cycles (pdf, slides)
Daniel Andersson, Vladimir Gurvich, and Thomas Dueholm Hansen
Discrete Applied Mathematics, 158(10):1049-1063, 2010.

Improved Bounds for Facility Location Games with Fair Cost Allocation (pdf)
Thomas Dueholm Hansen and Orestis A. Telelis
COCOA 2009.

Approximability and Parameterized Complexity of Minmax Values (pdf)
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen
WINE 2008.

On Pure and (approximate) Strong Equilibria of Facility Location Games (pdf, slides)
Thomas Dueholm Hansen and Orestis A. Telelis
WINE 2008.

On Range of Skill (pdf, slides)
Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen
AAAI 2008.


I lectured on the simplex algorithm and the Hirsch conjecture at the MADALGO & CTIC Summer School on High-dimensional Geometric Computing: Lecture 1, Lecture 2, Lecture 3.

I have made a small collection of interesting links on twitter.