Les membres de l'IRIF et les visiteurs sont priés de se conformer aux directives COVID-19 du CNRS et de l'Université de Paris. image/svg+xml Bienvenue L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, 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), cinq 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 9.4.2021 We are happy to welcome Mirna DŽAMONJA, winner of an individual grant Marie CURIE part of the H2020 European program. Learn more about her and her work here 7.4.2021 Stephen Wolfram, pioneer in the development and application of computational thinking, will be speaking on Wednesday April 28, 18:00 CET at GReTA special event co-organized by IRIF. 26.3.2021 The ANR projet MAVeriQ will be having its second kickoff meeting on Friday March 26th. It will be starting with 4 short scientific talks: Eugene Asarin (IRIF), Loïc Helouet (IRISA), Nicolas Basset (VERIMAG), Benoît Barbot (LACL). Anybody who is interested is kindly invited to attend. 4.1.2021 Frédéric Magniez (IRIF CNRS member) holds the 2020–2021 chair on Computer Science at Collège de France (in partnership with Inria), where he will present a course on Quantum Algorithms starting April 7th with an Inaugural lecture on April 1st. Poster with full program. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Événements Algorithmique distribuée et graphes Mardi 13 avril 2021, 15 heures, ZOOM Adrian Pastine (Universidad Nacional de San Luis) Null Decomposition of Graphs Given a vector $\vec{x}$ in the null space of the adjacency matrix of a graph $G$, the support of $\vec{x}$ are the vertices which correspond to non-zero coordinates of $\vec{x}$. The support of $G$, $\Supp{G}$, is the union of the supports of all vectors in the null space of its adjacency matrix. The null decomposition of $G$, first introduced by Jaume and Molina in 2018, studies two subgraphs of $G$, $C_S(G)$, induced by the vertices in $\Supp{G}$ and their neighbours, and $C_N(G)$, induced by the remaining vertices. In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time. This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur. One world numeration seminar Mardi 13 avril 2021, 14 heures 30, online Andrew Mitchell (University of Birmingham) Measure theoretic entropy of random substitutions Algorithmes et complexité Mercredi 14 avril 2021, 10 heures, Collège de France Frédéric Magniez - Thomas Vidick (IRIF - California Institute of Technology) Cryptographie et communication quantiques Deuxième cours de Frédéric Magniez au Collège de France sur les Algorithmes quantiques (à 10h), suivi d'un exposé de Thomas Vidick sur « Certifier la génération de nombres aléatoires avec le quantique » (à 11h30). Informations supplémentaires : https://www.college-de-france.fr/site/frederic-magniez/course-2021-04-14-10h00.htm Automates Vendredi 16 avril 2021, 14 heures 30, https://bbb-front.math.univ-paris-diderot.fr/recherche/ama-bgy-hx5-3rl Arthur Jaquard A Complexity Approach to Tree Algebras: the Bounded Case The talk is based on joint work with Thomas Colcombet. We initiate a study of the expressive power of tree algebras, and more generally infinitely sorted algebras, based on their asymptotic complexity. Tree algebras in many of their forms, such as clones, hyperclones, operads, etc, as well as other kind of algebras, are infinitely sorted: the carrier is a multi sorted set indexed by a parameter that can be interpreted as the number of variables or hole types. Finite such algebras - meaning when all sorts are finite - can be classified depending on the asymptotic size of the carrier sets as function of the parameter, that we call the complexity of the algebra. This naturally defines the notions of algebras of bounded, linear, polynomial, exponential or doubly exponential complexity… Our main result precisely characterizes the tree algebras of bounded complexity based on the languages that they recognize as Boolean closures of simple languages. Along the way, we prove that such algebras that are syntactic are exactly those in which, as soon as there are sufficiently many variables, the elements are invariant under permutation of the variables. Sémantique Mardi 20 avril 2021, 10 heures, Exposé à distance sur Galène – salle 3052 virtuelle Soichiro Fujii (Research Institute in Mathematical Science (RIMS), Kyoto) Completeness and injectivity We show that for any quantale Q, a Q-category is skeletal and complete if and only if it is injective with respect to fully faithful Q-functors. This is a special case of known theorems due to Hofmann and Stubbe, but we provide a different proof, using the characterisation of the MacNeille completion of a Q-category as its injective envelope. One world numeration seminar Mardi 20 avril 2021, 14 heures 30, online Ayreena Bakhtawar (La Trobe University) Metrical theory for the set of points associated with the generalized Jarnik-Besicovitch set