@inproceedings{21020,
  abstract     = {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.
In 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.
The 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.},
  author       = {Henzinger, Thomas A and Karimi, Mahyar and Thejaswini, K. S.},
  booktitle    = {Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security},
  isbn         = {9798400715259},
  location     = {Taipei, Taiwan},
  pages        = {2774--2787},
  publisher    = {Association for Computing Machinery},
  title        = {{Privacy-preserving runtime verification}},
  doi          = {10.1145/3719027.3765137},
  year         = {2025},
}

@inproceedings{20290,
  abstract     = {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.},
  author       = {Brice, Léonard and Henzinger, Thomas A and Thejaswini, K. S.},
  booktitle    = {50th International Symposium on Mathematical Foundations of Computer Science},
  isbn         = {9783959773881},
  issn         = {1868-8969},
  location     = {Warsaw, Poland},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Finding equilibria: Simpler for pessimists, simplest for optimists}},
  doi          = {10.4230/LIPIcs.MFCS.2025.30},
  volume       = {345},
  year         = {2025},
}

@inproceedings{20291,
  abstract     = {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.
The 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.},
  author       = {Henzinger, Thomas A and Prakash, Aditya and Thejaswini, K. S.},
  booktitle    = {50th International Symposium on Mathematical Foundations of Computer Science},
  isbn         = {9783959773881},
  issn         = {1868-8969},
  location     = {Warsaw, Poland},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Resolving nondeterminism with randomness}},
  doi          = {10.4230/LIPIcs.MFCS.2025.57},
  volume       = {345},
  year         = {2025},
}

@inproceedings{21281,
  abstract     = {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.
The 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.
To 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. 
We 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.},
  author       = {Asadi, Ali and Brice, Leonard and Chatterjee, Krishnendu and Thejaswini, K. S.},
  booktitle    = {45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  isbn         = {9783959774062},
  location     = {Pilani, India},
  pages        = {9:1--9:17},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{ε-stationary Nash equilibria in multi-player stochastic graph games}},
  doi          = {10.4230/lipics.fsttcs.2025.9},
  volume       = {360},
  year         = {2025},
}

@inproceedings{15377,
  abstract     = {We provide an algorithmto solve Rabin and Streett games over graphs
with n vertices,m edges, and k colours that runs in ˜O³mn(k!)1+o(1)´time and
O(nk logk logn) space, where ˜O hides poly-logarithmic factors. Our algorithm
is an improvement by a super quadratic dependence on k! from the currently
best known run time of O³mn2(k!)2+o(1)´, obtained by converting a Rabin
gameinto a parity game,while simultaneously improving its exponential space
requirement.
Our main technical ingredient is a characterisation of progress measures for
Rabin games using colourful trees and a combinatorial construction of succinctlyrepresented,
universal colourful trees. Colourful universal trees are generalisations
of universal trees used by Jurdzi´nski and Lazi´c (2017) to solve parity
games, as well as of Rabin progress measures of Klarlund and Kozen (1991).
Our algorithm for Rabin games is a progress measure lifting algorithm where
the lifting is performed on succinct, colourful, universal trees.},
  author       = {Majumdar, Rupak and Sağlam, Irmak and Thejaswini, K. S.},
  booktitle    = {30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems},
  isbn         = {9783031572555},
  issn         = {1611-3349},
  pages        = {213--231},
  publisher    = {Springer Nature},
  title        = {{Rabin games and colourful universal trees}},
  doi          = {10.1007/978-3-031-57256-2_11},
  volume       = {14572},
  year         = {2024},
}

@inproceedings{18955,
  abstract     = {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.},
  author       = {Casares, Antonio and Pilipczuk, Marcin and Pilipczuk, Michał and Souza, Uéverton S. and Thejaswini, K. S.},
  booktitle    = {2024 Symposium on Simplicity in Algorithms},
  isbn         = {9781611977936},
  location     = {Alexandria, VA, United States},
  pages        = {160--167},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Simple and tight complexity lower bounds for solving Rabin games}},
  doi          = {10.1137/1.9781611977936.16},
  year         = {2024},
}

