Stone spaces appear at the interface of computer science, logic and general mathematics. In this talk, we will give a gentle introduction to Stone spaces, distilling a few key examples that illustrate their peculiarities in an accessible way. We will also be hinting towards Stone duality and other related topics, such as applications in automata theory. No prerequisites.

In this presentation, I will provide an introduction to proof theory within the context of non-wellfounded proof systems. A non-wellfounded proof is generated by finitely branching logical rules, but potentially resulting in an infinitely deep proof tree. After defining the system, I will present a proof of cut-elimination for the $\mu$-MALL system, drawing from the work of Baelde et al. in 2016. Furthermore, I will discuss how we aim to extend this result with Alexis Saurin.

In this talk, I'll present the first inductive characterization of the useful evaluation for open call-by-value, with its results. We achieve such characterization by parameterizing the evaluation relation with the information provided by the context in which the computation takes place. Then, we study some of its properties, and compare it with other evaluation strategy. Lastly, we propose a quantitative type system (with tight rules) for the strategy.

I will present ongoing work about densities of regular languages under invariant measures of minimal shift spaces, which will serve as a pretext for an introduction to symbolic dynamics, with some algebra and ergodic theory thrown in the mix.

Two-party computation occasionally enables more efficient protocols compared to even three party computation. Two important building blocks enabling efficient two-party protocols are (1) distributed point functions (DPFs) and homomorphic secret sharing (HSS). In this talk, we will examine what properties enables these building blocks and why they are primarily restricted to the two party setting. This will provide insights into why multi-party computation protocols are more difficult to design and what assumptions allow us to circumvent these barriers.

Agreement tasks, e.g. consensus, k-set agreement, have been intensively studied in distributed computing for the last 30 years. A natural question is to find better lower bounds on the number of rounds for algorithms solving agreement tasks. In this talk, I will first define Local and Know-all models, agreement tasks, and some basic notions in combinatorial topology. Then, I will give an example to see a relation between the solvability of consensus and the path connectivity of a protocol complex. Finally, I will present some useful tools for lower bounds on the round complexity of agreement tasks.

No prior knowledge is required.

This will be a discussion in order to prepare the HCERES meeting. A group of 6 or 7 non permanents members should be constituted, they will meet for 30 minutes with the HCERES comitee the Wednesday 29th of November.

This will be an introductory session where we invite all (new and old!) non-permanent members to come and talk about their research interests. Each talk should be 2-5 minutes long, and understandable by everyone.

In a broadcast network, a node sends a message to all of its neighbors in a synchronous fashion. The communication topology is represented as a graph and each node executes a finite-state automaton. A problem of interest in verification is to determine if such a network allows for a node to reach an error state of the automaton, this is what we will call the coverability problem. When the communication topology is given, this problem is decidable, however, when it is not the case, one needs to check that for all possible communication topologies, an error state is never reached, and the problem becomes undecidable. It is the parameterised version of the coverability problem for broadcast networks, note that neither the number of nodes nor the graph is fixed. I will present this model as well as the undecidability proof before talking about a new restriction on the network aiming to regain decidability. As far as I know (this is some ongoing work), this restriction allows in some very particular cases to regain restrictions but fails in most cases.

This talk will not assume any prior knowledge in verification nor in distributed networks.

We present a layered approach to solve a multi-agent control problem. This methods mixes three domains: timed automata, SMT and reinforcement learning, in order to obtain the best of each: the method based on timed automata solves the combinatorial aspect of the problem, the SMT refine our model into a more realistic one and the two methods are combined into a SWA-SMT solver. Finally, the Reinforcment Learning trains the policy in order to show that the initial dataset generated with the the SWA-SMT solver is crucial for the overall success of the method.

This talk is going to be an introduction to some information theoretic graph parameters. Perhaps the most famous of these is the Shannon capacity which can be described as follows. Over a communication channel the sender can send some characters and on the other side some pairs of these characters are distinguishable to the receiver, but some pairs of them are confusable with positive probability. We can construct a graph of this channel: the vertices are the characters, and two of them are connected by an edge if they are distinguishable. If we want zero-error in the communication, then the maximum number of distinguishable messages of length 1 is just the clique number of this graph, and the maximum number of longer messages of fixed length is the clique number of some power of this graph. The Shannon capacity is defined as the limit of the normalized values of these clique numbers, and is the theoretical upper bound on the efficiency of zero-error communication over a discrete, memoryless channel. Some other parameters, such as the Sperner capacity or the Witsenhausen rate, can be defined in a similar way and are also of information theoretic relevance. We will discuss these parameters and their relation with other known graph invariants.

