20 citations · 62 across the 23 of their papers we have counts for
30 papers
The Complexity of Games with Randomised Control
Sarvin Bahmani, Rasmus Ibsen-Jensen, Soumyajit Paul +5
We study the complexity of solving two-player infinite duration games played on a fixed finite graph, where the control of a node is not predetermined but rather assigned randomly.…
Stochastic Games with Limited Public Memory
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Abraham Neyman
We study the memory resources required for near-optimal play in two-player zero-sum stochastic games with the long-run average payoff. Although optimal strategies may not exist in…
The Power of Counting Steps in Quantitative Games
Sougata Bose, Rasmus Ibsen-Jensen, David Purser +2
We study deterministic games of infinite duration played on graphs and focus on the strategy complexity of quantitative objectives. Such games are known to admit optimal memoryless…
Bounded-Memory Strategies in Partial-Information Games
Sougata Bose, Rasmus Ibsen-Jensen, Patrick Totzke
We study the computational complexity of solving stochastic games with mean-payoff objectives. Instead of identifying special classes in which simple strategies are sufficient to p…
Games on Graphs: From Logic and Automata to Algorithms
Nathanaël Fijalkow, C. Aiswarya, Guy Avni +22
The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared…
Simplified Game of Life: Algorithms and Complexity
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker +1
Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A…
Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis
Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen +1
Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointer…
One-Clock Priced Timed Games are PSPACE-hard
John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani
The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponen…
All-Pay Bidding Games on Graphs
Guy Avni, Rasmus Ibsen-Jensen, Josef Tkadlec
In this paper we introduce and study {\em all-pay bidding games}, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in…
Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen +1
Crypto-currencies are digital assets designed to work as a medium of exchange, e.g., Bitcoin, but they are susceptible to attacks (dishonest behavior of participants). A framework…
Infinite-Duration Poorman-Bidding Games
Guy Avni, Thomas A. Henzinger, Rasmus Ibsen-Jensen
In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner or payoff of the game. Such games are central in fo…
Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Martin A. Nowak
Evolutionary graph theory studies the evolutionary dynamics in a population structure given as a connected graph. Each node of the graph represents an individual of the population,…
A short proof of correctness of the quasi-polynomial time algorithm for parity games
Hugo Gimbert, Rasmus Ibsen-Jensen
Recently Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan proposed a quasi-polynomial time algorithm for parity games. This paper proposes a short pr…
The Big Match in Small Space
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký
In this paper we study how to play (stochastic) games optimally using little space. We focus on repeated games with absorbing states, a type of two-player, zero-sum concurrent mean…
Robust Draws in Balanced Knockout Tournaments
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Josef Tkadlec
Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decision-making and elections. The traditional computational question, that asks to compute…
Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components
Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen +1
We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations…
Strategy Complexity of Concurrent Stochastic Games with Safety and Reachability Objectives
Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen
We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of…
Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Andreas Pavlogiannis
We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio pr…
Edit Distance for Pushdown Automata
Krishnendu Chatterjee, Thomas A. Henzinger, Rasmus Ibsen-Jensen +1
The edit distance between two words is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform to . The…
Faster Algorithms for Algebraic Path Properties in RSMs with Constant Treewidth
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Andreas Pavlogiannis +1
Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias analysis, constant propagation, etc. Recursive state machines (RSMs) are s…
The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games
Krishnendu Chatterjee, Rasmus Ibsen-Jensen
We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a…
Qualitative Analysis of Concurrent Mean-payoff Games
Krishnendu Chatterjee, Rasmus Ibsen-Jensen
We consider concurrent games played by two-players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the join…
Generalized Risk-Aversion in Stochastic Multi-Armed Bandits
Alexander Zimin, Rasmus Ibsen-Jensen, Krishnendu Chatterjee
We consider the problem of minimizing the regret in stochastic multi-armed bandit, when the measure of goodness of an arm is not the mean return, but some general function of the m…
The Complexity of Ergodic Mean-payoff Games
Krishnendu Chatterjee, Rasmus Ibsen-Jensen
We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state graph. We focus on the important sub-class of ergodic games where all states are visited infini…