Please note that IST Research Explorer no longer supports Internet Explorer versions 8 or 9 (or earlier).
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.
356 Publications
2019 | Journal Article | IST-REx-ID: 7158 |

Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth
K. Chatterjee, A.K. Goharshady, P. Goyal, R. Ibsen-Jensen, A. Pavlogiannis, ACM Transactions on Programming Languages and Systems 41 (2019).
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, P. Goyal, R. Ibsen-Jensen, A. Pavlogiannis, ACM Transactions on Programming Languages and Systems 41 (2019).
2019 | Conference Paper | IST-REx-ID: 7183 |

Deciding fast termination for probabilistic VASS with nondeterminism
T. Brázdil, K. Chatterjee, A. Kucera, P. Novotný, D. Velan, in:, International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2019, pp. 462–478.
View
| DOI
| Download Preprint (ext.)
| arXiv
T. Brázdil, K. Chatterjee, A. Kucera, P. Novotný, D. Velan, in:, International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2019, pp. 462–478.
2019 | Journal Article | IST-REx-ID: 7210 |

Population structure determines the tradeoff between fixation probability and fixation time
J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Communications Biology 2 (2019).
View
| Files available
| DOI
| PubMed | Europe PMC
J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Communications Biology 2 (2019).
2019 | Conference Paper | IST-REx-ID: 7402 |

Graph planning with expected finite horizon
K. Chatterjee, L. Doyen, in:, 34th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2019, pp. 1–13.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, L. Doyen, in:, 34th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2019, pp. 1–13.
2019 | Preprint | IST-REx-ID: 7950 |

Token swapping on trees
A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).
View
| Files available
| Download Preprint (ext.)
| arXiv
A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).
2019 | Conference Paper | IST-REx-ID: 5948
Termination of nondeterministic probabilistic programs
H. Fu, K. Chatterjee, in:, International Conference on Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2019, pp. 468–490.
View
| DOI
| Download Preprint (ext.)
| arXiv
H. Fu, K. Chatterjee, in:, International Conference on Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2019, pp. 468–490.
2019 | Conference Paper | IST-REx-ID: 6056 |

Probabilistic smart contracts: Secure randomness on the blockchain
K. Chatterjee, A.K. Goharshady, A. Pourdamghani, in:, IEEE International Conference on Blockchain and Cryptocurrency, IEEE, 2019.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, A.K. Goharshady, A. Pourdamghani, in:, IEEE International Conference on Blockchain and Cryptocurrency, IEEE, 2019.
2019 | Conference Paper | IST-REx-ID: 6175 |

Cost analysis of nondeterministic probabilistic programs
P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2019, pp. 204–220.
View
| Files available
| DOI
| arXiv
P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2019, pp. 204–220.
2019 | Conference Paper | IST-REx-ID: 6378 |

Hybrid Mining: Exploiting blockchain’s computational power for distributed problem solving
K. Chatterjee, A.K. Goharshady, A. Pourdamghani, in:, Proceedings of the 34th ACM Symposium on Applied Computing, ACM, 2019, pp. 374–381.
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, A. Pourdamghani, in:, Proceedings of the 34th ACM Symposium on Applied Computing, ACM, 2019, pp. 374–381.
2019 | Journal Article | IST-REx-ID: 6380 |

Efficient parameterized algorithms for data packing
K. Chatterjee, A.K. Goharshady, N. Okati, A. Pavlogiannis, Proceedings of the ACM on Programming Languages 3 (2019).
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, N. Okati, A. Pavlogiannis, Proceedings of the ACM on Programming Languages 3 (2019).
2019 | Conference Paper | IST-REx-ID: 6462 |

Run-time optimization for learned controllers through quantitative games
G. Avni, R. Bloem, K. Chatterjee, T.A. Henzinger, B. Konighofer, S. Pranger, in:, 31st International Conference on Computer-Aided Verification, Springer, 2019, pp. 630–649.
View
| Files available
| DOI
G. Avni, R. Bloem, K. Chatterjee, T.A. Henzinger, B. Konighofer, S. Pranger, in:, 31st International Conference on Computer-Aided Verification, Springer, 2019, pp. 630–649.
2019 | Conference Paper | IST-REx-ID: 6490 |

