Talk 1 (Abhishek): How can someone from PPS chat up someone from ASD or ASV?

PPS looks at abstractions of programming languages and studies logics motivated to better understand these abstractions. How can tools developed here be used in other fields like automata theory and complexity theory? In this talk, I will give some ideas roughly along the lines of implicit complexity and hope to forge further collaborations between the 3rd floor and 4th floor.

Talk 2 (Pierre): What does it take to hide patterns of communication?

Secure Multiparty Computation (MPC) allows N mutually distrusting parties to perform some computation f(x_1,…,x_N) without having to reveal anything about their private inputs x_1,…,x_N beyond what is revealed by the output of the computation itself. Making sure that “adversaries”, which are internal to the system rather than external, cannot learn more information than they should is a well-understood task in the setting where any pair of parties can communicate directly (and privately). However, in many scenarios, setting up a complete communication network is impractical (e.g. too expensive) or impossible (e.g. some parties may outright refuse to communicate with some others). Therefore, we consider the more realistic setting where the parties are nodes in some incomplete graph, and can communicate only along the edges. In fact, knowledge of this network could be kept private too: each party knows who they are talking to but they do not need to know the metadata of how others are communicating, which may be sensitive information. There are two difficulties to achieving this extra privacy requirement: (1) the MPC protocol must be run even if the each party only knows their local view of the network (i.e. their neighbourhood), and (2) the MPC protocol should reveal nothing more about the graph.

In this talk, we will try and understand how hard this task is by relating it to a foundational hierarchy of cryptographic primitives: - Secure Communication: Two parties need to communicate privately even in the presence of an external eavesdropper monitoring all their interactions. - Secure Computation: Two parties need to compute some function without trusting each other with their inputs. Prerequisites: No background in cryptography is required.

Talk 1 (Corentin): Combinatorics of fighting fishes and related structures

Fighting fishes are combinatorial objects generalizing parallelogram polyominoes introduced in 2016 by Duchi et al. The enumeration of these objects with respect to their natural parameter of size (the half-perimeter) leads to a sequence that counts also other objects : two-stack sortable permutations, non-separable planar rooted maps, synchronized intervals of the Tamari lattice. In this presentation, I will define some bijections between fighting fishes and other objects that preserve a lot of structure and statistics, and I will give some perspectives about the generalization of considered objects and bijections.

Talk 2 (Simon): Random models for stable matching

In a two sided matching market, two types of agents have preferences over one another. Examples include college admissions (students and colleges), residency programs (doctors and hospitals), job markets (workers and jobs) and, in the classical analogy, stable marriages (men and women). In a founding paper, Gale and Shapley introduced the deferred acceptance procedure, where one side proposes and the other disposes, which computes a stable matching. In the worst case, the choice of which side of the market proposes has a big importance, both in terms of outcome (the output matching is optimal for the proposing side) and truthfulness (the receiving side might have incentives to lie). We will show that things are much nicer in the average case. Assuming that preferences of agents are drawn from certain distributions, then each agent receives with high probability the same allocation in the two variants of deferred acceptance.

Recoloring is a reconfiguration problem : given a graph and two proper coloring of this graph, how to recolor from one coloring to the other by a series of elementary changes ? The talk will be based on the Distributed Recoloring paper from Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, and Jara Uitto (Disc 2018) which introduced the notion of distributed recoloring as follow : the input graph represent a network of computers that need to be recolored. Each node know its input color and its target color. Nodes are allowed to exchange messages with each other synchronously and, given rounds of messages, each node have to output its recoloring schedule, indicating when the node changes its color and to which color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. This paper gave a lot of results for different situations of coloring (different types of graph, different number of color, different number of extra color), particularly problems with 1 extra colors, and left some open questions. I will present some results we have on some of those open questions.

In this talk, I will give a combinatorial proof of the Chernoff-Hoeffding concentration bound, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs, this proof does not use the method of higher moments, but rather uses a simple and intuitive counting argument. In addition, this proof is constructive in the following sense: if the sum of the given random variables is not concentrated around the expectation, then we can efficiently find (with high probability) a subset of the random variables that are statistically dependent. This talk is based on the paper “Constructive Proofs of Concentration Bounds” by Russell Impagliazzo and Valentine Kabanets.