[{"acknowledgement":"This work is a part of projects VAMOS that has received fund-ing from the European Research Council (ERC), grant agreementNo 101020093 and the Austrian Science Fund (FWF) SFB projectSpyCoDe F8502.We thank anonymous reviewers for pointing us to related work [ 3] and for their valuable suggestions that improved this paper.","citation":{"apa":"Henzinger, T. A., Karimi, M., &#38; Thejaswini, K. S. (2025). Privacy-preserving runtime verification. In <i>Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security</i> (pp. 2774–2787). Taipei, Taiwan: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3719027.3765137\">https://doi.org/10.1145/3719027.3765137</a>","mla":"Henzinger, Thomas A., et al. “Privacy-Preserving Runtime Verification.” <i>Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security</i>, Association for Computing Machinery, 2025, pp. 2774–87, doi:<a href=\"https://doi.org/10.1145/3719027.3765137\">10.1145/3719027.3765137</a>.","ama":"Henzinger TA, Karimi M, Thejaswini KS. Privacy-preserving runtime verification. In: <i>Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security</i>. Association for Computing Machinery; 2025:2774-2787. doi:<a href=\"https://doi.org/10.1145/3719027.3765137\">10.1145/3719027.3765137</a>","ista":"Henzinger TA, Karimi M, Thejaswini KS. 2025. Privacy-preserving runtime verification. Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. CCS: Conference on Computer and Communications Security, 2774–2787.","chicago":"Henzinger, Thomas A, Mahyar Karimi, and K. S. Thejaswini. “Privacy-Preserving Runtime Verification.” In <i>Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security</i>, 2774–87. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3719027.3765137\">https://doi.org/10.1145/3719027.3765137</a>.","ieee":"T. A. Henzinger, M. Karimi, and K. S. Thejaswini, “Privacy-preserving runtime verification,” in <i>Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security</i>, Taipei, Taiwan, 2025, pp. 2774–2787.","short":"T.A. Henzinger, M. Karimi, K.S. Thejaswini, in:, Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, 2025, pp. 2774–2787."},"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"orcid":"0009-0005-0820-1696","full_name":"Karimi, Mahyar","first_name":"Mahyar","last_name":"Karimi","id":"6e5417ba-5355-11ee-ae5a-94c2e510b26b"},{"id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","first_name":"K. S.","full_name":"Thejaswini, K. S.","last_name":"Thejaswini"}],"OA_place":"publisher","_id":"21020","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa":1,"date_updated":"2026-03-13T13:37:19Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"conference":{"start_date":"2025-10-13","name":"CCS: Conference on Computer and Communications Security","end_date":"2025-10-17","location":"Taipei, Taiwan"},"doi":"10.1145/3719027.3765137","file_date_updated":"2026-01-21T07:34:58Z","type":"conference","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"21401"}]},"publisher":"Association for Computing Machinery","date_published":"2025-11-22T00:00:00Z","date_created":"2026-01-20T10:17:10Z","oa_version":"Published Version","month":"11","project":[{"grant_number":"101020093","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"},{"name":"Interface Theory for Security and Privacy","_id":"34a1b658-11ca-11ed-8bc3-c75229f0241e","grant_number":"F8502"}],"ddc":["000"],"publication_identifier":{"isbn":["9798400715259"]},"external_id":{"arxiv":["2505.09276"]},"article_processing_charge":"Yes (via OA deal)","page":"2774-2787","status":"public","publication_status":"published","abstract":[{"text":"Runtime verification offers scalable solutions to improve the safety and reliability of systems. However, systems that require verification or monitoring by a third party to ensure compliance with a specification might contain sensitive information, causing privacy concerns when usual runtime verification approaches are used. Privacy is compromised if protected information about the system, or sensitive data that is processed by the system, is revealed. In addition, revealing the specification being monitored may undermine the essence of third-party verification.\r\nIn this work, we propose two novel protocols for the privacy-preserving runtime verification of systems against formal sequential specifications. In our first protocol, the monitor verifies whether the system satisfies the specification without learning anything else, though both parties are aware of the specification. Our second protocol ensures that the system remains oblivious to the monitored specification, while the monitor learns only whether the system satisfies the specification and nothing more. Our protocols adapt and improve existing techniques used in cryptography, and more specifically, multi-party computation.\r\nThe sequential specification defines the observation step of the monitor, whose granularity depends on the situation (e.g., banks may be monitored on a daily basis). Our protocols exchange a single message per observation step, after an initialisation phase. This design minimises communication overhead, enabling relatively lightweight privacy-preserving monitoring. We implement our approach for monitoring specifications described by register automata and evaluate it experimentally.","lang":"eng"}],"file":[{"access_level":"open_access","creator":"dernst","file_id":"21024","checksum":"615ffddab6c7285158c2953acec6fa6f","file_size":1241912,"relation":"main_file","date_updated":"2026-01-21T07:34:58Z","success":1,"content_type":"application/pdf","date_created":"2026-01-21T07:34:58Z","file_name":"2025_CCS_HenzingerT.pdf"}],"department":[{"_id":"ToHe"},{"_id":"GradSch"}],"OA_type":"hybrid","arxiv":1,"ec_funded":1,"title":"Privacy-preserving runtime verification","has_accepted_license":"1","year":"2025","scopus_import":"1","publication":"Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security","day":"22"},{"_id":"21281","OA_place":"publisher","author":[{"last_name":"Asadi","full_name":"Asadi, Ali","first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb"},{"first_name":"Leonard","full_name":"Brice, Leonard","last_name":"Brice"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","full_name":"Thejaswini, K. S.","first_name":"K. S.","last_name":"Thejaswini"}],"citation":{"apa":"Asadi, A., Brice, L., Chatterjee, K., &#38; Thejaswini, K. S. (2025). ε-stationary Nash equilibria in multi-player stochastic graph games. In <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 360, p. 9:1-9:17). Pilani, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">https://doi.org/10.4230/lipics.fsttcs.2025.9</a>","mla":"Asadi, Ali, et al. “ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games.” <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 360, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 9:1-9:17, doi:<a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">10.4230/lipics.fsttcs.2025.9</a>.","chicago":"Asadi, Ali, Leonard Brice, Krishnendu Chatterjee, and K. S. Thejaswini. “ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games.” In <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, 360:9:1-9:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">https://doi.org/10.4230/lipics.fsttcs.2025.9</a>.","ama":"Asadi A, Brice L, Chatterjee K, Thejaswini KS. ε-stationary Nash equilibria in multi-player stochastic graph games. In: <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 360. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:9:1-9:17. doi:<a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">10.4230/lipics.fsttcs.2025.9</a>","ista":"Asadi A, Brice L, Chatterjee K, Thejaswini KS. 2025. ε-stationary Nash equilibria in multi-player stochastic graph games. 45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 360, 9:1-9:17.","ieee":"A. Asadi, L. Brice, K. Chatterjee, and K. S. Thejaswini, “ε-stationary Nash equilibria in multi-player stochastic graph games,” in <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Pilani, India, 2025, vol. 360, p. 9:1-9:17.","short":"A. Asadi, L. Brice, K. Chatterjee, K.S. Thejaswini, in:, 45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 9:1-9:17."},"acknowledgement":"This work is a part of project VAMOS that has received funding from the European\r\nResearch Council (ERC), grant agreement No 101020093.\r\n","date_updated":"2026-02-19T09:39:15Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","date_published":"2025-12-09T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"type":"conference","file_date_updated":"2026-02-18T09:13:25Z","doi":"10.4230/lipics.fsttcs.2025.9","conference":{"name":"FSTTCS: Conference on Foundations of Software Technology and Theoretical Computer Science","start_date":"2025-12-17","end_date":"2025-12-19","location":"Pilani, India"},"external_id":{"arxiv":["2508.15356"]},"ddc":["000"],"publication_identifier":{"isbn":["9783959774062"]},"project":[{"name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","grant_number":"101020093"}],"month":"12","date_created":"2026-02-17T08:27:14Z","oa_version":"Published Version","page":"9:1-9:17","article_processing_charge":"Yes","intvolume":"       360","publication_status":"published","file":[{"access_level":"open_access","creator":"dernst","file_id":"21316","checksum":"a66343e3ccc4a9cc5bc699c03d5764ff","relation":"main_file","date_updated":"2026-02-18T09:13:25Z","file_size":1054007,"content_type":"application/pdf","success":1,"file_name":"2025_FSTTCS_Asadi.pdf","date_created":"2026-02-18T09:13:25Z"}],"abstract":[{"lang":"eng","text":"A strategy profile in a multi-player game is a Nash equilibrium if no player can unilaterally deviate to achieve a strictly better payoff. A profile is an ε-Nash equilibrium if no player can gain more than ε by unilaterally deviating from their strategy. In this work, we use ε-Nash equilibria to approximate the computation of Nash equilibria. Specifically, we focus on turn-based, multiplayer stochastic games played on graphs, where players are restricted to stationary strategies - strategies that use randomness but not memory.\r\nThe problem of deciding the constrained existence of stationary Nash equilibria - where each player’s payoff must lie within a given interval - is known to be ∃ℝ-complete in such a setting (Hansen and Sølvsten, 2020). We extend this line of work to stationary ε-Nash equilibria and present an algorithm that solves the following promise problem: given a game with a Nash equilibrium satisfying the constraints, compute an ε-Nash equilibrium that ε-satisfies those same constraints - satisfies the constraints up to an ε additive error. Our algorithm runs in FNP^NP time.\r\nTo achieve this, we first show that if a constrained Nash equilibrium exists, then one exists where the non-zero probabilities are at least an inverse of a double-exponential in the input. We further prove that such a strategy can be encoded using floating-point representations, as in the work of Frederiksen and Miltersen (2013), which finally gives us our FNP^NP algorithm. \r\nWe further show that the decision version of the promise problem is NP-hard. Finally, we show a partial tightness result by proving a lower bound for such techniques: if a constrained Nash equilibrium exists, then there must be one where the probabilities in the strategies are double-exponentially small."}],"status":"public","ec_funded":1,"alternative_title":["LIPIcs"],"OA_type":"gold","arxiv":1,"volume":360,"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"day":"09","publication":"45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science","year":"2025","has_accepted_license":"1","title":"ε-stationary Nash equilibria in multi-player stochastic graph games"},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2025-08-20T00:00:00Z","language":[{"iso":"eng"}],"type":"conference","conference":{"start_date":"2025-08-25","name":"MFCS: Mathematical Foundations of Computer Science","location":"Warsaw, Poland","end_date":"2025-08-29"},"doi":"10.4230/LIPIcs.MFCS.2025.30","file_date_updated":"2025-09-08T07:11:12Z","external_id":{"arxiv":["2502.0531"]},"ddc":["000"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773881"]},"project":[{"name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","grant_number":"101020093"}],"month":"08","oa_version":"Published Version","date_created":"2025-09-07T22:01:32Z","_id":"20290","OA_place":"publisher","author":[{"last_name":"Brice","first_name":"Léonard","full_name":"Brice, Léonard"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000-0002-2985-7724"},{"id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","last_name":"Thejaswini","first_name":"K. S.","full_name":"Thejaswini, K. S."}],"acknowledgement":"This work is a part of project VAMOS that has received funding from the European\r\nResearch Council (ERC), grant agreement No 101020093. We thank anonymous reviewers for pointing us to the Hurwicz criterion and to the work of Gallego-Hernández and Mansutti [13]. We thank Marie van den Bogaard for her valuable feedback on the first author’s PhD dissertation, which helped improve the quality of this work. ","citation":{"apa":"Brice, L., Henzinger, T. A., &#38; Thejaswini, K. S. (2025). Finding equilibria: Simpler for pessimists, simplest for optimists. In <i>50th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">https://doi.org/10.4230/LIPIcs.MFCS.2025.30</a>","mla":"Brice, Léonard, et al. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 345, 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">10.4230/LIPIcs.MFCS.2025.30</a>.","chicago":"Brice, Léonard, Thomas A Henzinger, and K. S. Thejaswini. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” In <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">https://doi.org/10.4230/LIPIcs.MFCS.2025.30</a>.","ama":"Brice L, Henzinger TA, Thejaswini KS. Finding equilibria: Simpler for pessimists, simplest for optimists. In: <i>50th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">10.4230/LIPIcs.MFCS.2025.30</a>","ista":"Brice L, Henzinger TA, Thejaswini KS. 2025. Finding equilibria: Simpler for pessimists, simplest for optimists. 50th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 345, 30.","ieee":"L. Brice, T. A. Henzinger, and K. S. Thejaswini, “Finding equilibria: Simpler for pessimists, simplest for optimists,” in <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Warsaw, Poland, 2025, vol. 345.","short":"L. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 50th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"date_updated":"2025-09-08T07:15:40Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","ec_funded":1,"alternative_title":["LIPIcs"],"OA_type":"gold","arxiv":1,"department":[{"_id":"ToHe"}],"article_number":"30","volume":345,"day":"20","publication":"50th International Symposium on Mathematical Foundations of Computer Science","scopus_import":"1","year":"2025","title":"Finding equilibria: Simpler for pessimists, simplest for optimists","has_accepted_license":"1","article_processing_charge":"Yes","intvolume":"       345","publication_status":"published","file":[{"file_id":"20306","creator":"dernst","access_level":"open_access","date_created":"2025-09-08T07:11:12Z","file_name":"2025_MFCS_Brice.pdf","success":1,"content_type":"application/pdf","relation":"main_file","date_updated":"2025-09-08T07:11:12Z","file_size":1149694,"checksum":"9bc6b8e537662d371d2a27444cbc0b75"}],"abstract":[{"text":"We consider equilibria in multiplayer stochastic graph games with terminal-node rewards. In such games, Nash equilibria are defined assuming that each player seeks to maximise their expected payoff, ignoring their aversion or tolerance to risk. We therefore study risk-sensitive equilibria (RSEs), where the expected payoff is replaced by a risk measure. A classical risk measure in the literature is the entropic risk measure, where each player has a real valued parameter capturing their risk-averseness. We introduce the extreme risk measure, which corresponds to extreme cases of entropic risk measure, where players are either extreme optimists or extreme pessimists. Under extreme risk measure, every player is an extremist: an extreme optimist perceives their reward as the maximum payoff that can be achieved with positive probability, while an extreme pessimist expects the minimum payoff achievable with positive probability. We argue that the extreme risk measure, especially in multi-player graph based settings, is particularly relevant as they can model several real life instances such as interactions between secure systems and potential security threats, or distributed controls for safety critical systems. We prove that RSEs defined with the extreme risk measure are guaranteed to exist when all rewards are non-negative. Furthermore, we prove that the problem of deciding whether a given game contains an RSE that generates risk measures within specified intervals is decidable and NP-complete for our extreme risk measure, and even PTIME-complete when all players are extreme optimists, while that same problem is undecidable using the entropic risk measure or even the classical expected payoff. This establishes, to our knowledge, the first decidable fragment for equilibria in simple stochastic games without restrictions on strategy types or number of players.","lang":"eng"}],"status":"public"},{"acknowledgement":"This work is a part of project VAMOS that has received funding from the European Research Council (ERC), grant agreement No 101020093.","citation":{"ieee":"T. A. Henzinger, A. Prakash, and K. S. Thejaswini, “Resolving nondeterminism with randomness,” in <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Warsaw, Poland, 2025, vol. 345.","short":"T.A. Henzinger, A. Prakash, K.S. Thejaswini, in:, 50th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","apa":"Henzinger, T. A., Prakash, A., &#38; Thejaswini, K. S. (2025). Resolving nondeterminism with randomness. In <i>50th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">https://doi.org/10.4230/LIPIcs.MFCS.2025.57</a>","mla":"Henzinger, Thomas A., et al. “Resolving Nondeterminism with Randomness.” <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 345, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">10.4230/LIPIcs.MFCS.2025.57</a>.","ama":"Henzinger TA, Prakash A, Thejaswini KS. Resolving nondeterminism with randomness. In: <i>50th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">10.4230/LIPIcs.MFCS.2025.57</a>","chicago":"Henzinger, Thomas A, Aditya Prakash, and K. S. Thejaswini. “Resolving Nondeterminism with Randomness.” In <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">https://doi.org/10.4230/LIPIcs.MFCS.2025.57</a>.","ista":"Henzinger TA, Prakash A, Thejaswini KS. 2025. Resolving nondeterminism with randomness. 50th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 345, 57."},"author":[{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Aditya","full_name":"Prakash, Aditya","last_name":"Prakash"},{"id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","last_name":"Thejaswini","full_name":"Thejaswini, K. S.","first_name":"K. S."}],"OA_place":"publisher","_id":"20291","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","corr_author":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_updated":"2025-09-08T07:06:11Z","oa":1,"type":"conference","doi":"10.4230/LIPIcs.MFCS.2025.57","file_date_updated":"2025-09-08T06:56:56Z","conference":{"end_date":"2025-08-29","location":"Warsaw, Poland","start_date":"2025-08-25","name":"MFCS: Mathematical Foundations of Computer Science"},"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2025-08-20T00:00:00Z","date_created":"2025-09-07T22:01:32Z","oa_version":"Published Version","month":"08","ddc":["000"],"publication_identifier":{"isbn":["9783959773881"],"issn":["1868-8969"]},"project":[{"name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","call_identifier":"H2020"}],"external_id":{"arxiv":["2502.12872"]},"article_processing_charge":"No","status":"public","abstract":[{"text":"We define and study classes of ω-regular automata for which the nondeterminism can be resolved by a policy that uses a combination of memory and randomness on any input word, based solely on the prefix read so far. We examine two settings for providing the input word to an automaton. In the first setting, called adversarial resolvability, the input word is constructed letter-by-letter by an adversary, dependent on the resolver’s previous decisions. In the second setting, called stochastic resolvability, the adversary pre-commits to an infinite word and reveals it letter-by-letter. In each setting, we require the existence of an almost-sure resolver, i.e., a policy that ensures that as long as the adversary provides a word in the language of the underlying nondeterministic automaton, the run constructed by the policy is accepting with probability 1.\r\nThe class of automata that are adversarially resolvable is the well-studied class of history-deterministic automata. The case of stochastically resolvable automata, on the other hand, defines a novel class. Restricting the class of resolvers in both settings to stochastic policies without memory introduces two additional new classes of automata. We show that the new automata classes offer interesting trade-offs between succinctness, expressivity, and computational complexity, providing a fine gradation between deterministic automata and nondeterministic automata.","lang":"eng"}],"publication_status":"published","file":[{"file_id":"20305","creator":"dernst","access_level":"open_access","date_created":"2025-09-08T06:56:56Z","file_name":"2025_MFCS_HenzingerT.pdf","success":1,"content_type":"application/pdf","file_size":1009644,"date_updated":"2025-09-08T06:56:56Z","relation":"main_file","checksum":"6068b772aba6cb0d01f3e5a90abed973"}],"intvolume":"       345","department":[{"_id":"ToHe"}],"volume":345,"article_number":"57","arxiv":1,"OA_type":"gold","ec_funded":1,"alternative_title":["LIPIcs"],"title":"Resolving nondeterminism with randomness","has_accepted_license":"1","scopus_import":"1","year":"2025","publication":"50th International Symposium on Mathematical Foundations of Computer Science","day":"20"},{"status":"public","isi":1,"abstract":[{"lang":"eng","text":"We provide an algorithmto solve Rabin and Streett games over graphs\r\nwith n vertices,m edges, and k colours that runs in ˜O³mn(k!)1+o(1)´time and\r\nO(nk logk logn) space, where ˜O hides poly-logarithmic factors. Our algorithm\r\nis an improvement by a super quadratic dependence on k! from the currently\r\nbest known run time of O³mn2(k!)2+o(1)´, obtained by converting a Rabin\r\ngameinto a parity game,while simultaneously improving its exponential space\r\nrequirement.\r\nOur main technical ingredient is a characterisation of progress measures for\r\nRabin games using colourful trees and a combinatorial construction of succinctlyrepresented,\r\nuniversal colourful trees. Colourful universal trees are generalisations\r\nof universal trees used by Jurdzi´nski and Lazi´c (2017) to solve parity\r\ngames, as well as of Rabin progress measures of Klarlund and Kozen (1991).\r\nOur algorithm for Rabin games is a progress measure lifting algorithm where\r\nthe lifting is performed on succinct, colourful, universal trees."}],"file":[{"success":1,"content_type":"application/pdf","date_created":"2024-05-22T07:24:45Z","file_name":"2024_LNCS_Majumdar.pdf","checksum":"492be74f69cd6ea42d38681082d0b521","relation":"main_file","date_updated":"2024-05-22T07:24:45Z","file_size":462173,"creator":"dernst","file_id":"15415","access_level":"open_access"}],"publication_status":"published","intvolume":"     14572","article_processing_charge":"Yes (in subscription journal)","page":"213-231","has_accepted_license":"1","title":"Rabin games and colourful universal trees","year":"2024","scopus_import":"1","publication":"30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","day":"06","department":[{"_id":"ToHe"}],"volume":14572,"arxiv":1,"alternative_title":["LNCS"],"ec_funded":1,"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","oa":1,"date_updated":"2025-09-08T07:34:49Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"citation":{"chicago":"Majumdar, Rupak, Irmak Sağlam, and K. S. Thejaswini. “Rabin Games and Colourful Universal Trees.” In <i>30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 14572:213–31. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-57256-2_11\">https://doi.org/10.1007/978-3-031-57256-2_11</a>.","ista":"Majumdar R, Sağlam I, Thejaswini KS. 2024. Rabin games and colourful universal trees. 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. , LNCS, vol. 14572, 213–231.","ama":"Majumdar R, Sağlam I, Thejaswini KS. Rabin games and colourful universal trees. In: <i>30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 14572. Springer Nature; 2024:213-231. doi:<a href=\"https://doi.org/10.1007/978-3-031-57256-2_11\">10.1007/978-3-031-57256-2_11</a>","apa":"Majumdar, R., Sağlam, I., &#38; Thejaswini, K. S. (2024). Rabin games and colourful universal trees. In <i>30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 14572, pp. 213–231). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-57256-2_11\">https://doi.org/10.1007/978-3-031-57256-2_11</a>","mla":"Majumdar, Rupak, et al. “Rabin Games and Colourful Universal Trees.” <i>30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 14572, Springer Nature, 2024, pp. 213–31, doi:<a href=\"https://doi.org/10.1007/978-3-031-57256-2_11\">10.1007/978-3-031-57256-2_11</a>.","short":"R. Majumdar, I. Sağlam, K.S. Thejaswini, in:, 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2024, pp. 213–231.","ieee":"R. Majumdar, I. Sağlam, and K. S. Thejaswini, “Rabin games and colourful universal trees,” in <i>30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 2024, vol. 14572, pp. 213–231."},"acknowledgement":"This work is a part of the project VAMOS that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreements No 101020093. Rupak Majumdar was partially supported by the DFG project 389792660 TRR 248-CPEC.","author":[{"first_name":"Rupak","full_name":"Majumdar, Rupak","last_name":"Majumdar"},{"last_name":"Sağlam","first_name":"Irmak","full_name":"Sağlam, Irmak"},{"id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","last_name":"Thejaswini","full_name":"Thejaswini, K. S.","first_name":"K. S."}],"_id":"15377","oa_version":"Published Version","date_created":"2024-05-12T22:01:02Z","month":"04","project":[{"call_identifier":"H2020","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"}],"ddc":["000"],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783031572555"]},"external_id":{"arxiv":["2401.07548"],"isi":["001284187100011"]},"doi":"10.1007/978-3-031-57256-2_11","file_date_updated":"2024-05-22T07:24:45Z","type":"conference","language":[{"iso":"eng"}],"date_published":"2024-04-06T00:00:00Z","publisher":"Springer Nature"},{"status":"public","abstract":[{"text":"We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time 2o(k log k) · nO(1), where k is the number of pairs of vertex subsets involved in the winning condition and n is the vertex count of the game graph. While this result follows from the lower bounds provided by Calude et al [SIAM J. Comp. 2022], our reduction is considerably simpler and arguably provides more insight into the complexity of the problem. In fact, the analogous lower bounds discussed by Calude et al, for solving Muller games and multidimensional parity games, follow as simple corollaries of our approach. Our reduction also highlights the usefulness of a certain pivot problem — Permutation SAT — which may be of independent interest.","lang":"eng"}],"publication_status":"published","article_processing_charge":"No","page":"160-167","title":"Simple and tight complexity lower bounds for solving Rabin games","year":"2024","scopus_import":"1","publication":"2024 Symposium on Simplicity in Algorithms","day":"01","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2310.20433","open_access":"1"}],"department":[{"_id":"ToHe"}],"OA_type":"green","arxiv":1,"ec_funded":1,"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-04-14T07:55:54Z","oa":1,"acknowledgement":"This work is a part of projects CUTACOMBS (Ma. Pilipczuk), BOBR (Mi. Pilipczuk), and VAMOS (K. S. Thejaswini) that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, grant agreements No 714704, 948057, and 101020093, respectively. Ma. Pilipczuk is also partially supported by Polish National Science Centre SONATA BIS-12 grant number 2022/46/E/ST6/00143.","citation":{"ieee":"A. Casares, M. Pilipczuk, M. Pilipczuk, U. S. Souza, and K. S. Thejaswini, “Simple and tight complexity lower bounds for solving Rabin games,” in <i>2024 Symposium on Simplicity in Algorithms</i>, Alexandria, VA, United States, 2024, pp. 160–167.","short":"A. Casares, M. Pilipczuk, M. Pilipczuk, U.S. Souza, K.S. Thejaswini, in:, 2024 Symposium on Simplicity in Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 160–167.","apa":"Casares, A., Pilipczuk, M., Pilipczuk, M., Souza, U. S., &#38; Thejaswini, K. S. (2024). Simple and tight complexity lower bounds for solving Rabin games. In <i>2024 Symposium on Simplicity in Algorithms</i> (pp. 160–167). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977936.16\">https://doi.org/10.1137/1.9781611977936.16</a>","mla":"Casares, Antonio, et al. “Simple and Tight Complexity Lower Bounds for Solving Rabin Games.” <i>2024 Symposium on Simplicity in Algorithms</i>, Society for Industrial and Applied Mathematics, 2024, pp. 160–67, doi:<a href=\"https://doi.org/10.1137/1.9781611977936.16\">10.1137/1.9781611977936.16</a>.","ama":"Casares A, Pilipczuk M, Pilipczuk M, Souza US, Thejaswini KS. Simple and tight complexity lower bounds for solving Rabin games. In: <i>2024 Symposium on Simplicity in Algorithms</i>. Society for Industrial and Applied Mathematics; 2024:160-167. doi:<a href=\"https://doi.org/10.1137/1.9781611977936.16\">10.1137/1.9781611977936.16</a>","ista":"Casares A, Pilipczuk M, Pilipczuk M, Souza US, Thejaswini KS. 2024. Simple and tight complexity lower bounds for solving Rabin games. 2024 Symposium on Simplicity in Algorithms. SOSA: Symposium on Simplicity in Algorithms, 160–167.","chicago":"Casares, Antonio, Marcin Pilipczuk, Michał Pilipczuk, Uéverton S. Souza, and K. S. Thejaswini. “Simple and Tight Complexity Lower Bounds for Solving Rabin Games.” In <i>2024 Symposium on Simplicity in Algorithms</i>, 160–67. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977936.16\">https://doi.org/10.1137/1.9781611977936.16</a>."},"author":[{"last_name":"Casares","full_name":"Casares, Antonio","first_name":"Antonio"},{"first_name":"Marcin","full_name":"Pilipczuk, Marcin","last_name":"Pilipczuk"},{"last_name":"Pilipczuk","first_name":"Michał","full_name":"Pilipczuk, Michał"},{"last_name":"Souza","full_name":"Souza, Uéverton S.","first_name":"Uéverton S."},{"full_name":"Thejaswini, K. S.","first_name":"K. S.","last_name":"Thejaswini","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753"}],"OA_place":"repository","_id":"18955","date_created":"2025-01-29T11:55:50Z","oa_version":"Preprint","month":"01","publication_identifier":{"isbn":["9781611977936"]},"project":[{"call_identifier":"H2020","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"}],"external_id":{"arxiv":["2310.20433"]},"type":"conference","doi":"10.1137/1.9781611977936.16","conference":{"end_date":"2024-01-10","location":"Alexandria, VA, United States","name":"SOSA: Symposium on Simplicity in Algorithms","start_date":"2024-01-08"},"language":[{"iso":"eng"}],"publisher":"Society for Industrial and Applied Mathematics","date_published":"2024-01-01T00:00:00Z"}]