The talk is introductory, so we will go through a few examples and skip the difficult proofs. No previous knowledge in information theory is required.

Affine constraints can describe a polytope P : the minimal number of inequalities required for a description is called the size of the polytope (it is its number of facets). For the sake of linear optimization, affine extensions Q of P can be useful : by adding a few extra variables, one can sometimes exponentially decrease the complexity (i.e. the size) of the description. This area has motivated research both in search of lower and upper bounds on the extension complexity (minimal size of an affine extension Q) of polytopes. Equivalent definitions (via non-negative rank, and via randomised communication protocols) of extension complexity xc(P) have been found (Yannakakis, Faenza-Fiorini), we will review them and some upper or lower bounds which use this alternative characterization.

NB : no previous knowledge in polytopes or in complexity theory is required.

Timed automata, as their name suggests, are a kind of automata in which time is taken into account. This is done by the presence of a number of clocks which can be tested or reset. Ever since they were introduced by Rajeev Alur and David L. Dill, they have been very important for modelling real-time systems. This presentation will give an introduction to the topic of timed automata, as well as present some usual tools and concepts for analysing them. Among these is the notion of clock regions, which spawn a very visual way of understanding the behaviour of these automata, and which will allow to state Puri's result characterizing reachability for a path.

Time permitting, I will talk about how starting from these tools, with some necessary additional work, it was possible to establish a characterization of the amount of “information per time unit” generated by a given automaton. This notion of “information” is to be defined during the presentation, it is the one we introduced recently, inspired by Kolmogorov and Tikhomirov's notion of epsilon-entropy.

At some point in our lives, one has to write comprehensive (and long) scientific documents, like a PhD or an habilitation thesis, for instance, or simply a long paper. When on the other side, as a reader or as a reviewer, one has to decipher these documents. Indeed, we discover in them clever ideas, marvellous algorithms, wonderful theorems. But also, one sometimes gets (very) angry and frustrated by the manuscript, because it is written in a way that makes the life hard for the reader.

In this talk, I will try to give some hints that may be of help in such writing processes. I will also talk of some technical tools that may turn to be useful, and in particular the « knowledge package » for LaTeX (that I happened to have written).

We introduce interactive devices and a visual representation of qubits to assist in explaining quantum computing to a broad audience. In this talk we will briefly explain the representation then we will invite the audience to play with games designed to develop intuition on quantum states, entanglement, and quantum circuits. This is the first time we will be testing out our games and we welcome feedback on the experience from audience members.

This is joint work with Loris Perez, Sylvie Tissot and Lou Vettier and the talk is based on the following paper https://arxiv.org/abs/2211.16324

The aim of this talk is to introduce free profinite monoids as a fundamental tool to study rational languages and automata.

From an algebraic perspective, running a finite-state automaton is like computing images under a morphism going to a finite monoid. Taken simultaneously, these morphic images act like a fingerprint which can tell apart words from each other. This also defines a metric, the profinite distance, based on how large monoids need to be in order to separate two given words.

The space defined by this metric is discrete and infinite, hence full of holes. Its metric completion is called the free profinite monoid. It is an intriguing object in which algebra, topology and combinatorics interact in subtle ways. Topologically, it looks like the Cantor space, but it also has an algebraic structure which extends the usual word concatenation.

Inside the free profinite monoid, rational languages turn into clopen subsets by topological closure, while clopen subsets turn back into rational languages by intersection. This back-and-fourth adds to the three classical representations of regular languages – automata, regexes and morphisms – a fourth one, which is purely topological.

Graph databases have recently transitioned from being a niche “old school” idea to the cool new paradigm used in biology, machine learning, banking and social network analysis, just to name a few. Because of this diversity, many data models and query languages have been developed and studied by different communities with few links to one another. In 2019, an ISO committee approved a project to create GQL, a standard Graph Query Language for the “property graph” model. The goal of this talk is to give a (theoretician-friendly) introduction to property graphs and GQL, after a brief review of the historical context that got us here.

