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
2016 | Conference Paper | IST-REx-ID: 1140 |

Model and objective separation with conditional lower bounds disjunction is harder than conjunction
K. Chatterjee, W. Dvoák, M. Henzinger, V. Loitzenbauer, in:, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, W. Dvoák, M. Henzinger, V. Loitzenbauer, in:, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206.
2016 | Conference Paper | IST-REx-ID: 1093 |

Linear distances between Markov chains
P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
View
| Files available
| DOI
P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
2016 | Conference Paper | IST-REx-ID: 1182 |

Robust draws in balanced knockout tournaments
K. Chatterjee, R. Ibsen-Jensen, J. Tkadlec, in:, AAAI Press, 2016, pp. 172–179.
View
| Files available
| Download Preprint (ext.)
K. Chatterjee, R. Ibsen-Jensen, J. Tkadlec, in:, AAAI Press, 2016, pp. 172–179.
2016 | Journal Article | IST-REx-ID: 1200 |

Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze
C. Hilbe, A. Traulsen, Physics of Life Reviews 19 (2016) 29–31.
View
| Files available
| DOI
C. Hilbe, A. Traulsen, Physics of Life Reviews 19 (2016) 29–31.
2016 | Conference Paper | IST-REx-ID: 1245
Game-theoretic models identify useful principles for peer collaboration in online learning platforms
V. Pandey, K. Chatterjee, in:, Proceedings of the ACM Conference on Computer Supported Cooperative Work, ACM, 2016, pp. 365–368.
View
| DOI
V. Pandey, K. Chatterjee, in:, Proceedings of the ACM Conference on Computer Supported Cooperative Work, ACM, 2016, pp. 365–368.
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.
2016 | Conference Paper | IST-REx-ID: 1389 |

On recurrent reachability for continuous linear dynamical systems
V.K. Chonev, J. Ouaknine, J. Worrell, in:, LICS ’16, IEEE, 2016, pp. 515–524.
View
| DOI
| Download Preprint (ext.)
V.K. Chonev, J. Ouaknine, J. Worrell, in:, LICS ’16, IEEE, 2016, pp. 515–524.
2016 | Thesis | IST-REx-ID: 1397
Algorithms for partially observable markov decision processes
M. Chmelik, Algorithms for Partially Observable Markov Decision Processes, IST Austria, 2016.
View
M. Chmelik, Algorithms for Partially Observable Markov Decision Processes, IST Austria, 2016.
2016 | Journal Article | IST-REx-ID: 1380 |

On the complexity of the orbit problem
V.K. Chonev, J. Ouaknine, J. Worrell, Journal of the ACM 63 (2016).
View
| DOI
| Download Preprint (ext.)
V.K. Chonev, J. Ouaknine, J. Worrell, Journal of the ACM 63 (2016).
2016 | Journal Article | IST-REx-ID: 1423 |

Comparing reactive and memory-one strategies of direct reciprocity
S. Baek, H. Jeong, C. Hilbe, M. Nowak, Scientific Reports 6 (2016).
View
| Files available
| DOI
S. Baek, H. Jeong, C. Hilbe, M. Nowak, Scientific Reports 6 (2016).
2016 | Journal Article | IST-REx-ID: 1426 |

Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites
M. Chakra, C. Hilbe, A. Traulsen, Royal Society Open Science 3 (2016).
View
| Files available
| DOI
M. Chakra, C. Hilbe, A. Traulsen, Royal Society Open Science 3 (2016).
2016 | Journal Article | IST-REx-ID: 1518 |

Efficient strategies for calculating blockwise likelihoods under the coalescent
K. Lohse, M. Chmelik, S. Martin, N.H. Barton, Genetics 202 (2016) 775–786.
View
| Files available
| DOI
K. Lohse, M. Chmelik, S. Martin, N.H. Barton, Genetics 202 (2016) 775–786.
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 | Journal Article | IST-REx-ID: 1477 |

What is decidable about partially observable Markov decision processes with ω-regular objectives
K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chmelik, M. Tracol, Journal of Computer and System Sciences 82 (2016) 878–911.
2016 | Journal Article | IST-REx-ID: 1529 |

