IRIF Cake^TM is an amazing opportunity to meet people while simultaneously eating cakes baked by your fellow colleagues! Join us every Thursday, at 5pm, in front of room 3052 (Sophie Germain 3rd floor) for a weekly feast. You can also express your cooking skills and volunteer to bake a cake by sending an email to cake@irif.fr.

The Partially asymmetric exclusion process (PASEP) is a physical model viewed as a Markov chain representing the displacement of particles over a finite line. The steady-state probabilities of this chain can be computed by enumerating permutations according to certain statistics. These probabilities have a natural connexion with some transition matrices, in the algebra of noncommutative symmetric functions, which implies a refinement of the probabilities of the PASEP using statistics on permuations. We place ourself in the context of the 2-PASEP, the PASEP with two kind of particles, and exhibit a connexion with the free algebra indexed by segmented compositions using statistics on partially signed permutations.

In this talk I will review G4ip, a simple calculus for intuitionistic propositional logic (IPL) that provides a decision procedure for provability. Its basic mechanisms can be traced back to Vorob'ev in the 50s, and were found again by Hudelmaier (88), Dyckhoff (90), Paulson (91), and (with a linear logic flavour) Lincoln-Scedrov-Shankar (91). In 2015, Claessen and Rosén presented the fastest decision procedure for IPL, based on SMT-solving techniques. We describe their algorithm and show how it can be seen as a variant of the aforementioned calculus, albeit with key variations that provide increased performance. Their algorithm relies on a SAT-solver used as a black box and treats intuitionistic entailment as a theory. We show how the recent framework of model-constructing satisfiability for SMT-solving could further integrate intuitionistic reasoning within the main SAT-solving loop. This would constitute an intuitionistic variant of the main algorithm of SAT-solvers, where Kripke models are built instead of Boolean models.

We present a new model of probabilistically checkable proof (PCP), which we call “Distributed PCP”: A satisfying assignment (x in {0,1}^n) to a SAT instance is shared between two parties (Alice knows x_1, … x_{n/2}, and Bob knows x_{n/2+1},…,x_n). Their goal is to jointly write a PCP for x, while exchanging little or no information.

Using our new framework, we obtain, for the first time, PCP-like hardness of approximation results for problems in P.

Based on joint works with Amir Abboud, Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy Rothblum, and Ryan Williams.

En 2015, Jeandel et Rao ont démontré par des calculs exhaustifs faits par ordinateur que tout ensemble de tuiles de Wang de cardinalité ≤ 10 soit admettent un pavage périodique du plan Z² soit n'admettent aucun pavage du plan. De plus, ils ont trouvé un ensemble de 11 tuiles de Wang qui pavent le plan mais jamais de façon périodique. Dans cet exposé, nous présenterons une définition alternative des pavages apériodiques de Jeandel-Rao comme le codage d'une Z²-action sur le tore et nous décrivons la structure substitutive de ces pavages.

Depuis les années 60, la sémantique s'est avérée très utile pour introduire des langages de haut niveau permettant d'écrire des programmes complexes et de les comprendre à un niveau mathématique précis. Dans les années 80, la logique linéaire a été introduite par Girard, reflétant des propriétés sémantiques liées à l'utilisation des ressources. Cette direction a été poursuivie par Ehrhard dans les années 2000 avec l'introduction du lambda-calcul différentiel. Dans ces modèles, les programmes sont approximés par des polynômes, dont les monômes représentent les appels d'un programme à ses entrées lors de son exécution. Cette approche analytique a constitué un outil crucial pour l'étude des propriétés quantitatives apparaissant dans les langages de programmation probabiliste. En parallèle, depuis les années 90, plusieurs modèles géométriques ont été développés pour représenter des traces d'exécution dans les systèmes distribués. Dans cette thèse d'habilitation, nous présentons des modèles que nous avons étudiés dans ces trois domaines : les systèmes distribués, le lambda-calcul différentiel, la programmation probabiliste, ainsi que les techniques générales nécessaires et les résultats qu'ils nous ont permis d'obtenir. Celles-ci ont nécessité l'utilisation et le développement d'outils issus de la combinatoire, de la topologie dirigée, de l'analyse fonctionnelle, de la théorie des catégories et des probabilités.