The treewidth of smart contracts
K. Chatterjee, A.K. Goharshady, E.K. Goharshady, in:, Proceedings of the 34th ACM Symposium on Applied Computing, ACM, n.d., pp. 400–408.
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, E.K. Goharshady, in:, Proceedings of the 34th ACM Symposium on Applied Computing, ACM, n.d., pp. 400–408.
2019 | Conference Paper | IST-REx-ID: 6780 |

Modular verification for almost-sure termination of probabilistic programs
M. Huang, H. Fu, K. Chatterjee, A.K. Goharshady, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications , ACM, 2019.
View
| Files available
| DOI
| arXiv
M. Huang, H. Fu, K. Chatterjee, A.K. Goharshady, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications , ACM, 2019.
2019 | Journal Article | IST-REx-ID: 6836 |

Social dilemmas among unequals
O.P. Hauser, C. Hilbe, K. Chatterjee, M.A. Nowak, Nature 572 (2019) 524–527.
View
| Files available
| DOI
O.P. Hauser, C. Hilbe, K. Chatterjee, M.A. Nowak, Nature 572 (2019) 524–527.
2019 | Conference Paper | IST-REx-ID: 6884 |

Bidding mechanisms in graph games
G. Avni, T.A. Henzinger, D. Zikelic, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
View
| Files available
| DOI
| arXiv
G. Avni, T.A. Henzinger, D. Zikelic, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
2019 | Conference Paper | IST-REx-ID: 6885 |

Long-run average behavior of vector addition systems with states
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
2019 | Conference Paper | IST-REx-ID: 6887 |

Near-linear time algorithms for Streett objectives in graphs and MDPs
K. Chatterjee, W. Dvorák, M. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
View
| Files available
| DOI
K. Chatterjee, W. Dvorák, M. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
2019 | Conference Paper | IST-REx-ID: 6889 |

Combinations of Qualitative Winning for Stochastic Parity Games
K. Chatterjee, N. Piterman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
View
| Files available
| DOI
K. Chatterjee, N. Piterman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
2019 | Conference Paper | IST-REx-ID: 6942 |

Strategy representation by decision trees with linear classifiers
P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, V. Toman, in:, 16th International Conference on Quantitative Evaluation of Systems, Springer Nature, 2019, pp. 109–128.
View
| DOI
| Download Preprint (ext.)
| arXiv
P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, V. Toman, in:, 16th International Conference on Quantitative Evaluation of Systems, Springer Nature, 2019, pp. 109–128.
2019 | Journal Article | IST-REx-ID: 7014 |

Non-polynomial worst-case analysis of recursive programs
K. Chatterjee, H. Fu, A.K. Goharshady, ACM Transactions on Programming Languages and Systems 41 (2019).
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, H. Fu, A.K. Goharshady, ACM Transactions on Programming Languages and Systems 41 (2019).
2018 | Conference Paper | IST-REx-ID: 24 |

Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives
K. Chatterjee, A. Elgyütt, P. Novotný, O. Rouillé, in:, IJCAI, 2018, pp. 4692–4699.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, A. Elgyütt, P. Novotný, O. Rouillé, in:, IJCAI, 2018, pp. 4692–4699.
2018 | Conference Paper | IST-REx-ID: 25 |

Goal-HSVI: Heuristic search value iteration for goal-POMDPs
K. Horák, B. Bošanský, K. Chatterjee, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4764–4770.
View
| DOI
| Download Published Version (ext.)
K. Horák, B. Bošanský, K. Chatterjee, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4764–4770.
2018 | Journal Article | IST-REx-ID: 293 |

The signal-burying game can explain why we obscure positive traits and good deeds
M. Hoffman, C. Hilbe, M. Nowak, Nature Human Behaviour 2 (2018) 397–404.
View
| Files available
| DOI
M. Hoffman, C. Hilbe, M. Nowak, Nature Human Behaviour 2 (2018) 397–404.
2018 | Conference Paper | IST-REx-ID: 297 |

