[{"language":[{"iso":"eng"}],"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"type":"conference","page":"4590-4605","date_created":"2023-02-24T12:20:47Z","publication":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","quality_controlled":"1","article_processing_charge":"No","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Meggendorfer","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","orcid":"0000-0002-1712-2165","full_name":"Meggendorfer, Tobias"},{"first_name":"Raimundo J","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J"},{"full_name":"Svoboda, Jakub","first_name":"Jakub","orcid":"0000-0002-1419-3267","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"}],"day":"01","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","title":"Faster algorithm for turn-based stochastic games with bounded treewidth","publisher":"Society for Industrial and Applied Mathematics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2023-02-01T00:00:00Z","oa_version":"Published Version","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2023-01-22","location":"Florence, Italy","end_date":"2023-01-25"},"publication_status":"published","doi":"10.1137/1.9781611977554.ch173","citation":{"chicago":"Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 4590–4605. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>.","ista":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster algorithm for turn-based stochastic games with bounded treewidth. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 4590–4605.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2023, pp. 4590–605, doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>.","apa":"Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., &#38; Svoboda, J. (2023). Faster algorithm for turn-based stochastic games with bounded treewidth. In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>","short":"K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 4590–4605.","ama":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm for turn-based stochastic games with bounded treewidth. In: <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2023:4590-4605. doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>","ieee":"K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster algorithm for turn-based stochastic games with bounded treewidth,” in <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy, 2023, pp. 4590–4605."},"main_file_link":[{"url":"https://doi.org/10.1137/1.9781611977554.ch173","open_access":"1"}],"_id":"12676","year":"2023","date_updated":"2025-07-14T09:09:50Z","abstract":[{"lang":"eng","text":"Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth."}],"ec_funded":1,"month":"02","publication_identifier":{"isbn":["9781611977554"]},"oa":1,"status":"public"},{"file_date_updated":"2022-06-20T07:51:32Z","scopus_import":"1","ddc":["510","570"],"citation":{"short":"R.J. Saona Urmeneta, F. Kondrashov, K. Khudiakova, Bulletin of Mathematical Biology 84 (2022).","ieee":"R. J. Saona Urmeneta, F. Kondrashov, and K. Khudiakova, “Relation between the number of peaks and the number of reciprocal sign epistatic interactions,” <i>Bulletin of Mathematical Biology</i>, vol. 84, no. 8. Springer Nature, 2022.","ama":"Saona Urmeneta RJ, Kondrashov F, Khudiakova K. Relation between the number of peaks and the number of reciprocal sign epistatic interactions. <i>Bulletin of Mathematical Biology</i>. 2022;84(8). doi:<a href=\"https://doi.org/10.1007/s11538-022-01029-z\">10.1007/s11538-022-01029-z</a>","chicago":"Saona Urmeneta, Raimundo J, Fyodor Kondrashov, and Kseniia Khudiakova. “Relation between the Number of Peaks and the Number of Reciprocal Sign Epistatic Interactions.” <i>Bulletin of Mathematical Biology</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s11538-022-01029-z\">https://doi.org/10.1007/s11538-022-01029-z</a>.","apa":"Saona Urmeneta, R. J., Kondrashov, F., &#38; Khudiakova, K. (2022). Relation between the number of peaks and the number of reciprocal sign epistatic interactions. <i>Bulletin of Mathematical Biology</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11538-022-01029-z\">https://doi.org/10.1007/s11538-022-01029-z</a>","ista":"Saona Urmeneta RJ, Kondrashov F, Khudiakova K. 2022. Relation between the number of peaks and the number of reciprocal sign epistatic interactions. Bulletin of Mathematical Biology. 84(8), 74.","mla":"Saona Urmeneta, Raimundo J., et al. “Relation between the Number of Peaks and the Number of Reciprocal Sign Epistatic Interactions.” <i>Bulletin of Mathematical Biology</i>, vol. 84, no. 8, 74, Springer Nature, 2022, doi:<a href=\"https://doi.org/10.1007/s11538-022-01029-z\">10.1007/s11538-022-01029-z</a>."},"intvolume":"        84","publication_status":"published","doi":"10.1007/s11538-022-01029-z","oa_version":"Published Version","date_published":"2022-06-17T00:00:00Z","status":"public","publication_identifier":{"issn":["0092-8240"],"eissn":["1522-9602"]},"oa":1,"month":"06","ec_funded":1,"date_updated":"2023-08-03T07:20:53Z","abstract":[{"lang":"eng","text":"Empirical essays of fitness landscapes suggest that they may be rugged, that is having multiple fitness peaks. Such fitness landscapes, those that have multiple peaks, necessarily have special local structures, called reciprocal sign epistasis (Poelwijk et al. in J Theor Biol 272:141–144, 2011). Here, we investigate the quantitative relationship between the number of fitness peaks and the number of reciprocal sign epistatic interactions. Previously, it has been shown (Poelwijk et al. in J Theor Biol 272:141–144, 2011) that pairwise reciprocal sign epistasis is a necessary but not sufficient condition for the existence of multiple peaks. Applying discrete Morse theory, which to our knowledge has never been used in this context, we extend this result by giving the minimal number of reciprocal sign epistatic interactions required to create a given number of peaks."}],"issue":"8","year":"2022","article_number":"74","_id":"11447","article_processing_charge":"Yes (via OA deal)","article_type":"original","external_id":{"isi":["000812509800001"]},"volume":84,"quality_controlled":"1","keyword":["Computational Theory and Mathematics","General Agricultural and Biological Sciences","Pharmacology","General Environmental Science","General Biochemistry","Genetics and Molecular Biology","General Mathematics","Immunology","General Neuroscience"],"related_material":{"link":[{"relation":"erratum","url":"https://doi.org/10.1007/s11538-022-01118-z"}]},"has_accepted_license":"1","date_created":"2022-06-17T16:16:15Z","publication":"Bulletin of Mathematical Biology","type":"journal_article","language":[{"iso":"eng"}],"department":[{"_id":"GradSch"},{"_id":"NiBa"},{"_id":"JaMa"}],"publisher":"Springer Nature","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Relation between the number of peaks and the number of reciprocal sign epistatic interactions","acknowledgement":"We are grateful to Herbert Edelsbrunner and Jeferson Zapata for helpful discussions. Open access funding provided by Austrian Science Fund (FWF). Partially supported by the ERC Consolidator (771209–CharFL) and the FWF Austrian Science Fund (I5127-B) grants to FAK.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"17","project":[{"_id":"26580278-B435-11E9-9278-68D0E5697425","grant_number":"771209","name":"Characterizing the fitness landscape on population and global scales","call_identifier":"H2020"},{"grant_number":"I05127","_id":"c098eddd-5a5b-11eb-8a69-abe27170a68f","name":"Evolutionary analysis of gene regulation"}],"author":[{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","first_name":"Raimundo J","orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J"},{"full_name":"Kondrashov, Fyodor","orcid":"0000-0001-8243-4694","first_name":"Fyodor","last_name":"Kondrashov","id":"44FDEF62-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Khudiakova","id":"4E6DC800-AE37-11E9-AC72-31CAE5697425","first_name":"Kseniia","orcid":"0000-0002-6246-1465","full_name":"Khudiakova, Kseniia"}],"isi":1,"file":[{"file_size":463025,"success":1,"content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"11455","creator":"dernst","checksum":"05a1fe7d10914a00c2bca9b447993a65","date_created":"2022-06-20T07:51:32Z","date_updated":"2022-06-20T07:51:32Z","file_name":"2022_BulletinMathBiology_Saona.pdf"}]},{"_id":"9311","year":"2022","date_updated":"2023-09-05T13:16:11Z","abstract":[{"text":"Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function. ","lang":"eng"}],"issue":"1","arxiv":1,"month":"02","publication_identifier":{"issn":["0364-765X"],"eissn":["1526-5471"]},"oa":1,"status":"public","date_published":"2022-02-01T00:00:00Z","oa_version":"Preprint","publication_status":"published","doi":"10.1287/moor.2020.1116","citation":{"chicago":"Chatterjee, Krishnendu, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2022. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>.","apa":"Chatterjee, K., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2022). Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>","mla":"Chatterjee, Krishnendu, et al. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>, vol. 47, no. 1, Institute for Operations Research and the Management Sciences, 2022, pp. 100–19, doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>.","ista":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. 2022. Finite-memory strategies in POMDPs with long-run average objectives. Mathematics of Operations Research. 47(1), 100–119.","short":"K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations Research 47 (2022) 100–119.","ieee":"K. Chatterjee, R. J. Saona Urmeneta, and B. Ziliotto, “Finite-memory strategies in POMDPs with long-run average objectives,” <i>Mathematics of Operations Research</i>, vol. 47, no. 1. Institute for Operations Research and the Management Sciences, pp. 100–119, 2022.","ama":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. 2022;47(1):100-119. doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>"},"intvolume":"        47","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1904.13360"}],"project":[{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"isi":1,"author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","first_name":"Raimundo J","orcid":"0000-0001-5103-038X"},{"first_name":"Bruno","last_name":"Ziliotto","full_name":"Ziliotto, Bruno"}],"day":"01","acknowledgement":"Partially supported by Austrian Science Fund (FWF) NFN Grant No RiSE/SHiNE S11407, by CONICYT Chile through grant PII 20150140, and by ECOS-CONICYT through grant C15E03.\r\n","title":"Finite-memory strategies in POMDPs with long-run average objectives","publisher":"Institute for Operations Research and the Management Sciences","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","language":[{"iso":"eng"}],"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"type":"journal_article","date_created":"2021-04-08T09:33:31Z","page":"100-119","publication":"Mathematics of Operations Research","external_id":{"arxiv":["1904.13360"],"isi":["000731918100001"]},"keyword":["Management Science and Operations Research","General Mathematics","Computer Science Applications"],"quality_controlled":"1","volume":47,"article_type":"original","article_processing_charge":"No"},{"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"first_name":"Mona","id":"4363614d-b686-11ed-a7d5-ac9e4a24bc2e","last_name":"Mohammadi","full_name":"Mohammadi, Mona"},{"full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","orcid":"0000-0001-5103-038X"}],"article_number":"2209.14368","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"_id":"12677","arxiv":1,"abstract":[{"lang":"eng","text":"In modern sample-driven Prophet Inequality, an adversary chooses a sequence of n items with values v1,v2,…,vn to be presented to a decision maker (DM). The process follows in two phases. In the first phase (sampling phase), some items, possibly selected at random, are revealed to the DM, but she can never accept them. In the second phase, the DM is presented with the other items in a random order and online fashion. For each item, she must make an irrevocable decision to either accept the item and stop the process or reject the item forever and proceed to the next item. The goal of the DM is to maximize the expected value as compared to a Prophet (or offline algorithm) that has access to all information. In this setting, the sampling phase has no cost and is not part of the optimization process. However, in many scenarios, the samples are obtained as part of the decision-making process.\r\nWe model this aspect as a two-phase Prophet Inequality where an adversary chooses a sequence of 2n items with values v1,v2,…,v2n and the items are randomly ordered. Finally, there are two phases of the Prophet Inequality problem with the first n-items and the rest of the items, respectively. We show that some basic algorithms achieve a ratio of at most 0.450. We present an algorithm that achieves a ratio of at least 0.495. Finally, we show that for every algorithm the ratio it can achieve is at most 0.502. Hence our algorithm is near-optimal."}],"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","date_updated":"2025-07-14T09:09:51Z","year":"2022","day":"28","month":"09","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","oa":1,"title":"Repeated prophet inequality with near-optimal bounds","oa_version":"Preprint","type":"preprint","date_published":"2022-09-28T00:00:00Z","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"language":[{"iso":"eng"}],"doi":"10.48550/ARXIV.2209.14368","publication_status":"submitted","publication":"arXiv","date_created":"2023-02-24T12:21:40Z","citation":{"ama":"Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with near-optimal bounds. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">10.48550/ARXIV.2209.14368</a>","ieee":"K. Chatterjee, M. Mohammadi, and R. J. Saona Urmeneta, “Repeated prophet inequality with near-optimal bounds,” <i>arXiv</i>. .","short":"K. Chatterjee, M. Mohammadi, R.J. Saona Urmeneta, ArXiv (n.d.).","ista":"Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with near-optimal bounds. arXiv, 2209.14368.","mla":"Chatterjee, Krishnendu, et al. “Repeated Prophet Inequality with Near-Optimal Bounds.” <i>ArXiv</i>, 2209.14368, doi:<a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">10.48550/ARXIV.2209.14368</a>.","apa":"Chatterjee, K., Mohammadi, M., &#38; Saona Urmeneta, R. J. (n.d.). Repeated prophet inequality with near-optimal bounds. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">https://doi.org/10.48550/ARXIV.2209.14368</a>","chicago":"Chatterjee, Krishnendu, Mona Mohammadi, and Raimundo J Saona Urmeneta. “Repeated Prophet Inequality with Near-Optimal Bounds.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">https://doi.org/10.48550/ARXIV.2209.14368</a>."},"external_id":{"arxiv":["2209.14368"]},"article_processing_charge":"No","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2209.14368","open_access":"1"}]}]