11 papers
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,…