Strategy representation by decision trees in reactive synthesis
T. Brázdil, K. Chatterjee, J. Kretinsky, V. Toman, in:, Springer, 2018, pp. 385–407.
View
| Files available
| DOI
T. Brázdil, K. Chatterjee, J. Kretinsky, V. Toman, in:, Springer, 2018, pp. 385–407.
2018 | Book Chapter | IST-REx-ID: 86 |

Computing average response time
K. Chatterjee, T.A. Henzinger, J. Otop, in:, M. Lohstroh, P. Derler, M. Sirjani (Eds.), Principles of Modeling, Springer, 2018, pp. 143–161.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, in:, M. Lohstroh, P. Derler, M. Sirjani (Eds.), Principles of Modeling, Springer, 2018, pp. 143–161.
2018 | Journal Article | IST-REx-ID: 198 |

Language acquisition with communication between learners
R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, Journal of the Royal Society Interface 15 (2018).
View
| Files available
| DOI
R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, Journal of the Royal Society Interface 15 (2018).
2018 | Journal Article | IST-REx-ID: 2 |

Indirect reciprocity with private, noisy, and incomplete information
C. Hilbe, L. Schmid, J. Tkadlec, K. Chatterjee, M. Nowak, PNAS 115 (2018) 12241–12246.
View
| Files available
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
C. Hilbe, L. Schmid, J. Tkadlec, K. Chatterjee, M. Nowak, PNAS 115 (2018) 12241–12246.
2018 | Journal Article | IST-REx-ID: 738 |

Automated competitive analysis of real time scheduling with graph games
K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, Real-Time Systems 54 (2018) 166–207.
View
| Files available
| DOI
K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, Real-Time Systems 54 (2018) 166–207.
2018 | Conference Paper | IST-REx-ID: 79 |

Parameter-independent strategies for pMDPs via POMDPs
S. Arming, E. Bartocci, K. Chatterjee, J.P. Katoen, A. Sokolova, in:, Springer, 2018, pp. 53–70.
View
| DOI
| Download Preprint (ext.)
| arXiv
S. Arming, E. Bartocci, K. Chatterjee, J.P. Katoen, A. Sokolova, in:, Springer, 2018, pp. 53–70.
2018 | Conference Paper | IST-REx-ID: 5679 |

New approaches for almost-sure termination of probabilistic programs
M. Huang, H. Fu, K. Chatterjee, in:, S. Ryu (Ed.), Springer, 2018, pp. 181–201.
View
| DOI
| Download Preprint (ext.)
| arXiv
M. Huang, H. Fu, K. Chatterjee, in:, S. Ryu (Ed.), Springer, 2018, pp. 181–201.
2018 | Journal Article | IST-REx-ID: 5751 |

Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M.A. Nowak, Communications Biology 1 (2018).
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M.A. Nowak, Communications Biology 1 (2018).
2018 | Book Chapter | IST-REx-ID: 59
Graph games and reactive synthesis
R. Bloem, K. Chatterjee, B. Jobstmann, in:, T.A. Henzinger, E.M. Clarke, H. Veith, R. Bloem (Eds.), Handbook of Model Checking, 1st ed., Springer, 2018, pp. 921–962.
View
| DOI
R. Bloem, K. Chatterjee, B. Jobstmann, in:, T.A. Henzinger, E.M. Clarke, H. Veith, R. Bloem (Eds.), Handbook of Model Checking, 1st ed., Springer, 2018, pp. 921–962.
2018 | Conference Paper | IST-REx-ID: 5967 |

The Big Match with a clock and a bit of memory
K.A. Hansen, R. Ibsen-Jensen, A. Neyman, in:, Proceedings of the 2018 ACM Conference on Economics and Computation - EC ’18, ACM Press, 2018, pp. 149–150.
View
| Files available
| DOI
K.A. Hansen, R. Ibsen-Jensen, A. Neyman, in:, Proceedings of the 2018 ACM Conference on Economics and Computation - EC ’18, ACM Press, 2018, pp. 149–150.
2018 | Conference Paper | IST-REx-ID: 5977 |

