Bienvenue L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, qui héberge une équipe-projet Inria. Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques. L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), trois sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences. Tweets by IRIF_Paris Notion du jour Actualités 31.5.2023 Geoffroy Couteau et Pierre-Evariste Dagand ont écrit un texte à quatre mains dans le Blog Binaire du Journal Le Monde. Ils se demandent s'il est possible de contrôler l'accès aux sites pornographiques tout en conservant l'anonymat et les données de l'utilisateur pour protéger les enfants. C'est ici que le “zéro-proof knowledge” rentre en jeux… 15.5.2023 Congratulations to Jean Krivine (IRIF) and Vincent Danos (ENS and CNRS) who have received the Concur Test-of-Time Award (period 2002-2005) for their article “Reversible Communicating Systems”, published at CONCUR 2004. To read their article : 4.5.2023 Le pôle PPS organise ses journées 2023, les 25 et 26 mai prochains, et c'est ouvert à tous. 4.5.2023 Claire Mathieu a été citée dans un article du journal “La Croix” : “Intelligence artificielle : “pourquoi sa vision du monde est-elle si biaisée ?” 4.5.2023 Juliette Calvi, la nouvelle assistante de communication de l'IRIF est arrivée depuis la semaine dernière. N'hésitez pas à lui faire part de tous vos besoins en communication ou simplement à aller la rencontrer dans son bureau 4004. 11.5.2023 À l’occasion du départ à la retraite de François Métayer, le LHC rendra hommage au spécialiste des polygraphes, de l’homotopie et de la réécriture, animateur d’un groupe de travail mythique sur ces sujets. L’événement aura lieu les *8 et 9 juin 2023 et sera précédé par les journées LHC edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Combinatoire énumérative et analytique Jeudi 8 juin 2023, 14 heures, Olympe de Gouges 147 David Forge Généralisation de l'activité des matroides aux arbres Collaboration avec Rigo Florez. Nous généralisons la définition de l'activité à un cadre plus large contenant les matroides et des arbres enracinés. Ceci était motivé par un problème concernant l'arrangement de Linial. Séminaire des membres non-permanents Jeudi 8 juin 2023, 16 heures, Olympe de Gouges 147 and Zoom link Bernardo Jacobo-Inclan Timed automata and information of timed languages 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. Automates Vendredi 9 juin 2023, 14 heures, Salle 146 Olympe de Gouges Daniel Smertnig Deciding Sequential? and Unambiguous? for weighted automata over fields Previous work reduces the problem of deciding whether a weighted finite automaton (WFA) over a field is equivalent to a sequential, respectively, unambiguous, WFA to the computation of the linear hull. The linear hull is the topological closure of the reachability set in a certain linear version of the Zariski topology. We discuss an algorithm to compute the linear hull that works essentially entirely in the realm of linear algebra (i.e., without first resorting to the computation of the finer Zariski topology). Further, we show how this leads to double-exponential bounds on the size of the linear hull. This talk is on joint work with J. Bell. Algorithmes et complexité Lundi 12 juin 2023, 11 heures, Salle 147 (Olympe de Gouges) Themistoklis Melissourgos (University of Essex) Strong Inapproximability Results on Pizza-Sharing We study the computational complexity of finding a solution in straight-cut and square-cut pizza sharing, where the objective is to fairly divide 2-dimensional resources. We show that, for both the discrete and continuous versions of the problems, finding an approximate solution is PPA-complete even for very large constant additive approximation, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. We also study the corresponding decision variants of the problems and their complexity. All our hardness results for the continuous versions apply even when the input is very simple, namely, a union of unweighted squares or triangles. Joint work with Argyrios Deligkas and John Fearnley. Vérification Lundi 12 juin 2023, 11 heures, Olympe de Gouges 147 and Zoom link Themistoklis Melissourgos (University of Essex) Strong Inapproximability Results on Pizza-Sharing We study the computational complexity of finding a solution in straight-cut and square-cut pizza sharing, where the objective is to fairly divide 2-dimensional resources. We show that, for both the discrete and continuous versions of the problems, finding an approximate solution is PPA-complete even for very large constant additive approximation, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. We also study the corresponding decision variants of the problems and their complexity. All our hardness results for the continuous versions apply even when the input is very simple, namely, a union of unweighted squares or triangles. Joint work with Argyrios Deligkas and John Fearnley. Algorithmique distribuée et graphes Mardi 13 juin 2023, 15 heures, 147 Olympe de Gouges Anna Gujgiczer (Budapest University of Technology and Economics, Hungary) Circular chromatic number of generalised Mycielski graphs on odd cycles and other quadrangulations of the projective plane Generalised Mycielskians of odd cycles are relatively small graphs with high odd girth and chromatic number 4. In the literature there are many proofs using different techniques, like methods from algebraic topology, to show the second property. It is also proven by DeVos et al that these graphs have circular chromatic number 4. Using a result from about the same time of Simonyi and Tardos, namely that for a “topologically t-chromatic” graph $G$, where $t$ is even we have $\chi_c(G) = \chi(G) = t$, one can also get this strengthened statement. In this talk we present a new, relatively short direct proof for the circular chromatic number, using only a basic notion of algebraic topology, namely the winding number. Then we present another graph family with high odd girth and circular chromatic number 4. This construction is very similar to the generalized Mycielski, but on its first two layers it forms a M$\ddot{o}$bius ladder. We prove the statement about their circular chromatic number with similar techniques. Moreover we present a similar result for a family of signed graphs. This talk is based on a joint work with Reza Naserasr (Universit´e de Paris, IRIF, CNRS, F-75006, Paris, France), S Rohini (Indian Institute of Technology Madras, India) and S Taruni (Indian Institute of Technology Dharwad, India). Combinatoire énumérative et analytique Jeudi 15 juin 2023, 14 heures, Salle 146 - Olympe de Gouges Marc Noy (UPC (Espagne)) Chordal graphs with bounded tree-width https://arxiv.org/abs/2301.00194 Séminaire des membres non-permanents Jeudi 15 juin 2023, 16 heures, Olympe de Gouges 147 and Zoom link Maud Szusterman (IMJ-PRG) Non encore annoncé. Automates Vendredi 16 juin 2023, 14 heures, Salle 147 Olympe de Gouges Stefan Keifer On the state complexity of complementing unambiguous finite automata Given two finite automata A1, A2, recognising languages L1, L2, respectively, the state complexity of union (or intersection, or complement, etc.) is how many states (in terms of the number of states in A1, A2) may be needed in the worst case for an automaton that recognises L1 union L2 (or L1 intersect L2, or the complement of L1, etc.). The state complexity of complementing unambiguous finite automata has long been open, and as late as 2015 Colcombet asked whether unambiguous automata can be complemented with a polynomial blowup. I will report on progress on this question in recent years, both in terms of lower and upper bounds. For the currently best lower bound, techniques from communication complexity play an essential role. Graph Transformation Theory and Applications Vendredi 16 juin 2023, 15 heures, online Dániel Varró (Linköping University, Sweden and McGill University, Canada) Automated generation of domain-specific graph models Graphs are key abstractions in science and engineering. They may represent linked data in graph databases or social networks, complex designs of cyber-physical systems, or critical validation scenarios for autonomous systems. Synthetic graph generators are essential when the use of real graph models is restricted (to respect privacy regulations or intellectual properties of companies) or impractical (to find corner-cases for safety assurance). In this talk, I will provide an overview of major challenges and recent research results on automated graph generation which aims to derive domain-specific graph models which are simultaneously consistent (CO), realistic (RE), diverse (DI) and scalable (SC). In particular, I will present a graph solver that combines advanced graph algorithms with 3-valued logic satisfiability techniques. Zoom meeting registration link YouTube live stream