Publications

Limit-sure reachability for small memory policies in POMDPs is NP-complete

A. Asadi, K. Chatterjee, R. Saona, J. Svoboda.

• ArXiv
  • Paper: https://doi.org/10.48550/arXiv.2412.00941

POMDPs and Blind MDPs: (Dis)continuity of Values and Strategies

K. Chatterjee, R. Saona.

Submitted.

Linear Equations with Min and Max Operators: Computational Complexity

K. Chatterjee, R. Luo, R. Saona, J. Svoboda.

Submitted.

Stochastic homogenization of HJ equations: a differential game approach

A. Davini, R. Saona, B. Ziliotto.

• ArXiv
  • Paper: https://doi.org/10.48550/arXiv.2406.18404

Ergodic Unobservable MDPs: Decidability of Approximation

K. Chatterjee, D. Lurie, R. Saona, B. Ziliotto.

• ArXiv
  • Paper: https://doi.org/10.48550/arXiv.2405.12583

Concurrent Stochastic Games with Stateful-discounted and Parity Objectives: Complexity and Algorithms

A. Asadi, K. Chatterjee, R. Saona, J. Svoboda.

• FSTTCS 2024
  • Paper: https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5
  • PDF: self-hosted
• ArXiv
  • Paper: https://doi.org/10.48550/arXiv.2405.02486

IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates

G. Giambartolomei, F. Mallmann-Trenn, R. Saona.

• ArXiv
  • Paper: https://doi.org/10.48550/arXiv.2407.11752

Zero-sum Random Games on Directed Graphs

L. Attia, L. Lichev, D. Mitsche, R. Saona, B. Ziliotto

Submitted.

• ArXiv
  • Paper: https://doi.org/10.48550/arXiv.2401.16252

Marginal Values of a Stochastic Game

L. Attia, M. Oliu-Barton, R. Saona.

• Mathematics of Operations Research
  • Paper https://doi.org/10.1287/moor.2023.0297
  • PDF: self-hosted

Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights

A. Asadi, K. Chatterjee, R. Saona, J. Svoboda

• ArXiv
  • Paper: https://arxiv.org/abs/2405.02479
• LICS 2024
  • Paper: https://doi.org/10.1145/3661814.3662080
  • PDF: self-hosted

Value-iteration with Guessing for Markov chains and Markov decision processes

K. Chatterjee, M. JafariRaviz, R. Saona, J. Svoboda

Submitted.

Prophet Inequalities: Separating Random Order from Order Selection

G. Giambartolomei, F. Mallmann-Trenn, R. Saona.

• ArXiv
  • Paper: https://doi.org/10.48550/arXiv.2304.04024

Value-Positivity for Matrix Games

K. Chatterjee, M. Oliu-Barton, R. Saona.

• Mathematics of Operations Research.
  • Paper: https://doi.org/10.1287/moor.2022.0332.
  • PDF: self-hosted

Repeated Prophet Inequality with Near-optimal Bounds

K. Chatterjee, M. Mohammadi, R. Saona.

Submitted.

• ArXiv
  • Paper: https://arxiv.org/abs/2209.14368

Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth

K. Chatterjee, T. Meggendorfer, R. Saona, J. Svoboda.

• SODA 2023
  • DOI: https://doi.org/10.1137/1.9781611977554.ch173
  • PDF: https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch173
  • PDF: self-hosted

Relation between the number of peaks and the number of reciprocal sign epistatic interactions

Raimundo Saona, Fyodor A. Kondrashov, Ksenia A. Khudiakova.

• Bulletin of Mathematical Biology
  • Paper: https://doi.org/10.1007/s11538-022-01029-z. Also available at ISTA repository
  • PDF: self-hosted
  • Correction: https://doi.org/10.1007/s11538-022-01118-z.
  • PDF: self-hosted
• BioRxiv
  • Paper: https://doi.org/10.1101/2022.01.23.477446

Finite-Memory Strategies in POMDPs with Long-Run Average Objectives

K. Chatterjee, R. Saona, B. Ziliotto.

• Mathematics of Operations Research.
  • Paper: https://doi.org/10.1287/moor.2020.1116. Also available at ISTA repository.
  • PDF: self-hosted
• ArXiv
  • Paper: https://arxiv.org/abs/1904.13360
• Video: Bernoulli-IMS One World Symposium 2020

Prophet Secretary Through Blind Strategies

J. Correa, R. Saona, B. Ziliotto.

• Math. Program.
  • Paper: https://doi.org/10.1007/s10107-020-01544-8
  • PDF: self-hosted
• Master thesis at University of Chile.
  • R. Saona. Prophet inequality through schur-convexity and optimal control.
  • Master thesis: https://repositorio.uchile.cl/handle/2250/168161
• SODA 2019

  • J. Correa, R. Saona, B. Ziliotto. SODA ‘19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms.

  • Paper: https://doi.org/10.1137/1.9781611975482.118

Conditional Predictive Bayesian Cramér-Rao Lower Bounds for Prognostic Algorithms Design

D. Acuña, M. Orchard, R. Saona.

• Applied Soft Computing
  • Paper: https://doi.org/10.1016/j.asoc.2018.01.033
  • PDF: self-hosted