Kristoffer Arnsfelt Hansen

Online Publications

Please do contact me if you would like a copy of a paper not available as a link below.

The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form.
SAGT 2014, to appear.

Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma M. N., Sven Skyum, and Navid Talebanfard
Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth
MFCS 2014, to appear.

Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii
Polynomial threshold functions and Boolean threshold circuits

Patience of Matrix Games

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, and Elad Verbin
Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques

Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák and Emanuele Viola
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen and Peter Bro Miltersen
The complexity of solving reachability games using value and strategy iteration
Theory of Computing Systems, Volume 55, Issue 2.

Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen and Denis Thérien
Learning Read-Constant Polynomials of Constant Degree Modulo Composites
Theory of Computing Systems, Volume 55, Issue 2.

Exact algorithms for solving stochastic games

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen and Troels Bjerre Sørensen
The computational complexity of trembling hand perfection and other equilibrium refinements

László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii and Xiaoming Sun
Weights of Exact Threshold Functions

Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii,
Exact Threshold Circuits

Kristoffer Arnsfelt Hansen, Oded Lachish and Peter Bro Miltersen
Hilbert's thirteenth problem and circuit complexity.

Kristoffer Arnsfelt Hansen
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates.

Kristoffer Arnsfelt Hansen, Michal Koucký and Peter Bro Miltersen
Winning concurrent reachability games requires doubly-exponential patience.

Kristoffer Arnsfelt Hansen and Michal Koucký
A new characterization of ACC0 and probabilistic CC0.

Approximability and Parameterized Complexity of Minmax Values.

Kristoffer Arnsfelt Hansen
Constant Width Planar Branching Programs Characterize ACC0 in Quasipolynomial Size.

Deterministic Graphical Games Revisited.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen and Troels Bjerre Sørensen
Finding Equilibria in Games of No Chance.

Kristoffer Arnsfelt Hansen
Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates.

Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen and Irit Katriel
Dynamic Matchings in Convex Bipartite Graphs

Kristoffer Arnsfelt Hansen
Constant Width and Constant Depth Computation
PhD Dissertation, PD-06-13, 2006.

Kristoffer Arnsfelt Hansen
Lower Bounds for Circuits with Few Modular Gates using Exponential Sums
Note, 2006.

Kristoffer Arnsfelt Hansen
On Modular Counting with Polynomials.

Arkadev Chattopadhyay and Kristoffer Arnsfelt Hansen
Lower Bounds for Circuits With Few Modular and Symmetric Gates.

Kristoffer Arnsfelt Hansen and Peter Bro Miltersen
Some meet-in-the-middle circuit lower bounds.

Kristoffer Arnsfelt Hansen
Constant width planar computation characterizes ACC0.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen and V Vinay
Circuits on Cylinders.

Valid HTML 4.01!