Optimal cost almost-sure reachability in POMDPs
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Artificial Intelligence 234 (2016) 26–48.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Artificial Intelligence 234 (2016) 26–48.
2016 | Conference Paper | IST-REx-ID: 1166
A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps
K. Chatterjee, M. Chmelik, J. Davies, in:, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, 2016, pp. 3225–3232.
View
| Files available
K. Chatterjee, M. Chmelik, J. Davies, in:, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, 2016, pp. 3225–3232.
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: 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: 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 | 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 | Conference Paper | IST-REx-ID: 1438 |

Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, in:, ACM, 2016, pp. 327–342.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, in:, ACM, 2016, pp. 327–342.
2016 | Conference Paper | IST-REx-ID: 1071 |

Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs
K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.
View
| Files available
| DOI
K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.
2016 | Conference Paper | IST-REx-ID: 1437 |

Algorithms for algebraic path properties in concurrent systems of constant treewidth components
K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, ACM, 2016, pp. 733–747.
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, ACM, 2016, pp. 733–747.
2016 | Conference Paper | IST-REx-ID: 1386 |

Termination analysis of probabilistic programs through Positivstellensatz's
K. Chatterjee, H. Fu, A.K. Goharshady, in:, Springer, 2016, pp. 3–22.
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, H. Fu, A.K. Goharshady, in:, Springer, 2016, pp. 3–22.
2015 | Conference Paper | IST-REx-ID: 1499 |

Polynomial time decidability of weighted synchronization under partial observability
J. Kretinsky, K. Larsen, S. Laursen, J. Srba, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 142–154.
View
| Files available
| DOI
J. Kretinsky, K. Larsen, S. Laursen, J. Srba, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 142–154.
2015 | Journal Article | IST-REx-ID: 1559 |

Computational complexity of ecological and evolutionary spatial dynamics
R. Ibsen-Jensen, K. Chatterjee, M. Nowak, PNAS 112 (2015) 15636–15641.
View
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
R. Ibsen-Jensen, K. Chatterjee, M. Nowak, PNAS 112 (2015) 15636–15641.
2015 | Conference Paper | IST-REx-ID: 1502 |

Complete composition operators for IOCO-testing theory
N. Beneš, P. Daca, T.A. Henzinger, J. Kretinsky, D. Nickovic, in:, ACM, 2015, pp. 101–110.
View
| Files available
| DOI
N. Beneš, P. Daca, T.A. Henzinger, J. Kretinsky, D. Nickovic, in:, ACM, 2015, pp. 101–110.
2015 | Journal Article | IST-REx-ID: 1501 |

CEGAR for compositional analysis of qualitative properties in Markov decision processes
K. Chatterjee, M. Chmelik, P. Daca, Formal Methods in System Design 47 (2015) 230–264.
View
| Files available
| DOI
| Download Preprint (ext.)
K. Chatterjee, M. Chmelik, P. Daca, Formal Methods in System Design 47 (2015) 230–264.
2015 | Conference Paper | IST-REx-ID: 1594
Controller synthesis for MDPs and frequency LTL\GU
V. Forejt, J. Krčál, J. Kretinsky, in:, Springer, 2015, pp. 162–177.
View
| DOI
V. Forejt, J. Krčál, J. Kretinsky, in:, Springer, 2015, pp. 162–177.
2015 | Conference Paper | IST-REx-ID: 1601 |

The Hanoi omega-automata format
T. Babiak, F. Blahoudek, A. Duret Lutz, J. Klein, J. Kretinsky, D. Mueller, D. Parker, J. Strejček, in:, Springer, 2015, pp. 479–486.
View
| Files available
| DOI
T. Babiak, F. Blahoudek, A. Duret Lutz, J. Klein, J. Kretinsky, D. Mueller, D. Parker, J. Strejček, in:, Springer, 2015, pp. 479–486.
2015 | Conference Paper | IST-REx-ID: 1609 |

The complexity of synthesis from probabilistic components
K. Chatterjee, L. Doyen, M. Vardi, 9135 (2015) 108–120.
View
| DOI
| Download Preprint (ext.)
K. Chatterjee, L. Doyen, M. Vardi, 9135 (2015) 108–120.
2015 | Journal Article | IST-REx-ID: 1624 |

Cellular cooperation with shift updating and repulsion
A. Pavlogiannis, K. Chatterjee, B. Adlam, M. Nowak, Scientific Reports 5 (2015).
View
| Files available
| DOI
A. Pavlogiannis, K. Chatterjee, B. Adlam, M. Nowak, Scientific Reports 5 (2015).
2015 | Conference Paper | IST-REx-ID: 1660 |

