Kristoffer Arnsfelt Hansen

According to our database, Kristoffer Arnsfelt Hansen authored at least 55 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship.

Ioannis Caragiannis, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, Zihan Tan

Math. Program., January, 2024

2023

The Big Match with a Clock and a Bit of Memory.

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Abraham Neyman

Math. Oper. Res., February, 2023

PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization.

Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender

CoRR, 2023

On the complexity of Pareto-optimal and envy-free lotteries.

Ioannis Caragiannis, Kristoffer Arnsfelt Hansen, Nidhi Rathi

CoRR, 2023

Computational Complexity of Decision Problems About Nash Equilibria in Win-Lose Multi-player Games.

Vittorio Bilò, Kristoffer Arnsfelt Hansen, Marios Mavronicolas

Proceedings of the Algorithmic Game Theory - 16th International Symposium, 2023

2022

On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria.

Marie Louisa Tølbøll Berthelsen, Kristoffer Arnsfelt Hansen

Theory Comput. Syst., 2022

2021

Absorbing games with a clock and two bits of memory.

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Abraham Neyman

Games Econ. Behav., 2021

Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem.

Eleni Batziou, Kristoffer Arnsfelt Hansen, Kasper Høgh

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

FIXP-membership via Convex Optimization: Games, Cakes, and Markets.

Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Computational Complexity of Computing a Quasi-Proper Equilibrium.

Kristoffer Arnsfelt Hansen, Troels Bjerre Lund

Proceedings of the Fundamentals of Computation Theory - 23rd International Symposium, 2021

Computational Complexity of Multi-player Evolutionarily Stable Strategies.

Manon Blanc, Kristoffer Arnsfelt Hansen

Proceedings of the Computer Science - Theory and Applications, 2021

2020

Existential Theory of the Reals Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games.

Kristoffer Arnsfelt Hansen, Steffan Christ Sølvsten

CoRR, 2020

∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games.

Kristoffer Arnsfelt Hansen, Steffan Christ Sølvsten

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games.

Kristoffer Arnsfelt Hansen

Theory Comput. Syst., 2019

A Stay-in-a-Set Game without a Stationary Equilibrium.

Kristoffer Arnsfelt Hansen, Mikhail A. Raskin

Proceedings of the Proceedings Tenth International Symposium on Games, 2019

2018

Computational Complexity of Proper Equilibrium.

Kristoffer Arnsfelt Hansen, Troels Bjerre Lund

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations.

Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, Yuchen Zhou

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017

Computation of Stackelberg Equilibria of Finite Sequential Games.

Branislav Bosanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Troels Bjerre Lund, Peter Bro Miltersen

ACM Trans. Economics and Comput., 2017

Strategy Complexity of Concurrent Safety Games.

Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

The Big Match in Small Space.

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký

CoRR, 2016

The Big Match in Small Space - (Extended Abstract).

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký

Proceedings of the Algorithmic Game Theory - 9th International Symposium, 2016

2015

On Low Rank Approximation of Binary Matrices.

Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, Yuchen Zhou

CoRR, 2015

Strategy Complexity of Concurrent Stochastic Games with Safety and Reachability Objectives.

Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen

CoRR, 2015

2014

The Complexity of Solving Reachability Games Using Value and Strategy Iteration.

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen

Theory Comput. Syst., 2014

Learning Read-Constant Polynomials of Constant Degree Modulo Composites.

Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien

Theory Comput. Syst., 2014

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form.

Kousha Etessami, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth.

Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum, Navid Talebanfard

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Polynomial threshold functions and Boolean threshold circuits.

Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2013

Patience of matrix games.

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias P. Tsigaridas

Discret. Appl. Math., 2013

2012

Deterministic Graphical Games Revisited.

Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

J. Log. Comput., 2012

Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques.

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

Electron. Colloquium Comput. Complex., 2012

Exact Algorithms for Solving Stochastic Games

Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas

CoRR, 2012

Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques.

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

2011

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.

Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

Exact algorithms for solving stochastic games: extended abstract.

Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

A New Characterization of ACC⁰ and Probabilistic CC⁰.

Kristoffer Arnsfelt Hansen, Michal Koucký

Comput. Complex., 2010

The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

Weights of Exact Threshold Functions.

László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Exact Threshold Circuits.

Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Winning Concurrent Reachability Games Requires Doubly-Exponential Patience.

Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

Hilbert's Thirteenth Problem and Circuit Complexity.

Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

Approximability and Parameterized Complexity of Minmax Values.

Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

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

Kristoffer Arnsfelt Hansen

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size.

Kristoffer Arnsfelt Hansen

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Simple Recursive Games

Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

CoRR, 2007

Dynamic Matchings in Convex Bipartite Graphs.

Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Finding Equilibria in Games of No Chance.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

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

Kristoffer Arnsfelt Hansen

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

Constant Width Planar Computation Characterizes ACC⁰.

Kristoffer Arnsfelt Hansen

Theory Comput. Syst., 2006

Lower Bounds for Circuits with Few Modular Gates using Exponential Sums.

Kristoffer Arnsfelt Hansen

Electron. Colloquium Comput. Complex., 2006

Circuits on cylinders.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay

Comput. Complex., 2006

On Modular Counting with Polynomials.

Kristoffer Arnsfelt Hansen

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Lower Bounds for Circuits with Few Modular and Symmetric Gates.

Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

Some Meet-in-the-Middle Circuit Lower Bounds.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003

Constant width planar computation characterizes ACC0

Kristoffer Arnsfelt Hansen

Electron. Colloquium Comput. Complex., 2003