Computational approaches for stochastic shortest path on succinct MDPs
K. Chatterjee, H. Fu, A.K. Goharshady, N. Okati, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4700–4707.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, H. Fu, A.K. Goharshady, N. Okati, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4700–4707.
2018 | Journal Article | IST-REx-ID: 5993 |

Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, ACM Transactions on Programming Languages and Systems 40 (2018).
View
| Files available
| DOI
| Download Submitted Version (ext.)
| arXiv
K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, ACM Transactions on Programming Languages and Systems 40 (2018).
2018 | Journal Article | IST-REx-ID: 6009 |

Algorithms for algebraic path properties in concurrent systems of constant treewidth components
K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, ACM Transactions on Programming Languages and Systems 40 (2018).
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, ACM Transactions on Programming Languages and Systems 40 (2018).
2018 | Conference Paper | IST-REx-ID: 6340 |

Secure Credit Reporting on the Blockchain
A.K. Goharshady, A. Behrouz, K. Chatterjee, in:, Proceedings of the IEEE International Conference on Blockchain, IEEE, 2018, pp. 1343–1348.
View
| Files available
| DOI
| arXiv
A.K. Goharshady, A. Behrouz, K. Chatterjee, in:, Proceedings of the IEEE International Conference on Blockchain, IEEE, 2018, pp. 1343–1348.
2018 | Conference Paper | IST-REx-ID: 66 |

Ergodic mean-payoff games for the analysis of attacks in crypto-currencies
K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, Y. Velner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
View
| Files available
| DOI
| arXiv
K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, Y. Velner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
2018 | Conference Paper | IST-REx-ID: 141 |

Symbolic algorithms for graphs and Markov decision processes with fairness objectives
K. Chatterjee, M. Henzinger, V. Loitzenbauer, S. Oraee, V. Toman, in:, Springer, 2018, pp. 178–197.
View
| Files available
| DOI
K. Chatterjee, M. Henzinger, V. Loitzenbauer, S. Oraee, V. Toman, in:, Springer, 2018, pp. 178–197.
2018 | Conference Paper | IST-REx-ID: 143 |

Efficient algorithms for asymptotic bounds on termination time in VASS
T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, D. Velan, F. Zuleger, in:, IEEE, 2018, pp. 185–194.
View
| DOI
| Download Preprint (ext.)
T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, D. Velan, F. Zuleger, in:, IEEE, 2018, pp. 185–194.
2018 | Journal Article | IST-REx-ID: 157 |

Evolution of cooperation in stochastic games
C. Hilbe, Š. Šimsa, K. Chatterjee, M. Nowak, Nature 559 (2018) 246–249.
View
| Files available
| DOI
C. Hilbe, Š. Šimsa, K. Chatterjee, M. Nowak, Nature 559 (2018) 246–249.
2018 | Journal Article | IST-REx-ID: 419 |

Partners and rivals in direct reciprocity
C. Hilbe, K. Chatterjee, M. Nowak, Nature Human Behaviour 2 (2018) 469–477.
View
| Files available
| DOI
C. Hilbe, K. Chatterjee, M. Nowak, Nature Human Behaviour 2 (2018) 469–477.
2018 | Journal Article | IST-REx-ID: 454 |

Crosstalk in concurrent repeated games impedes direct reciprocity and requires stronger levels of forgiveness
J. Reiter, C. Hilbe, D. Rand, K. Chatterjee, M. Nowak, Nature Communications 9 (2018).
View
| Files available
| DOI
J. Reiter, C. Hilbe, D. Rand, K. Chatterjee, M. Nowak, Nature Communications 9 (2018).
2018 | Conference Paper | IST-REx-ID: 310 |

Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety and diameter
K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, ACM, 2018, pp. 2341–2356.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, ACM, 2018, pp. 2341–2356.
2018 | Conference Paper | IST-REx-ID: 311 |

Quantitative analysis of smart contracts
K. Chatterjee, A.K. Goharshady, Y. Velner, in:, Springer, 2018, pp. 739–767.
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, Y. Velner, in:, Springer, 2018, pp. 739–767.
2018 | Conference Paper | IST-REx-ID: 325 |

