Welcome IRIF is a research laboratory of CNRS and Université Paris Cité, also hosting one Inria project-team. The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences. IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), six are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences. Tweets by IRIF_Paris Notion of the day News 22.6.2022 The 2022 edition of Highlights will happen from June 28th to July 1st, 2022, in Paris, France. The conference will be hosted by Université Paris Cité, and happen on the site of Grands Moulins. To register, please fill in the registration form. If you wish to watch Highlights remotely, please fill in the online registration form. Online attendance is free. 7.6.2022 IRIF is proud to announce that Olivier Carton, professor of Université Paris Cité and researcher at IRIF, was appointed senior member of IUF. 7.6.2022 Four papers coauthored by IRIF members will be presented at the conference PODC'22, the main conference on distributed computing, this summer. 7.6.2022 Two papers coauthored by IRIF members will be presented at the conference ISSAC'22, the main conference on symbolic and algebraic computation , this summer. 7.6.2022 Four papers coauthored by IRIF members will be presented at the conference TYPES'22, the main conference on type theory, this summer. 7.6.2022 IRIF is co-organizing a Workshop on Differentiable Programming, June 29-30, Université Paris Cité. 7.6.2022 IRIF is co-organizing a Workshop Labyrinth of Combinatorics in memory of Pierre Rosenstiehl, June 15-17, Université Paris Cité 5.5.2022 Gaëtan Douéneau-Tabot (IRIF, DGA) will present at ICALP 2022 his paper Hiding pebbles when the output alphabet is unary. Pebble transducers are simple programs which compute functions over finite words. This paper studies subclass membership problems for the functions computed by pebble transducers whose outputs are unary. Its results can be understood as program optimization techniques. edit all the past news (These news are displayed using a randomized-priority ranking.) Agenda Enumerative and analytic combinatorics Thursday June 30, 2022, 2PM, Salle 1007 Lucia Rossi (Graz) Limit words for $N$-continued fractions Given $N\geq 1$ and $x \in [0, 1]\backslash \mathbb{Q}$, an $N$-continued fraction expansion of $x$ is defined analogously as the classical continued fraction, but with the numerators being all equal to $N$. We introduce two infinite words $\omega(x, N )$ and $\hat\omega(x, N )$ on a two letter alphabet, which are related to the $N$-continued fraction expansion of $x$ and are obtained as a limit word of a sequence of substitutions. We call them $N$-continued fraction words. When $N=1$, we are in the classical case and find a Sturmian word. We show that these words are $C$-balanced for some explicit values of $C$, and we compute the factor complexity function of both families of words. We relate this to the more general setting of limit words of non unimodular $S$-adic sequences. This is joint work with Jörg Thuswaldner and Niels Langeveld. Analysis and conception of systems Friday July 1, 2022, 10:30AM, Salle 3052 Jean-Baptiste Tristan (Boston College) Probabilistic Programming and Molecular Optimization (Zoom link) The energy of a system of atoms is approximately a function of the position of the nuclei. This function is called the potential energy surface (PES). Knowledge of the PES is fundamental in ab-initio sciences but unfortunately, it cannot be computed in closed form. As a result, an important problem is that of exploring the PES to discover important features, such as local minima. In this talk, I will introduce an experimental probabilistic programming language designed to facilitate the exploration of PES. In this language, the semantics of a program is a probability distribution over PES. The objective of the compiler is to generate an optimizer that combines solvers from machine learning and quantum chemistry to discover local minima of the PES. While much of this language and compiler is routine, we will see that the principle of conservation of energy brings about genuinely interesting compilation problems. One world numeration seminar Tuesday July 5, 2022, 2:30PM, Online Charlene Kalle (Universiteit Leiden) Random Lüroth expansions Since the introduction of Lüroth expansions by Lüroth in his paper from 1883 many results have appeared on their approximation properties. In 1990 Kalpazidou, Knopfmacher and Knopfmacher introduced alternating Lüroth expansions and studied their properties. A comparison between the two and other comparable number systems was then given by Barrionuevo, Burton, Dajani and Kraaikamp in 1996. In this talk we introduce a family of random dynamical systems that produce many Lüroth type expansions at once. Topics that we consider are periodic expansions, universal expansions, speed of convergence and approximation coefficients. This talk is based on joint work with Marta Maggioni. Analysis and conception of systems Friday July 8, 2022, 10:30AM, Salle 1007 Ada Vienot (IRIF) A reactive operational semantics for a lambda-calculus with time warps Many computer systems are reactive: they execute in continuous interaction with their environment. From the perspective of functional programming, reactive systems can be modeled and programmed as stream functions. Several lines of research have exploited this point of view. Works based on Nakano’s guarded recursion use type-theoretical modalities to guarantee productivity. Works based on synchronous programming use more specialized methods but guarantee incremental processing of stream fragments. In this paper, we contribute to a recent synthesis between the two approaches by describing how a language with a family of type-theoretical modalities can be given an incremental semantics in the synchronous style. We prove that this semantics coincides with a more usual big-step semantics. Algorithms and complexity Tuesday July 12, 2022, 10AM, Salle 3052 Seeun William Umboh (The University of Sydney) Online Weighted Cardinality Joint Replenishment Problem with Delay We study a generalization of the classic Online Joint Replenishment Problem (JRP) with Delays that we call the Online Weighted Cardinality JRP with Delays. The JRP is an extensively studied inventory management problem wherein requests for different item types arrive at various points in time. A request is served by ordering its corresponding item type. The cost of serving a set of requests depends on the item types ordered. Furthermore, each request incurs a delay penalty while it is left unserved. The objective is to minimise the total service and delay costs. In the Weighted Cardinality JRP, each item type has a positive weight and the cost of ordering is a non-decreasing, concave function of the total weight of the item types ordered. This problem was first considered in the offline setting by Cheung et al.~(2015) but nothing is known in the online setting. Our main result is a deterministic, constant competitive algorithm for this problem. Algorithms and complexity Tuesday July 12, 2022, 11AM, Salle 3052 Kheeran Naidu (University of Bristol) Space Optimal Vertex Cover in Dynamic Streams (with an overview of graph streaming) With the world as connected as ever and data being created at an unprecedented rate, there has been an increasing need for algorithms that efficiently process massive graphs. Graph streaming is one such memory efficient setting where the edges of a graph are presented as a sequence of edges and an algorithm's goal is to store a sublinear number of edges needed to solve a graph problem exactly or approximately. In particular, this talk discusses the insertion-only, dynamic (or insertion-deletion) and sliding window graph streaming models of computation, highlighting the well-studied maximum matching and sister minimum vertex cover problems, and focusing on a recent space optimal (up to constant factors) algorithm for minimum vertex cover in the dynamic graph streaming model. One world numeration seminar Tuesday July 12, 2022, 2:30PM, Online Ruofan Li (South China University of Technology) Rational numbers in ×b-invariant sets Let $b \ge 2$ be an integer and $S$ be a finite non-empty set of primes not containing divisors of $b$. For any $\times b$-invariant, non-dense subset $A$ of $[0,1)$, we prove the finiteness of rational numbers in $A$ whose denominators can only be divided by primes in $S$. A quantitative result on the largest prime divisors of the denominators of rational numbers in $A$ is also obtained. This is joint work with Bing Li and Yufeng Wu.