Long-run average behaviour of probabilistic vector addition systems
T. Brázdil, S. Kiefer, A. Kučera, P. Novotný, in:, IEEE, 2015, pp. 44–55.
View
| DOI
| Download Preprint (ext.)
T. Brázdil, S. Kiefer, A. Kučera, P. Novotný, in:, IEEE, 2015, pp. 44–55.
2015 | Conference Paper | IST-REx-ID: 1667 |

Optimizing performance of continuous-time stochastic systems using timeout synthesis
T. Brázdil, L. Korenčiak, J. Krčál, P. Novotný, V. Řehák, 9259 (2015) 141–159.
View
| DOI
| Download Preprint (ext.)
T. Brázdil, L. Korenčiak, J. Krčál, P. Novotný, V. Řehák, 9259 (2015) 141–159.
2015 | Journal Article | IST-REx-ID: 1673 |

Amplifiers of selection
B. Adlam, K. Chatterjee, M. Nowak, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 471 (2015).
View
| Files available
| DOI
B. Adlam, K. Chatterjee, M. Nowak, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 471 (2015).
2015 | Journal Article | IST-REx-ID: 1665 |

Mutations driving CLL and their evolution in progression and relapse
D. Landau, E. Tausch, A. Taylor Weiner, C. Stewart, J. Reiter, J. Bahlo, S. Kluth, I. Božić, M. Lawrence, S. Böttcher, S. Carter, K. Cibulskis, D. Mertens, C. Sougnez, M. Rosenberg, J. Hess, J. Edelmann, S. Kless, M. Kneba, M. Ritgen, A. Fink, K. Fischer, S. Gabriel, E. Lander, M. Nowak, H. Döhner, M. Hallek, D. Neuberg, G. Getz, S. Stilgenbauer, C. Wu, Nature 526 (2015) 525–530.
View
| DOI
| Download Submitted Version (ext.)
| PubMed | Europe PMC
D. Landau, E. Tausch, A. Taylor Weiner, C. Stewart, J. Reiter, J. Bahlo, S. Kluth, I. Božić, M. Lawrence, S. Böttcher, S. Carter, K. Cibulskis, D. Mertens, C. Sougnez, M. Rosenberg, J. Hess, J. Edelmann, S. Kless, M. Kneba, M. Ritgen, A. Fink, K. Fischer, S. Gabriel, E. Lander, M. Nowak, H. Döhner, M. Hallek, D. Neuberg, G. Getz, S. Stilgenbauer, C. Wu, Nature 526 (2015) 525–530.
2015 | Conference Paper | IST-REx-ID: 1689 |

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, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 259–268.
View
| Files available
| DOI
| Download Preprint (ext.)
M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 259–268.
2015 | Conference Paper | IST-REx-ID: 1691
Temporal logic motion planning using POMDPs with parity objectives: Case study paper
M. Svoreňová, M. Chmelik, K. Leahy, H. Eniser, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 233–238.
View
| DOI
M. Svoreňová, M. Chmelik, K. Leahy, H. Eniser, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 233–238.
2015 | Journal Article | IST-REx-ID: 1694
Quantitative temporal simulation and refinement distances for timed systems
K. Chatterjee, V. Prabhu, IEEE Transactions on Automatic Control 60 (2015) 2291–2306.
View
| DOI
K. Chatterjee, V. Prabhu, IEEE Transactions on Automatic Control 60 (2015) 2291–2306.
2015 | Journal Article | IST-REx-ID: 1698 |

The complexity of multi-mean-payoff and multi-energy games
Y. Velner, K. Chatterjee, L. Doyen, T.A. Henzinger, A. Rabinovich, J. Raskin, Information and Computation 241 (2015) 177–196.
View
| DOI
| Download Preprint (ext.)
Y. Velner, K. Chatterjee, L. Doyen, T.A. Henzinger, A. Rabinovich, J. Raskin, Information and Computation 241 (2015) 177–196.
2015 | Journal Article | IST-REx-ID: 1681 |

Evolution of decisions in population games with sequentially searching individuals
T. Priklopil, K. Chatterjee, Games 6 (2015) 413–437.
View
| Files available
| DOI
T. Priklopil, K. Chatterjee, Games 6 (2015) 413–437.