Lexicographic ranking supermartingales: an efficient approach to termination of probabilistic programs
S. Agrawal, K. Chatterjee, P. Novotný, in:, ACM, 2018.
View
| DOI
| Download Preprint (ext.)
| arXiv
S. Agrawal, K. Chatterjee, P. Novotný, in:, ACM, 2018.
2018 | Conference Paper | IST-REx-ID: 34 |

Sensor synthesis for POMDPs with reachability objectives
K. Chatterjee, M. Chemlík, U. Topcu, in:, AAAI Press, 2018, pp. 47–55.
View
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chemlík, U. Topcu, in:, AAAI Press, 2018, pp. 47–55.
2018 | Conference Paper | IST-REx-ID: 35 |

Algorithms and conditional lower bounds for planning problems
K. Chatterjee, W. Dvorák, M. Henzinger, A. Svozil, in:, 28th International Conference on Automated Planning and Scheduling , AAAI Press, 2018.
View
| Download None (ext.)
| arXiv
K. Chatterjee, W. Dvorák, M. Henzinger, A. Svozil, in:, 28th International Conference on Automated Planning and Scheduling , AAAI Press, 2018.
2017 | Thesis | IST-REx-ID: 821 |

Algorithmic advances in program analysis and their applications
A. Pavlogiannis, Algorithmic Advances in Program Analysis and Their Applications, IST Austria, 2017.
View
| Files available
| DOI
A. Pavlogiannis, Algorithmic Advances in Program Analysis and Their Applications, IST Austria, 2017.
2017 | Journal Article | IST-REx-ID: 716 |

The complexity of mean-payoff pushdown games
K. Chatterjee, Y. Velner, Journal of the ACM 64 (2017) 34.
View
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, Y. Velner, Journal of the ACM 64 (2017) 34.
2017 | Journal Article | IST-REx-ID: 717 |

Hyperplane separation technique for multidimensional mean-payoff games
K. Chatterjee, Y. Velner, Journal of Computer and System Sciences 88 (2017) 236–259.
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, Y. Velner, Journal of Computer and System Sciences 88 (2017) 236–259.
2017 | Journal Article | IST-REx-ID: 719
Special issue: Synthesis and SYNT 2014
K. Chatterjee, R. Ehlers, Acta Informatica 54 (2017) 543–544.
View
| DOI
K. Chatterjee, R. Ehlers, Acta Informatica 54 (2017) 543–544.
2017 | Journal Article | IST-REx-ID: 744 |

Optional interactions and suspicious behaviour facilitates trustful cooperation in prisoners dilemma
T. Priklopil, K. Chatterjee, M. Nowak, Journal of Theoretical Biology 433 (2017) 64–72.
View
| Files available
| DOI
| PubMed | Europe PMC
T. Priklopil, K. Chatterjee, M. Nowak, Journal of Theoretical Biology 433 (2017) 64–72.
2017 | Journal Article | IST-REx-ID: 464 |

Improved algorithms for parity and Streett objectives
K. Chatterjee, M. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).
View
| Files available
| DOI
K. Chatterjee, M. Henzinger, V. Loitzenbauer, Logical Methods in Computer Science 13 (2017).
2017 | Journal Article | IST-REx-ID: 465 |

Edit distance for pushdown automata
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Logical Methods in Computer Science 13 (2017).
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Logical Methods in Computer Science 13 (2017).
2017 | Journal Article | IST-REx-ID: 466 |

Unifying two views on multiple mean-payoff objectives in Markov decision processes
K. Chatterjee, Z. Křetínská, J. Kretinsky, Logical Methods in Computer Science 13 (2017).
View
| Files available
| DOI
K. Chatterjee, Z. Křetínská, J. Kretinsky, Logical Methods in Computer Science 13 (2017).
2017 | Journal Article | IST-REx-ID: 467 |

Nested weighted automata
K. Chatterjee, T.A. Henzinger, J. Otop, ACM Transactions on Computational Logic (TOCL) 18 (2017).
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, T.A. Henzinger, J. Otop, ACM Transactions on Computational Logic (TOCL) 18 (2017).
2017 | Journal Article | IST-REx-ID: 512 |

