image/svg+xml Welcome IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, 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), five 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 14.9.2021 Eugene Asarin (IRIF), Thomas Ferrère, Dejan Ničković and Dogan Ulus receive the Oded Maler best paper award in Timed Systems at the conference Formats’2021 for their paper On the complexity of timed pattern matching. 7.9.2021 IRIF is very pleased to host for three months Sergio Rajsbaum, full time Researcher at the Instituto de Matemáticas of the Universidad Nacional Autónoma de México. This collaboration focuses on the use of algebraic topology to study the complexity of distributed algorithms. Algebraic topology tools have been mainly used for shared memory models. The purpose of the visit is to extend this research to distributed memory models. Professor Rajsbaum is partially funded by an invitational program from École Polytechnique. Meet him in office 4028a. 27.4.2020 Claire Mathieu (IRIF) has been interviewed by the online news site of CNRS about using graphs to devise a lockdown exit strategy. 3.9.2021 Yiting Jiang (IRIF) and Jaroslav Nešetřil will present a result that there are infinitely many minimal asymmetric k-uniform hypergraphs. 24.8.2021 Dans le cadre d’un mini-cours donné au 86ème séminaire Lotharingien de combinatoire, Guillaume Chapuy (IRIF) parlera d'un nouveau point de vue sur la correspondance entre cartes et tableaux de Young, qui joue un rôle fondamental en combinatoire algébrique. Ce nouveau point de vue, développé dans le cadre des polynômes de Jack et des surfaces non-orientables, est issu de ses travaux avec Maciek Dołęga (ancien postdoctorant à l'IRIF/LIAFA). 3.9.2021 Reza Naserasr (IRIF) is an invited speaker at the 29th Workshop on Cycles and Colourings. He will present a joint work with Lan Anh Pham (IRIF), Zhouningxin Wang PhD student (IRIF) and Xuding Zhu (University Jinchua): Density of C –4 -critical signed graphs. There is a classic one-to-one correspondence between (2k+1)-colorability of a graph and mapping of a specific subdivision of it to the (2k+1)-cycle. In this work they present an extension of this to 2k-coloring using homomorphisms of signed graphs. 26.8.2021 Ahmed Bouajjani (IRIF), Javier Esparza, and Oded Maler have received the Concur Test-of-Time Award (period 1996-1999) for their article Reachability Analysis of Pushdown Automata: Application to Model-checking published at CONCUR 1997. Read the interview. 3.9.2021 Guillaume Aubian, Pierre Charbit (IRIF) and Pierre Aboulker study the class of oriented graphs such that the out-neighbourhood of any vertex induces a transitive tournament and prove for it a decomposition theorem. As a consequence, they obtain that oriented graphs in this class have dichromatic number at most $2$ and satisfy Caccetta-Häggkvist conjecture. edit all the past news (These news are displayed using a randomized-priority ranking.) Events Limited number of events during the Summer break. Semantics Tuesday September 21, 2021, 11AM, Exposé à distance sur Galène – salle 3052 virtuelle Tom Hirschowitz (CNRS, Université Savoie Mont Blanc) A categorical framework for congruence of applicative bisimilarity [Part one] Applicative bisimilarity is a coinductive characterisation of observational equivalence in call-by-name lambda-calculus, introduced by Abramsky. Howe (1989) gave a direct proof that it is a congruence. We propose a categorical framework for specifying operational semantics, in which we prove that (an abstract analogue of) applicative bisimilarity is automatically a congruence. Example instances include standard applicative bisimilarity in call-by-name and call-by-value λ-calculus, as well as in a simple non-deterministic variant. One world numeration seminar Tuesday September 21, 2021, 2:30PM, Online Maria Siskaki (University of Illinois at Urbana-Champaign) The distribution of reduced quadratic irrationals arising from continued fraction expansions It is known that the reduced quadratic irrationals arising from regular continued fraction expansions are uniformly distributed when ordered by their length with respect to the Gauss measure. In this talk, I will describe a number theoretical approach developed by Kallies, Ozluk, Peter and Snyder, and then by Boca, that gives the error in the asymptotic behavior of this distribution. Moreover, I will present the respective result for the distribution of reduced quadratic irrationals that arise from even (joint work with F. Boca) and odd continued fractions. Enumerative and analytic combinatorics Thursday September 23, 2021, 2PM, Salle 1007 Séverin Charbonnier (IRIF) Weighted enumeration of ciliated maps and applications Some models of ribbon graphs can be interpreted as Feynman graphs of matrix models. In this manner, the graphs used by Kontsevich in his proof of Witten's conjecture – about the generating function of intersection numbers of psi-classes satisfying the KdV hierarchy – are Feynman graphs of a cubic hermitian matrix model with external field. Ciliated maps arise as generalisations of those graphs. I will first describe the ciliated maps and their weighted enumeration. Second, I will detail Tutte's equation and state how the generating functions are computed via topological recursion. Last, I will discuss applications of this result to intersection theory of Witten's class, to the enumeration of fully simple maps and to free probabilities. In collaboration with Raphaël Belliard, Gaëtan Borot, Bertrand Eynard and Elba Garcia-Failde. Graph Transformation Theory and Applications Friday September 24, 2021, 3PM, online Romain Pascual (MICS laboratory, CentraleSupélec, University Paris-Saclay, France) Combinatorial maps: transformations and application to geometric modeling In the first part of the talk, I will present generalized maps that represent quasi-manifolds through their subdivision into topological cells (vertices,edges, faces, volumes). We defined generalized maps as constrained labeled graphs. Arc labels encode topological relations of the subparts modeled object while node labels describe the geometric data used to represent the object. Modeling operations are designed regardless of the object's underlying topology. Therefore, we generalize DPO rules with a functorial approach to encode semi-global relabeling with a product operation. Rules and their extensions (called rule schemes) are considered valid if any application to a well-formed graph results in an equally well-formed graph. We provide set-theoric conditions on rules and rule schemes to ensure the preservation of the model consistency. In the second part of the talk, I will present how this approach allows the design of geometric modelers (software used to create and edit geometric objects) in Jerboa. The set-theoric conditions can be checked via graph traversal in Jerboa's rule editor to ensure that the code derived from the rule will never break the model. The generated code can be used as an add-on in other software or Jerboa's generic viewer. Zoom meeting registration link YouTube live stream