Approximability and Parameterized Complexity of Minmax Values ⋆ (2009)
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We consider approximating the minmax value of a multiplayer game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of ɛ...
Deterministic Graphical Games Revisited ⋆ (2008)
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We revisit the deterministic graphical games of Washburn. A deterministic graphical game can be described as a simple stochastic game (a notion due to Anne Condon), except that we allow...
Approximability and parameterized complexity of minmax values (2008)
Hansen, Kristoffer Arnsfelt, Hansen, Thomas Dueholm, Miltersen, Peter Bro, Sørensen, Troels Bjerre
We consider approximating the minmax value of a multi-player game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of epsilon log...
Dynamic Matchings in Convex Bipartite Graphs (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel
Abstract. We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V, E) under a set of update operations which includes insertions and deletions of vertices and...
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We define the class of simple recursive games. A simple recursive game is defined as a simple stochastic game (a notion due to Anne Condon), except that we allow arbitrary real payoffs but...
Dynamic Matchings in Convex Bipartite Graphs (2008)
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel
Abstract. We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V, E) under a set of update operations which includes insertions and deletions of vertices and...
Finding Equilibria in Games of No Chance (2008)
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We consider finding maximin strategies and equilibria of explicitly given extensive form games with imperfect information but with no moves of chance. We show that a maximin pure strategy...
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates (2008)
We consider the class of constant depth AND/OR circuits augmented with a layer of modular counting gates at the bottom layer, i.e ${AC}^0 circ {MOD}_m$ circuits. We show that the following holds for...
Andersson, Daniel, Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Sorensen, Troels Bjerre
We define the class of "simple recursive games". A simple recursive game is defined as a simple stochastic game (a notion due to Anne Condon), except that we allow arbitrary real payoffs but disallow...
Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Vinay, V
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching pro-grams. We show that every function computed by a...
Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Vinay, V
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching pro-grams. We show that every function computed by a...
Lower Bounds for Circuits With Few Modular and Symmetric Gates (2005)
Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen
circuits augmented with s MODm gates must have size n\Omega ( 1s log 1r-1 n) to compute MAJORITY or MODl, if l has a prime factor not dividing m. For proving the latter result we introduce a new...
Lower Bounds for Circuits with Few Modular Gates using Exponential Sums (2005)
We prove that any AC 0 circuit augmented with ɛ log 2 n MODm gates and with a MAJORITY gate at the output, require size n Ω(log n) to compute MODl, when l has a prime factor not dividing m and ɛ...
Some Meet-in-the-Middle Circuit Lower Bounds (2004)
Kristoffer Arnsfelt Hansen, Kristo#er Arnsfelt Hansen, Peter Bro Miltersen
We observe that a combination of known top-down and bottom-up lower bound techniques of circuit complexity may yield new circuit lower bounds.
Some meet-in-the-middle circuit lower bounds (2004)
Abstract We observe that a combination of known top-down and bottom-up lower bound techniques of circuit complexity may yield new circuit lower bounds. An important example is this: Razborov and...
This document in subdirectoryRS/02/50/ Circuits on Cylinders (2002)
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay, Copyright C, Kristoffer Arnsfelt Hansen, Peter Bro, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...