Amplification on undirected population structures: Comets beat stars
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Scientific Reports 7 (2017).
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Scientific Reports 7 (2017).
2017 | Technical Report | IST-REx-ID: 5455 |

Optimal Dyck reachability for data-dependence and alias analysis
K. Chatterjee, B. Choudhary, A. Pavlogiannis, Optimal Dyck Reachability for Data-Dependence and Alias Analysis, IST Austria, 2017.
View
| Files available
| DOI
K. Chatterjee, B. Choudhary, A. Pavlogiannis, Optimal Dyck Reachability for Data-Dependence and Alias Analysis, IST Austria, 2017.
2017 | Technical Report | IST-REx-ID: 5456 |

Data-centric dynamic partial order reduction
M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2017.
View
| Files available
| DOI
M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2017.
2017 | Conference Paper | IST-REx-ID: 551 |

Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs
K. Chatterjee, R. Ibsen-Jensen, M. Nowak, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
View
| Files available
| DOI
K. Chatterjee, R. Ibsen-Jensen, M. Nowak, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
2017 | Conference Paper | IST-REx-ID: 552 |

Faster algorithms for mean payoff parity games
K. Chatterjee, M. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
View
| Files available
| DOI
K. Chatterjee, M. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
2017 | Conference Paper | IST-REx-ID: 553 |

Strategy complexity of concurrent safety games
K. Chatterjee, K. Hansen, R. Ibsen-Jensen, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
View
| Files available
| DOI
| Download Published Version (ext.)
K. Chatterjee, K. Hansen, R. Ibsen-Jensen, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
2017 | Research Data | IST-REx-ID: 5559 |

Strong amplifiers of natural selection
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak , (2017).
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak , (2017).
2017 | Book Chapter | IST-REx-ID: 625 |

The cost of exactness in quantitative reachability
K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017, pp. 367–381.
View
| Files available
| DOI
K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017, pp. 367–381.
2017 | Conference Paper | IST-REx-ID: 628 |

Automated recurrence analysis for almost linear expected runtime bounds
K. Chatterjee, H. Fu, A. Murhekar, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 118–139.
View
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, H. Fu, A. Murhekar, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 118–139.
2017 | Conference Paper | IST-REx-ID: 639 |

Non-polynomial worst case analysis of recursive programs
K. Chatterjee, H. Fu, A.K. Goharshady, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 41–63.
View
| Files available
| DOI
| Download Submitted Version (ext.)
| arXiv
K. Chatterjee, H. Fu, A.K. Goharshady, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 41–63.
2017 | Conference Paper | IST-REx-ID: 645 |

Value iteration for long run average reward in markov decision processes
P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, T. Meggendorfer, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 201–221.
View
| DOI
| Download Submitted Version (ext.)
P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, T. Meggendorfer, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 201–221.
2017 | Conference Paper | IST-REx-ID: 6519 |

Improved set-based symbolic algorithms for parity games
K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017.
View
| Files available
| DOI
K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017.
2017 | Journal Article | IST-REx-ID: 653 |

Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer
A. Makohon Moore, M. Zhang, J. Reiter, I. Božić, B. Allen, D. Kundu, K. Chatterjee, F. Wong, Y. Jiao, Z. Kohutek, J. Hong, M. Attiyeh, B. Javier, L. Wood, R. Hruban, M. Nowak, N. Papadopoulos, K. Kinzler, B. Vogelstein, C. Iacobuzio Donahue, Nature Genetics 49 (2017) 358–366.
View
| Files available
| DOI
A. Makohon Moore, M. Zhang, J. Reiter, I. Božić, B. Allen, D. Kundu, K. Chatterjee, F. Wong, Y. Jiao, Z. Kohutek, J. Hong, M. Attiyeh, B. Javier, L. Wood, R. Hruban, M. Nowak, N. Papadopoulos, K. Kinzler, B. Vogelstein, C. Iacobuzio Donahue, Nature Genetics 49 (2017) 358–366.
2017 | Journal Article | IST-REx-ID: 671 |