Grover algorithm is the second most well-known quantum algorithm after Shor's. If the speedup in complexity it represents is “only” quadratic, its main strength is the generality of its use: finding unknown marked items in a set of mostly unmarked ones, where the set and the marks are arbitrarily defined. In recent years, a distributed version of this algorithm has emerged leading to faster algorithms in the CONGEST model.

In this talk, the basics of quantum computing will first be defined. Afterwards, I will try to give a feel of how the Grover algorithm operates before finally exploring one or two of its applications in the CONGEST model.

In this talk, I will give an introduction to quantum algorithms. First, I will explain what quantum algorithms are. Then, I will elaborate on a canonical example known as Grover's algorithm, which provides a quadratic improvement in query complexity for the unstructured search problem over the best classical algorithm. If time permits, I will end with a discussion on generalizations of this result.

NP-hard problems have many applications in our society, from optimizing industry processes, to transports, and even biology. While we cannot efficiently solve every instance of these problems, we sometimes find that the most common instances have simpler structure, which we can exploit to obtain faster algorithms. Parameterized algorithms focus on solving instances instances where some parameter of the instance is low, such as the maximum degree (of the input graph); the number of dimensions (for input data in the Euclidean space); or the size of the solution.

In this talk, we will give an introduction to parameterized algorithms, starting by some simple examples of problems where this approach is useful. Then, we will turn our focus to a specific parameter, called treewidth, which has lead to many new algorithms and also has some practical applications. We will start by looking at an intuitive view of what treewidth is, and how that intuition can be formally defined; then, we will look at how the treewidth of a graph can be computed; and finally, how we can solve problems in graphs with low treewidth.

This will be an introductory talk, so no prior knowledge is needed!

Program verification is a quite well-known field in computer science research that is still obscure for those out of it. This talk presents one particular case, verification of concurrent programs under weak transactional isolation levels via Dynamic Partial Order Reduction (DPOR). I will first introduce the concept of verification, followed by an introduction of weak memory models and distributed databases using several simple examples. Finally, I will explain dynamic partial order reduction (DPOR) technique used to solve our problem and elaborate on our results. No prior knowledge is expected!

In this talk, we will introduce a space constrained model of computation, aka the Streaming Model. In particular, we will look at a simple algorithm for degeneracy based graph coloring in this model, which was proposed in 2019 and is currently the state of the art (in terms of number of colors used). We will complement the algorithm with a corresponding lower bound which uses a reduction to the problem of indexing in communication complexity and end with an open problem.

No prerequisite is assumed and every notion used will defined in the talk.

This presentation is based on the paper “Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models” by Suman Kalyan Bera, Amit Chakrabarti and Prantar Ghosh.

The study of combinatorial optimization problems with a submodular objective has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. A few examples of such functions include cuts functions of graphs and hypergraphs, rank functions of matroids, and covering functions.

Let $N = {u_1, u_2, ..., u_n}$ be a ground set of elements, A function $F : 2^{\mathcal{N}} \to R_{\geq 0}$ is submodular if for every $A \subset B \subset \mathcal{N}$ and $u \in \mathcal{N} \setminus B$, $F(A\cup\{u\})−F(A) \geq F (B \cup \{u\}) − F (B)$. Since the submodular maximization problem is NP-hard, we will discuss some important approximation algorithms of the constrained versions of the problem in both monotone and non-monotone cases.

One of the most fascinating phenomena in game theory is the Braess paradox, which occurs when adding an additional route to a network leads to increased congestion and travel times for everyone. In this talk, after introducing some basic concepts and presenting the paradox, I will describe a few other scenarios in which improving the productivity of individuals counter-intuitively leads to degraded group productivity.

Secure Multiparty Computation (MPC) is a set of techniques that allows n distrustful parties to perform a computation, e.g. f(x_1,…,x_n), without revealing anything about their private values x_1,…,x_n. In this talk, I want to present some basic but fundamental principles and techniques of the field - ideal vs. real world / secret sharing / Multiplication Triples - and give a taste of what MPC looks like. It will also serve as an introduction to a future talk on my research into pseudorandom correlation generators.

No prior knowledge is required.

Topological Data Analysis (TDA) has recently been getting more and more attention. It models a data set as a simplicial complex, a generalisation of a graph, that is a collection of points having higher order relations among each other. This talk aims at introducing simplicial complexes and some related notions, as well as presenting some algorithmic aspects of calculating and approximating the so-called Betti numbers (the number of high dimensional “holes” in the complex) that can be used to characterise the underlying data set.

