We investigate two-player win/lose games over finite graphs. In all generality, these games are concurrent, i.e. at each state of the graph, there is a concurrent interaction between the two players to determine the next state visited. In the special case where, at every state of the graph, there are no real concurrent interaction, i.e. only one player is truly playing, the game is turn-based. Various desirable properties hold on turn-based games, but do not on arbitrary concurrent games; e.g. there exist subgame optimal strategies in all prefix-independent turn-based games, while there do not in very simple prefix-independent concurrent games. A possible way to circumvent this issue is to define a subclass of concurrent games, that is a proper superclass of turn-based games, while enjoying several of their nice properties. The goal of this talk is to introduce such a subclass of concurrent games, namely finitely maximizable games, and to show step by step how we came up with this definition. The novel way that we use to define such a subclass of well-behaving concurrent games constitutes a promising approach for investigating more general concurrent games, such as non-antagonistic two-player games, or even multi-player games.

Presentations given by students who will be presenting at JGA 2024.

Hector Buffière: Shallow vertex minors, stability, and dependence (abstract: https://jga2024.sciencesconf.org/579556)

Renaud Torfs: Biclique maximum des graphes Star_1,2,3-free sans jumeau et des graphes de bimodularwidth bornée (abstract: https://jga2024.sciencesconf.org/579711)

Guillaume Aubian: Une construction de graphes de grand nombre chromatique sans triangle (abstract: https://jga2024.sciencesconf.org/581565)

Jules Bouton Popper: Comment rendre un graphe temporel connecté ? (abstract: https://jga2024.sciencesconf.org/581190)

In recent years, there has been much work done in probabilistic semantics. Most of them fall in one of two categories; those based on monads and those based on linear logic. At the semantic level, these two different semantics correspond to distinct basic programming abstractions. In this case, semantically, programming with monads corresponds to programming with Markov kernels, while linear logic corresponds to programming with linear operators.

In this talk I will go over recent work of mine that tries to establish a formal connection between these two families of semantics. I will start by presenting a new core calculus for programming with Markov kernels and linear operators, will show that this formalism encompasses useful models from the probabilistic semantics literature and will conclude by sketching some applications of this formalism to the new research program of synthetic probability theory.

Since the beginning of modern cryptography, the question of secure computation (MPC) has been extensively studied. MPC allows for a set of parties to perform some joint computation while ensuring that their input remains secure up to what is implied by the output. The massive development of our daily Internet usage makes the need for secure computation methods more urgent: computations on private data is everywhere, from recommendation algorithms to electronic auctions. Modern MPC algorithms greatly benefit from correlated randomness to achieve fast online protocols. Correlated randomness has to be massively produced beforehand for the MPC protocols to work best, and this is still a challenge to do efficiently today.

In this thesis, we study pseudorandom correlation generators (PCGs). This construction transforms a small amount of correlated randomness into a large amount of correlated pseudorandomness with minimal interaction and local computation. We present different PCG constructions whose security relies on variants of the Syndrome Decoding (SD) assumption, a classical assumption in coding theory. The intuition behind these constructions is to merge the SD assumption with some MPC techniques that enable additively sharing sparse vectors. We achieve state-of-the-art results regarding secure computation protocols requiring more than two players when the computation is over a finite field of size > 2. We show how to remove this constraint at the cost of a small overhead in communication.

Next, we consider the construction of pseudorandom correlation functions (PCFs). PCFs produce correlations on-the-fly: players each hold correlated functions such that the outputs of the functions, when evaluated on the same entry, are correlated. These objects offer more flexibility than PCGs but are also harder to construct. We again rely on variants of SD to construct PCFs. We build on a previous PCF construction, showing that the associated proof of security was incorrect, and propose a correction. Additionally, we present optimizations of the construction, coming from a better analysis and precise optimization of parameters via simulations. We achieve parameters usable in practice.

Finally, this thesis revolves around the use of certain codes, particularly the SD assumption. The search for good complexity entails efforts to find the most efficient codes while ensuring that security is not compromised. We consider a framework tailored to the study of promising attacks on SD and its variants. For each construction previously mentioned, we conduct a thorough security analysis of the associated variant of SD and attempt cryptanalysis efforts to compute concrete parameters.

It is known that the partition function $p(n)$ obeys Benford's law in any integer base $b\ge 2$. A similar result was obtained by Douglass and Ono for the plane partition function $\text{PL}(n)$ in a recent paper. In their paper, Douglass and Ono asked for an explicit version of this result. In particular, given an integer base $b\ge 2$ and string $f$ of digits in base $b$ they asked for an explicit value $N(b,f)$ such that there exists $n\le N(b,f)$ with the property that $\text{PL}(n)$ starts with the string $f$ when written in base $b$. In my talk, I will present an explicit value for $N(b,f)$ both for the partition function $p(n)$ as well as for the plane partition function $\text{PL}(n)$.

Contextual equivalence is the de facto standard notion of program equivalence. A key theorem is that contextual equivalence is an equational theory. Making contextual equivalence more intensional, for example taking into account the time cost of the computation, seems a natural refinement. Such a change, however, does not induce an equational theory, for an apparently essential reason: cost is not invariant under reduction.

In the paradigmatic case of the untyped λ-calculus, we introduce interaction equivalence. Inspired by game semantics, we observe the number of interaction steps between terms and contexts but—crucially—ignore their own internal steps. We prove that interaction equivalence is an equational theory and we characterize it as B, the well-known theory induced by Böhm tree equality. Ours is the first observational characterization of B obtained without enriching the discriminating power of contexts with extra features such as non-determinism. To prove our results, we develop interaction-based refinements of the Böhm-out technique and of intersection types.

Deterministic two-way transducers capture the class of regular functions. The efficiency of composing two-way transducers has a direct implication in algorithmic problems related to synthesis, where transformation specifications are converted into equivalent transducers. These specifications are presented in a modular way, and composing the resultant machines simulates the full specification. In this talk, I will present how we can achieve efficient composition of two-way transducers, mainly through the use of Reversible Transducers. Reversible machines are machine that are both deterministic and codeterministic. I will show how any two-way transducers can be made reversible, while being easily composable. I will also show how these results can be extended to the setting of infinite words, which is the dedicated setting for model-checking for example.