Memory-n strategies of direct reciprocity
C. Hilbe, V. Martinez, K. Chatterjee, M. Nowak, PNAS 114 (2017) 4715–4720.
View
| DOI
| Download Published Version (ext.)
| PubMed | Europe PMC
C. Hilbe, V. Martinez, K. Chatterjee, M. Nowak, PNAS 114 (2017) 4715–4720.
2017 | Journal Article | IST-REx-ID: 681 |

Doomsday equilibria for omega-regular games
K. Chatterjee, L. Doyen, E. Filiot, J. Raskin, Information and Computation 254 (2017) 296–315.
View
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, L. Doyen, E. Filiot, J. Raskin, Information and Computation 254 (2017) 296–315.
2017 | Journal Article | IST-REx-ID: 684 |

Obligation blackwell games and p-automata
K. Chatterjee, N. Piterman, Journal of Symbolic Logic 82 (2017) 420–452.
View
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, N. Piterman, Journal of Symbolic Logic 82 (2017) 420–452.
2017 | Journal Article | IST-REx-ID: 699 |

The red queen and king in finite populations
C. Veller, L. Hayward, M. Nowak, C. Hilbe, PNAS 114 (2017) E5396–E5405.
View
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
C. Veller, L. Hayward, M. Nowak, C. Hilbe, PNAS 114 (2017) E5396–E5405.
2017 | Conference Paper | IST-REx-ID: 711 |

Bidirectional nested weighted automata
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
2017 | Journal Article | IST-REx-ID: 1294 |

Trading performance for stability in Markov decision processes
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, Journal of Computer and System Sciences 84 (2017) 144–170.
View
| Files available
| DOI
T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, Journal of Computer and System Sciences 84 (2017) 144–170.
2017 | Journal Article | IST-REx-ID: 1407 |

Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.
2017 | Conference Paper | IST-REx-ID: 1009 |

Optimizing expectation with guarantees in POMDPs
K. Chatterjee, P. Novotný, G. Pérez, J. Raskin, D. Zikelic, in:, Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI Press, 2017, pp. 3725–3732.
View
| Download Submitted Version (ext.)
K. Chatterjee, P. Novotný, G. Pérez, J. Raskin, D. Zikelic, in:, Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI Press, 2017, pp. 3725–3732.
2017 | Conference Paper | IST-REx-ID: 1011 |

Faster algorithms for weighted recursive state machines
K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.), Springer, 2017, pp. 287–313.
View
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.), Springer, 2017, pp. 287–313.
2017 | Journal Article | IST-REx-ID: 1065 |

Pushdown reachability with constant treewidth
K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
View
| Files available
| DOI
K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
2017 | Journal Article | IST-REx-ID: 1066
Quantitative fair simulation games
K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Information and Computation 254 (2017) 143–166.
View
| Files available
| DOI
K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Information and Computation 254 (2017) 143–166.
2017 | Journal Article | IST-REx-ID: 1080 |

Reconstructing metastatic seeding patterns of human cancers
J. Reiter, A. Makohon Moore, J. Gerold, I. Božić, K. Chatterjee, C. Iacobuzio Donahue, B. Vogelstein, M. Nowak, Nature Communications 8 (2017).
View
| Files available
| DOI
J. Reiter, A. Makohon Moore, J. Gerold, I. Božić, K. Chatterjee, C. Iacobuzio Donahue, B. Vogelstein, M. Nowak, Nature Communications 8 (2017).
2017 | Conference Paper | IST-REx-ID: 1194 |

Stochastic invariants for probabilistic termination
K. Chatterjee, P. Novotný, D. Zikelic, in:, ACM, 2017, pp. 145–160.
View
| DOI
| Download Submitted Version (ext.)
K. Chatterjee, P. Novotný, D. Zikelic, in:, ACM, 2017, pp. 145–160.
2017 | Conference Paper | IST-REx-ID: 949 |

JTDec: A tool for tree decompositions in soot
K. Chatterjee, A.K. Goharshady, A. Pavlogiannis, in:, D. D’Souza (Ed.), Springer, 2017, pp. 59–66.
View
| Files available
| DOI
K. Chatterjee, A.K. Goharshady, A. Pavlogiannis, in:, D. D’Souza (Ed.), Springer, 2017, pp. 59–66.
2017 | Conference Paper | IST-REx-ID: 950 |

