Zero-sum stochastic games, henceforth stochastic games, are a classical model in game theory in which two opponents interact and the environment changes in response to the players’ behavior. The central solution concepts for these games are the discounted values and the value, which represent what playing the game is worth to the players for different levels of impatience. In the present manuscript, we provide algorithms for computing exact expressions for the discounted values and for the value, which are polynomial in the number of pure stationary strategies of the players. This result considerably improves all the existing algorithms.

Years ago Zeev Rudnick defined the Poisson generic real numbers as those where the number of occurrences of the long strings in the initial segments of their fractional expansions in some base have the Poisson distribution. Yuval Peres and Benjamin Weiss proved that almost all real numbers, with respect to Lebesgue measure, are Poisson generic. They also showed that Poisson genericity implies Borel normality but the two notions do not coincide, witnessed by the famous Champernowne constant. We recently showed that there are computable Poisson generic real numbers and that all Martin-Löf real numbers are Poisson generic.

This is joint work Nicolás Álvarez and Martín Mereb.

Parmi les techniques de détection automatisée de tests, le fuzzing gagne chaque année en popularité.

Cette technique permet d'explorer rapidement la surface d'un programme grâce à la génération automatique rapide de cas de tests, parfois guidée par exemple par des mesures de couverture.

En revanche, dès que le programme contient des conditions spécifiques (par exemple, x = 0x42, où x a été lu depuis l'entrée utilisateur), la probabilité qu'un fuzzeur génère une solution est assez faible.

On propose d'améliorer les perfomances du fuzzeur AFL en le combinant avec une analyse symbolique, qui analysera les traces des cas de tests générés, pour identifier ces conditions (par exemple, on aurait input[0] = 0x0042). On en déduit des prédicats de chemins sous-approximés, qu'on appelle “facilement énumérable”, et dont les solutions sont directement générées par notre fuzzeur modifié.

L'outil ainsi créé, ConFuzz, est intégré à la plateforme d'analyse de code binaire Binsec, développée au CEA List, et a été testé sur LAVA-M, un banc de test standard en fuzzing.

Graph transformation allows to extend formal language theory to the generation of graph languages. This has applications in areas such as model-driven software engineering, natural language processing, and shape analysis of programs.

We start from the well-established theory of context-free grammars based on hyperedge replacement (HR) and introduces a modest extension, contextual hyperedge replacement (CHR), in order to extend their generative power. We discuss the generative power and other properties of CHR, and relate them to HR.

Then we consider parsing for CHR grammars. As for HR, parsing is NP-complete in general, so that efficient parsing algorithms can only be achieved for subclasses. We have devised two algorithms, called predictive top-down (PTD) and predictive shift-reduce (PSR), which are inspired by the well-known LL(k) and LR(k) parsing for strings, and are usually linear, at most quadratic. We illustrate the ideas of these algorithms by graph transformation rules.

Finally we demonstrate Mark Minas' graph parser generator Grappa, which implements not only PTD and PSR parsing, including the needed analysis tools, but also generalized PSR, where parallel parsing allows to cope with ambiguous grammars. Measurements of generated parsers validate our theoretical findings regarding complexity.

Zoom meeting registration link

YouTube live stream

We introduce an explicit construction for a key distribution protocol in the Quantum Computational Timelock (QCT) security model, where one assumes that computationally secure encryption may only be broken after a time much longer than the coherence time of available quantum memories. Taking advantage of the QCT assumptions, we build a key distribution protocol called HM-QCT from the Hidden Matching problem for which there exists an exponential gap in one-way communication complexity between classical and quantum strategies. We establish that the security of HM-QCT against arbitrary attacks can be reduced to the difficulty of solving the underlying distributed problem with classical information, while legitimate users can use quantum communication. This leads to a HM-QCT key distribution scheme over n bosonic modes that can be secure with up to O(sqrt(n)/log(n)) input photons per channel use, boosting key rates by several orders of magnitude compared to QKD and allowing to operate with a non-trusted receiver.

Classical sequences of numbers often lead to interesting q-analogues. The most popular among them are certainly the q-integers and the q-binomial coefficients which both appear in various areas of mathematics and physics. With Valentin Ovsienko we recently suggested a notion of q-rationals based on combinatorial properties and continued fraction expansions. The definition of q-rationals naturally extends the one of q-integers and leads to a ratio of polynomials with positive integer coefficients. I will explain the construction and give the main properties. In particular I will briefly mention connections with the combinatorics of posets, cluster algebras, Jones polynomials, homological algebra. Finally I will also present further developments of the theory, leading to the notion of q-irrationals and q-unimodular matrices.