Bienvenue à l'IRIF L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'université Paris-Diderot, qui héberge deux équipes-projets 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) et deux sont membres de l'Academia Europæa. Présentation Annuaire Contacts Suivre @IRIF_Paris Notion du jour Actualités 23.4.2019 The Spring session of Graph Theory in Paris will be held on Friday April 26 at Amphi Turing. Speakers of the event: Penny Haxell from U. Waterloo and Patrice Ossona de Mendez from CNRS. 23.4.2019 Sergio Rajsbaum from Universidad Nacional Autonoma de Mexico, a world-renowned expert in the theory of distributed computing, is visiting IRIF from March 31st to May 2nd. Distributed systems Distributed systems are groups of networked computers, interacting with each other in order to achieve the same goal. In parallel computing, all processors have access to a shared memory to exchange information between processors. In distributed computing, information is exchanged by passing messages between the processors. Cluster of computers and peer-to-peer systems are examples of such architectures. Models of distributed systems are also used in other science, such as in biology, in order to analyze collective behaviors of autonomous entities interacting with each other by message passing. 26.4.2019 Seven papers coauthored by IRIF members will be presented at the prestigious conference ICALP'19 in Patras this summer. Topics include automata, games, graphs, quantum computing, randomized complexity, and semigroups. 15.3.2019 From March 20th to May 22nd, Uri Zwick (Univ. of Tel Aviv) will give a series of 7 courses related to his FSMP Chaire of Excellence on the topic of Games on Graphs and Linear Programming Abstractions each Wednesday 2:15pm - 4:15pm at IRIF, room 3052. Linear programming Linear programming is a technique for the optimization of a linear function, subject to linear equality and linear inequality constraints. A linear programming algorithm finds a point in the polyhedron of feasible solutions satisfying those constrains, where this function has the smallest (or largest) value. Linear programming is widely used in industries, including transportation, energy, telecommunications, and manufacturing, for diverse types of tasks such as planning, routing, scheduling, assignment, and design. 19.4.2019 Three papers coauthored by IRIF members will be presented at the prestigious conference LICS'19 in Vancouver this summer. Topics include sequent calculus, differential logic and probabilistic computation. 16.4.2019 Ali Charara, director of INS2I at CNRS, visits IRIF on the morning of April 24th. The research conducted at IRIF will be presented as well as 6 specific scientific talks. The visit will be followed by a light buffet lunch. 19.4.2019 Iordanis Kerenidis (IRIF) explains what we can expect from Quantum Computing in this interview of the CNRS journal. 19.4.2019 Université Paris Diderot has opened several teaching assistant positions (ATER) in Computer Science on the research topics of IRIF. Deadline to apply : May 6, 2019. edit toutes les actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Événements Nombre limité d'évènements durant les vacances de printemps Preuves, programmes et systèmes Jeudi 2 mai 2019, 10 heures 30, Salle 3052 Hugo Férée (University of Kent) Une théorie de la complexité d'ordre supérieur via la sémantique des jeux Alors que de nombreux modèles de calcul nous permettent de manipuler des données issues de domaines non dénombrables (fonctions d'ordre supérieur, nombres réels, objets définis par co-induction), les différentes notions de complexité ne permettent de s'intéresser qu'à des fonctions d'ordre 1 (i.e. traitant des données finies) voire des fonctions d'ordre 2 (i.e. traitant des fonctions d'ordre 1). Dû à la difficulté de définir une notion pertinente de taille pour des données d'ordre quelconque, les notions de complexité pour des fonctions d'ordre 3 ou plus sont à la fois incomplètes et imparfaites. En nous appuyant sur la sémantique des jeux nous proposons ici une définition de taille et de complexité pour les fonctions d'ordre supérieur de PCF, et plus généralement pour tout processus calculatoire assimilable à une certaine classe de jeux séquentiels. Automates Vendredi 3 mai 2019, 14 heures 30, Salle 3052 Sam Van Gool (Utrecht University) Separation and covering for varieties determined by groups The separation problem for a variety of regular languages V asks to decide whether two disjoint regular languages can be separated by a language in V. The covering problem is a generalization of the separation problem to an arbitrary finite list of regular languages. The covering problem for the variety of star-free languages was shown to be decidable by Henckell. In fact, he gave an algorithm for an equivalent problem, namely, computing the pointlike subsets of a finite semigroup with respect to the variety of aperiodic semigroups, i.e., semigroups all of whose subgroups are trivial. In this talk, I will present the following wide generalization of Henckell's result. Let H be any decidable variety of groups. I will describe an algorithm for computing pointlike sets for the variety of semigroups all of whose subgroups are in H. The correctness proof for the algorithm uses asynchronous transducers, Schützenberger groups, and self-similarity. An application of our result is the decidability of the covering and separation problems for the variety of languages definable in first order logic with modular counting quantifiers. This talk is based on our paper S. v. Gool & B. Steinberg, Adv. in Math. 348, 18-50 (2019).