Schedule

We prove an exponential separation between classical and quantum communication complexity for synthesizing quantum circuits with succinct structure. Consider the task where Alice holds a specification of an n-qubit circuit from a structured family (e.g., k-sparse permutations, parameterized fault-tolerant gadgets, or tensor network circuits with bond dimension k), and Bob must synthesize a concrete circuit implementation using his quantum computer. We show that classical communication protocols require Ω(k·polylog(n)) bits, while quantum protocols achieve the same task with O(log k + log n) qubits—an exponential improvement when k = poly(n). The proof uses amplitude encoding combined with quantum parameter extraction via Grover-style query algorithms.

The key insight connects to automata-theoretic games: classical synthesis corresponds to solving reachability games on automata of size 2^Ω(k), while quantum protocols exploit the exponential state-space compression of quantum finite automata. This separation implies that for structured circuits ubiquitous in quantum error correction—where classical synthesis algorithms based on graph games provably require exponential space—quantum communication provides a genuine computational advantage. Our results suggest the "right" model for synthesis in the quantum regime isn't classical automata games, but rather their quantum generalizations.

In multiplayer games played on graphs, as soon as randomness is involved (because the game is stochastic or because the players are allowed to randomise their strategies), deciding the existence of a Nash equilibrium that satisfies a given constraint, for example such that the players' payoffs lie in specified intervals, is undecidable in all reasonable settings. However, these results rely on a definition of Nash equilibria that implies that each player intends to maximise their expected payoff, which is not always the most rational behaviour: their tolerance to risk may vary. In this talk, we consider the pessimistic risk measure, which interprets randomness by considering the worst possible scenario, and its dual, the optimistic risk measure. We define from those notions a new notion of equilibrium, the extreme risk-sensitive equilibrium, and show that the constrained existence problem of such an equilibrium is decidable.

The window mean-payoff objective strengthens the classical mean-payoff objective by computing the mean-payoff over a finite window that slides along an infinite path. In this talk, we will look at the problem of synthesizing strategies in Markov decision processes that maximize the window mean-payoff value in expectation, while also simultaneously guaranteeing that the value is above a certain threshold. We solve the synthesis problem for three different kinds of guarantees: sure (that needs to be satisfied in the worst-case, that is, for an adversarial environment), almost-sure (that needs to be satisfied with probability one), and probabilistic (that needs to be satisfied with at least some given probability p). 

This is based on joint work with Shibahsis Guha that was accepted in AAMAS 2025.

In a seminal work, [Gibbons and Korach, '97] studied the complexity of deciding whether an observed sequence of reads and writes of a multi-threaded program admits a sequentially consistent interleaving. They showed the problem to be NP-hard even under strong syntactic restrictions. More recently, [Chakraborty et al., '24]  considered the problem for weak memory models and proved that NP-hardness remains even when the number of threads, the number of memory locations, and the value domain are all bounded.

In this paper we revisit the problem for the release–acquire variants of the C11 memory model. Our main positive result is that consistency checking can be done in polynomial-time when each memory location is written by at most one thread (multiple readers are allowed). Notably, this restriction is already NP-hard for sequential consistency. We complement this upper bound with tight hardness results: the problem is NP-hard when two threads may write to the same location, and allowing four writers per location rules out 2^{o(k)} algorithms under the Exponential Time Hypothesis, where k denotes the number of threads.

Mazurkiewikz traces are a well known model of concurrency. I will talk about logics over Mazurkiewikz traces which are amenable to translations to cascade products of simple asynchronous automata. 

The results I will talk about are from our: 

LICS 2024 paper: "An expressively complete local past propositional dynamic logic over Mazurkiewicz traces and its applications" 

and CONCUR 2025 paper : "Characterizations of Fragments of Temporal Logic over Mazurkiewicz Traces"