Identity testing is a fundamental problem in algorithmic algebra which asks to test equality of two given algebraic expressions. The identity testing problem has many versions according to the syntactic representation of expressions and the ring in which evaluation is carried out. I will introduce different versions of the problem, and then focus on Radical Identity Testing (RIT): Given an algebraic circuit representing a polynomial $f\in \mathbb{Z}[x_1, \dots, x_k]$ and nonnegative integers $a_1, \dots, a_k$ and $d_1, \dots,$ $d_k$, written in binary, test whether the polynomial vanishes at the real radicals $\sqrt[d_1]{a_1}, \dots,\sqrt[d_k]{a_k}$, i.e., test whether $f(\sqrt[d_1]{a_1}, \dots, \sqrt[d_k]{a_k}) = 0$.

In a LICS’22 paper we showed that the RIT problem is in coNP assuming the Generalised Riemann Hypothesis (GRH), improving on the straightforward PSPACE upper bound obtained by reduction to the existential theory of reals. We also considered a restricted version, called 2-RIT, where the radicals are square roots of prime numbers; and showed that 2-RIT is in coRP assuming GRH and in coNP unconditionally.

Our proof relies on theorems from algebraic and analytic number theory, such as the Chebotarev density theorem and quadratic reciprocity, however, no prior knowledge on algebraic circuits, identity testing, or any of the underlying math will be required!

Denotational semantic is a field which consists in studying computation without computing. That is, a program P of type int → int can be seen on a high level as a function from the integers to the integers.

After a quick review of the idea behind denotational semantic, we will show that the word “denotational” can in fact be replaced by the word “categorical”. A program will not be interpreted as a mere function, but rather as a morphism in some category. This enlargement of perspective allows us to consider a lot more interesting interpretations for programs: relations, games, probability kernels…

We will then cover the basic categorical ingredients that makes a category a good candidate for interpreting computation. That is, a category must handle tupling and curryfication. If the time allows for it, we will then quickly introduce how those categorical ideas lead to the development of linear logic.

This talk *will not* assume any prior knowledge in category theory nor in denotational semantic.

In a temporal graph, each edge is available at specific points in time. Such an availability is often represented by a ``temporal edge'' that can be traversed from its tail only at a specific departure time, for arriving in its head after a specific travel time. In such a graph, the connectivity from one node to another is naturally captured by the existence of a temporal path where temporal edges can be traversed one after the other. When imposing constraints on how much time it is possible to wait at a node in-between two temporal edges, it then becomes interesting to consider temporal walks where it is allowed to visit several times the same node, possibly at different times.

I will introduce the problem of computing minimum-cost temporal walks, using an algebraic framework for manipulating abstract costs enabling the optimization of a large variety of criteria. I will then present some algorithmic results recently obtained together with my supervisor (Laurent Viennot).

No prior knowledge of graph theory is going to be required.

In this talk I want to show how sometimes breakthrough results in complexity can almost directly provide us with interesting new ways of doing cryptography and how we then build more interesting cryptography from it. My aim is to be accessible to all IRIF students.

Concretely we start from the space-time lower bound for (parity-)learning by Raz (FOCS'16) – which we are using in a blackbox manner – and see how this almost directly gives us encryption. In a second step we will explore key agreement using the same building blocks as proposed by Guan and Zhandry (EuroCrypt'19).

Fuzzing is nowadays one of the most popular test generation technique. It is very good at quickly exploring the surface of a program, using quick automatic generation of test cases, sometimes guided through measures such as coverage.

However, if a program contains specific conditions (such as x = 0x42, where x is a user input), the probability of a fuzzer generating a solution is rather low.

During my thesis, we tried to improve AFL, an existing fuzzer, by combining it with a symbolic analysis. This analysis analyzes traces of generated test cases, in order to identify such conditions (e.g, it would identify that input[0] = 0x0042). From this information we deduce under-approximated path predicates, which we call “easily enumerable”. The solutions to those path predicates are then generated by our fuzzer, which we modified to this purpose, rather than an SMT solver.

This work resulted in a tool, called Confuzz, combining a modified AFL and the symbolic analysis written as a plug-in to the Binsec binary code analysis platform.