2023
Hansen, K. A., Ibsen-Jensen, R., & Neyman, A. (2022). The Big Match with a Clock and a Bit of Memory. MATHEMATICS OF OPERATIONS RESEARCH. doi:10.1287/moor.2022.1267DOI: 10.1287/moor.2022.1267
Games on Graphs. (Journal article)
Fijalkow, N., Bertrand, N., Bouyer-Decitre, P., Brenguier, R., Carayol, A., Fearnley, J., . . . Skomra, M. (2023). Games on Graphs.. CoRR, abs/2305.10546.
2022
Chatterjee, K., Ibsen-Jensen, R., Jecker, I., & Svoboda, J. (2022). Complexity of Spatial Games. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 250. doi:10.4230/LIPIcs.FSTTCS.2022.11DOI: 10.4230/LIPIcs.FSTTCS.2022.11
2021
Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2021). Quantitative Verification on Product Graphs of Small Treewidth. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 213. doi:10.4230/LIPIcs.FSTTCS.2021.42DOI: 10.4230/LIPIcs.FSTTCS.2021.42
Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (n.d.). Faster algorithms for quantitative verification in bounded treewidth graphs. Formal Methods in System Design. doi:10.1007/s10703-021-00373-5DOI: 10.1007/s10703-021-00373-5
Hansen, K. A., Ibsen-Jensen, R., & Neyman, A. (2021). Absorbing games with a clock and two bits of memory. Games and Economic Behavior, 128, 213-230. doi:10.1016/j.geb.2021.04.008DOI: 10.1016/j.geb.2021.04.008
2020
Chatterjee, K., Ibsen-Jensen, R., Jecker, I., & Svoboda, J. (2020). Simplified game of life: Algorithms and complexity. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 170. doi:10.4230/LIPIcs.MFCS.2020.22DOI: 10.4230/LIPIcs.MFCS.2020.22
Fearnley, J., Ibsen-Jensen, R., & Savani, R. (2020). One-Clock Priced Timed Games are PSPACE-hard. LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Retrieved from http://arxiv.org/abs/2001.04458v2
Avni, G., Ibsen-Jensen, R., & Tkadlec, J. (2020). All-Pay Bidding Games on Graphs. THIRTY-FOURTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THE THIRTY-SECOND INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE AND THE TENTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 34, 1798-1805. Retrieved from https://www.webofscience.com/
All-Pay Bidding Games on Graphs. (Conference Paper)
Avni, G., Ibsen-Jensen, R., & Tkadlec, J. (2020). All-Pay Bidding Games on Graphs.. In AAAI (pp. 1798-1805). AAAI Press. Retrieved from https://ojs.aaai.org/index.php/AAAI/issue/view/249
Fearnley, J., Ibsen-Jensen, R., & Savani, R. (2020). One-Clock Priced Timed Games are PSPACE-hard.. In H. Hermanns, L. Zhang, N. Kobayashi, & D. Miller (Eds.), LICS (pp. 397-409). ACM. Retrieved from https://doi.org/10.1145/3373718
Optimal and Perfectly Parallel Algorithms for On-demand Data-Flow Analysis. (Conference Paper)
Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2020). Optimal and Perfectly Parallel Algorithms for On-demand Data-Flow Analysis.. In P. Müller (Ed.), ESOP Vol. 12075 (pp. 112-140). Springer. Retrieved from https://doi.org/10.1007/978-3-030-44914-8
Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2020). Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis. PROGRAMMING LANGUAGES AND SYSTEMS ( ESOP 2020), 12075, 112-140. doi:10.1007/978-3-030-44914-8_5DOI: 10.1007/978-3-030-44914-8_5
2019
Chatterjee, K., Goharshady, A. K., Goyal, P., Ibsen-Jensen, R., & Pavlogiannis, A. (2019). Faster Algorithms for Dynamic Algebraic Queries in Basic RSMs with Constant Treewidth. ACM Transactions on Programming Languages and Systems, 41(4). doi:10.1145/3363525DOI: 10.1145/3363525
Avni, G., Henzinger, T. A., Ibsen-Jensen, R., & Novotný, P. (2019). Bidding Games on Markov Decision Processes. In Unknown Conference (pp. 1-12). Springer International Publishing. doi:10.1007/978-3-030-30806-3_1DOI: 10.1007/978-3-030-30806-3_1
2018
Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., & Pavlogiannis, A. (2018). Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. ACM Transactions on Programming Languages and Systems, 40(3). doi:10.1145/3210257DOI: 10.1145/3210257
Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Velner, Y. (2018). Ergodic mean-payo games for the analysis of attacks in crypto-currencies. Leibniz International Proceedings in Informatics, LIPIcs, 118. doi:10.4230/LIPIcs.CONCUR.2018.11DOI: 10.4230/LIPIcs.CONCUR.2018.11
Hansen, K. A., Ibsen-Jensen, R., & Neyman, A. (2018). The Big Match with a Clock and a Bit of Memory. In ACM EC'18: PROCEEDINGS OF THE 2018 ACM CONFERENCE ON ECONOMICS AND COMPUTATION (pp. 149-150). doi:10.1145/3219166.3219198DOI: 10.1145/3219166.3219198
Avni, G., Henzinger, T. A., & Ibsen-Jensen, R. (2018). Infinite-Duration Poorman-Bidding Games. WEB AND INTERNET ECONOMICS, WINE 2018, 11316, 21-36. doi:10.1007/978-3-030-04612-5_2DOI: 10.1007/978-3-030-04612-5_2
Infinite-Duration Poorman-Bidding Games. (Conference Paper)
Avni, G., Henzinger, T. A., & Ibsen-Jensen, R. (2018). Infinite-Duration Poorman-Bidding Games.. In G. Christodoulou, & T. Harks (Eds.), WINE Vol. 11316 (pp. 21-36). Springer. Retrieved from https://doi.org/10.1007/978-3-030-04612-5
Ibsen-Jensen, R., Tkadlec, J., Chatterjee, K., & Nowak, M. A. (2018). Language acquisition with communication between learners. JOURNAL OF THE ROYAL SOCIETY INTERFACE, 15(140). doi:10.1098/rsif.2018.0073DOI: 10.1098/rsif.2018.0073
2017
Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. A. (2017). Faster Monte-Carlo algorithms for fixation probability of the moran process on undirected graphs. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 83. doi:10.4230/LIPIcs.MFCS.2017.61DOI: 10.4230/LIPIcs.MFCS.2017.61
Chatterjee, K., Hansen, K. A., & Ibsen-Jensen, R. (2017). Strategy complexity of concurrent safety games. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 83. doi:10.4230/LIPIcs.MFCS.2017.55DOI: 10.4230/LIPIcs.MFCS.2017.55
Gimbert, H., & Ibsen-Jensen, R. (2017). A short proof of correctness of the quasi-polynomial time algorithm for parity games.. CoRR, abs/1702.01953.
2016
Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2016). Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 57. doi:10.4230/LIPIcs.ESA.2016.28DOI: 10.4230/LIPIcs.ESA.2016.28
Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components (Conference Paper)
Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2016). Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. In ACM SIGPLAN NOTICES Vol. 51 (pp. 733-747). doi:10.1145/2914770.2837624DOI: 10.1145/2914770.2837624
Algorithms for algebraic path properties in concurrent systems of constant treewidth components (Conference Paper)
Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2016). Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM. doi:10.1145/2837614.2837624DOI: 10.1145/2837614.2837624
Chatterjee, K., Ibsen-Jensen, R., & Tkadlec, J. (2016). Robust draws in balanced knockout tournaments. In IJCAI International Joint Conference on Artificial Intelligence Vol. 2016-January (pp. 172-179).
Hansen, K. A., Ibsen-Jensen, R., & Koucky, M. (2016). The Big Match in Small Space (Extended Abstract). In ALGORITHMIC GAME THEORY, SAGT 2016 Vol. 9928 (pp. 64-76). doi:10.1007/978-3-662-53354-3_6DOI: 10.1007/978-3-662-53354-3_6
Chatterjee, K., & Ibsen-Jensen, R. (2016). The Complexity of Deciding Legality of a Single Step of Magic: The Gathering. In ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE Vol. 285 (pp. 1432-1439). doi:10.3233/978-1-61499-672-9-1432DOI: 10.3233/978-1-61499-672-9-1432
2015
Ibsen-Jensen, R., Chatterjee, K., & Nowak, M. A. (2015). Computational complexity of ecological and evolutionary spatial dynamics. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 112(51), 15636-15641. doi:10.1073/pnas.1511366112DOI: 10.1073/pnas.1511366112
Qualitative analysis of concurrent mean-payoff games (Journal article)
Chatterjee, K., & Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean-payoff games. INFORMATION AND COMPUTATION, 242, 2-24. doi:10.1016/j.ic.2015.03.009DOI: 10.1016/j.ic.2015.03.009
Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth (Journal article)
Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A., & Goyal, P. (2015). Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth. ACM SIGPLAN Notices, 50(1), 97-109. doi:10.1145/2775051.2676979DOI: 10.1145/2775051.2676979
Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A., & Goyal, P. (2015). Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth. ACM SIGPLAN NOTICES, 50(1), 97-109. doi:10.1145/2775051.2676979DOI: 10.1145/2775051.2676979
Edit Distance for Pushdown Automata (Chapter)
Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit Distance for Pushdown Automata. In Automata, Languages, and Programming (pp. 121-133). Springer Berlin Heidelberg. doi:10.1007/978-3-662-47666-6_10DOI: 10.1007/978-3-662-47666-6_10
Edit distance for pushdown automata (Journal article)
Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit Distance for Pushdown Automata. Automata, Languages, and Programming, 9135, 121-133. doi:10.1007/978-3-662-47666-6_10DOI: 10.23638/LMCS-13(3:23)2017
Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. In COMPUTER AIDED VERIFICATION, PT I Vol. 9206 (pp. 140-157). doi:10.1007/978-3-319-21690-4_9DOI: 10.1007/978-3-319-21690-4_9
Chatterjee, K., & Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean-payoff games.. Inf. Comput., 242, 2-24. doi:10.1016/j.ic.2015.03.009DOI: 10.1016/j.ic.2015.03.009
Chatterjee, K., & Ibsen-Jensen, R. (2015). The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973730.69DOI: 10.1137/1.9781611973730.69
2014
Edit distance for timed automata (Conference Paper)
Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2014). Edit distance for timed automata. In Proceedings of the 17th international conference on Hybrid systems: computation and control. ACM. doi:10.1145/2562059.2562141DOI: 10.1145/2562059.2562141
Faster Algorithms for Algebraic Path Properties in RSMs with Constant Treewidth. (Journal article)
Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A., & Goyal, P. (2014). Faster Algorithms for Algebraic Path Properties in RSMs with Constant Treewidth.. CoRR, abs/1410.7724.
Generalized Risk-Aversion in Stochastic Multi-Armed Bandits. (Journal article)
Zimin, A., Ibsen-Jensen, R., & Chatterjee, K. (2014). Generalized Risk-Aversion in Stochastic Multi-Armed Bandits.. CoRR, abs/1405.0833.
The Complexity of Ergodic Mean-payoff Games (Conference Paper)
Chatterjee, K., & Ibsen-Jensen, R. (2014). The Complexity of Ergodic Mean-payoff Games. In AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT II Vol. 8573 (pp. 122-133). Retrieved from https://www.webofscience.com/
The Complexity of Ergodic Mean-payoff Games. (Journal article)
Chatterjee, K., & Ibsen-Jensen, R. (2014). The Complexity of Ergodic Mean-payoff Games.. CoRR, abs/1404.5734.
The Complexity of Solving Reachability Games Using Value and Strategy Iteration (Journal article)
Hansen, K. A., Ibsen-Jensen, R., & Miltersen, P. B. (2014). The Complexity of Solving Reachability Games Using Value and Strategy Iteration. THEORY OF COMPUTING SYSTEMS, 55(2), 380-403. doi:10.1007/s00224-013-9524-6DOI: 10.1007/s00224-013-9524-6
2013
Patience of matrix games (Journal article)
Hansen, K. A., Ibsen-Jensen, R., Podolskii, V. V., & Tsigaridas, E. (2013). Patience of matrix games. Discrete Applied Mathematics, 161(16-17), 2440-2459. doi:10.1016/j.dam.2013.05.008DOI: 10.1016/j.dam.2013.05.008
A Faster Algorithm for Solving One-Clock Priced Timed Games (Conference Paper)
Hansen, T. D., Ibsen-Jensen, R., & Miltersen, P. B. (2013). A Faster Algorithm for Solving One-Clock Priced Timed Games. In Unknown Conference (pp. 531-545). Springer Berlin Heidelberg. doi:10.1007/978-3-642-40184-8_37DOI: 10.1007/978-3-642-40184-8_37
The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games (Conference Paper)
Hansen, T. D., & Ibsen-Jensen, R. (2013). The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games. In Unknown Conference (pp. 252-262). Springer Berlin Heidelberg. doi:10.1007/978-3-642-39053-1_29DOI: 10.1007/978-3-642-39053-1_29
Strategy Complexity of Finite-Horizon Markov Decision Processes and Simple Stochastic Games (Conference Paper)
Chatterjee, K., & Ibsen-Jensen, R. (2013). Strategy Complexity of Finite-Horizon Markov Decision Processes and Simple Stochastic Games. In Unknown Conference (pp. 106-117). Springer Berlin Heidelberg. doi:10.1007/978-3-642-36046-6_11DOI: 10.1007/978-3-642-36046-6_11
2012
Solving Simple Stochastic Games with Few Coin Toss Positions (Conference Paper)
Ibsen-Jensen, R., & Miltersen, P. B. (2012). Solving Simple Stochastic Games with Few Coin Toss Positions. In ALGORITHMS - ESA 2012 Vol. 7501 (pp. 636-647). Retrieved from https://www.webofscience.com/
2011
The Complexity of Solving Reachability Games Using Value and Strategy Iteration (Conference Paper)
Hansen, K. A., Ibsen-Jensen, R., & Miltersen, P. B. (2011). The Complexity of Solving Reachability Games Using Value and Strategy Iteration. In Unknown Conference (pp. 77-90). Springer Berlin Heidelberg. doi:10.1007/978-3-642-20712-9_7DOI: 10.1007/978-3-642-20712-9_7