En collaboration avec des chercheurs en biologie à Jussieu, nous étudions des graphes issus de données biologiques afin de d'en améliorer la compréhension. Ces graphes sont constitués à partir de fragments d'ADN, nommés reads. Chaque read correspond à un sommet, et deux sommets sont reliés si les deux séquences d'ADN correspondantes ont un taux de similarité suffisant. Ainsi se forme des graphes ayant une structure bien particulière que nous nommons hub-laminaire. Un graphe est dit hub-laminaire s'il peut être résumé en quelques plus courts chemins dont tous les sommets du graphe soient proche. Nous étudions en détail le cas où le graphe est composé d'un unique plus court chemin d'excentricité faible. Nous améliorons la preuve d'un algorithme d'approximation déjà existant et en proposons un nouveau, effectuant une 3-approximation en temps linéaire. De plus, nous analysons le lien avec le problème de k-laminarité défini par Michel Habib et Finn Völkel, ce dernier consistant en la recherche d'un diamètre de faible excentricité. Nous étudions ensuite le problème du cycle isométrique de plus faible excentricité. Nous montrons que ce problème est NP-complet et proposons deux algorithmes d'approximations. Nous définissons ensuite précisément la structure “hub-laminaire” et présentons un algorithme d'approximation en temps O(nm). Nous confrontons cet algorithme à des graphes générés par une procédure aléatoire et l'appliquons à nos données biologiques. Pour finir nous montrons que le calcul du cycle isométrique d'excentricité minimale permet le plongement d'un graphe dans un cercle avec une distorsion multiplicative faible. Le calcul d'une décomposition hub-laminaire permet quant à lui une représentation compacte des distances avec une distorsion additive bornée.

Agreeing on a common value in a distributed system is a problem that lies at the heart of many distributed computing problems and occurs in several flavors. Unfortunately, even modest network dynamics already prohibit solvability of exact consensus, where agents have to decide on a single output value that is within the range of the agents' initial values.

For many problems (distributed control, clock synchronization, load balancing, …) it is however sufficient to asymptotically converge to the same value, or decide on values not too far from each other. We study solvability of these consensus variants in highly dynamic networks, provide time complexity results, and present fast algorithms. We then show how the results on dynamic networks are relevant for classical fault-models, such as asynchronous message passing with crashes.

The talk is on previous and current research with Bernadette Charron-Bost (LIX), Thomas Nowak (LRI), and Manfred Schwarz (ECS, TU Wien).

We provide syntactic (expression-level) language derivative operations, both in the styles of Brzozowski and Antimirov, for trace closures of regular word languages wrt. an independence relation on the alphabet. The Brzozowski and Antimirov style derivatives essentially define functional resp. relational small-step operational semantics of an (abstracted) sequential programming language where some instructions, given by the independence relation, can be reordered without any observable consequences. Our development is motivated by the fact that some aspects of relaxed memories can be explained by allowing the threads of a concurrent program to be reordered in this manner.

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ \EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ \EQ_n$ is $\Omega(\deg(f) \cdot n)$. However, there is a surprising counter-example of a partial function $f$ on $p$ bits, such that any completion $f'$ of $f$ has $\deg(f') = \Omega(p)$, and yet $f \circ \EQ_n$ has communication complexity $O(n)$. Nonetheless, we are able to show that the communication complexity of $f \circ \EQ_n$ is at least $D(f) \cdot n$ for a complexity measure $D(f)$ which is closely related to the $\AND$-query complexity of $f$ and is lower-bounded by the logarithm of the leaf complexity of $f$. As a corollary, we also obtain lifting theorems for the set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the $\NOR$ gadget.

In this talk, I will talk about simulations or lifting theorems in general from a previous work of Chattopadhyay et al., and lifting theorem for Equality in particular—especially why the general recipe of Chattopadhyay et al. does not work for Equality. I will also mention an application of this technique to prove tight communication lower bound for Gap-Equality problem. This is a joint work with Bruno Loff.