Infinite-duration bidding games
G. Avni, T.A. Henzinger, V.K. Chonev, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
View
| Files available
| DOI
| arXiv
G. Avni, T.A. Henzinger, V.K. Chonev, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
2016 | Conference Paper | IST-REx-ID: 478 |

The complexity of deciding legality of a single step of magic: The gathering
K. Chatterjee, R. Ibsen-Jensen, in:, IOS Press, 2016, pp. 1432–1439.
View
| Files available
| DOI
K. Chatterjee, R. Ibsen-Jensen, in:, IOS Press, 2016, pp. 1432–1439.
2016 | Conference Paper | IST-REx-ID: 480 |

Perfect-information stochastic games with generalized mean-payoff objectives
K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256.
2016 | Technical Report | IST-REx-ID: 5445 |

Quantitative interprocedural analysis
K. Chatterjee, A. Pavlogiannis, Y. Velner, Quantitative Interprocedural Analysis, IST Austria, 2016.
View
| Files available
| DOI
K. Chatterjee, A. Pavlogiannis, Y. Velner, Quantitative Interprocedural Analysis, IST Austria, 2016.
2016 | Technical Report | IST-REx-ID: 5449 |

Amplification on undirected population structures: Comets beat stars
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Amplification on Undirected Population Structures: Comets Beat Stars, IST Austria, 2016.
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Amplification on Undirected Population Structures: Comets Beat Stars, IST Austria, 2016.
2016 | Technical Report | IST-REx-ID: 5451 |

Strong amplifiers of natural selection
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Strong Amplifiers of Natural Selection, IST Austria, 2016.
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Strong Amplifiers of Natural Selection, IST Austria, 2016.
2016 | Technical Report | IST-REx-ID: 5452 |

Arbitrarily strong amplifiers of natural selection
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016.
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016.
2016 | Technical Report | IST-REx-ID: 5453 |

Arbitrarily strong amplifiers of natural selection
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016.
View
| Files available
| DOI
A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016.
2016 | Journal Article | IST-REx-ID: 1322 |

Asymmetric power boosts extortion in an economic experiment
C. Hilbe, K. Hagel, M. Milinski, PLoS One 11 (2016).
View
| Files available
| DOI
C. Hilbe, K. Hagel, M. Milinski, PLoS One 11 (2016).
2016 | Conference Paper | IST-REx-ID: 1324
Indefinite-horizon reachability in Goal-DEC-POMDPs
K. Chatterjee, M. Chmelik, in:, Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, 2016, pp. 88–96.
View
| Download None (ext.)
K. Chatterjee, M. Chmelik, in:, Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, 2016, pp. 88–96.
2016 | Conference Paper | IST-REx-ID: 1325 |

Stability in graphs and games
T. Brázdil, V. Forejt, A. Kučera, P. Novotný, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
View
| Files available
| DOI
T. Brázdil, V. Forejt, A. Kučera, P. Novotný, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
2016 | Conference Paper | IST-REx-ID: 1326 |

Optimizing the expected mean payoff in Energy Markov Decision Processes
T. Brázdil, A. Kučera, P. Novotný, in:, Springer, 2016, pp. 32–49.
View
| DOI
| Download Preprint (ext.)
T. Brázdil, A. Kučera, P. Novotný, in:, Springer, 2016, pp. 32–49.
2016 | Conference Paper | IST-REx-ID: 1327 |

Stochastic shortest path with energy constraints in POMDPs
T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.
View
| Download Preprint (ext.)
T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.
2016 | Journal Article | IST-REx-ID: 1333 |

Humans choose representatives who enforce cooperation in social dilemmas through extortion
M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, J. Marotzke, Nature Communications 7 (2016).
View
| Files available
| DOI
M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, J. Marotzke, Nature Communications 7 (2016).
2016 | Conference Paper | IST-REx-ID: 1335 |

Quantitative monitor automata
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 23–38.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 23–38.
2016 | Conference Paper | IST-REx-ID: 1340 |

The big match in small space
K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 64–76.
View
| DOI
| Download Preprint (ext.)
K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 64–76.