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 de l'IRIF Annuaire Contacts et accès Suivre @IRIF_Paris Notion du jour Actualités 13.12.2018 Constantin Enea (IRIF) will present at POPL 2019 a methodology for specifying software modules whose operations satisfy multiple consistency levels. This work has revealed previously unknown documentation errors and bugs in Java concurrent objects. 9.12.2018 The Alexander von Humboldt Foundation has honored Ahmed Bouajjani (IRIF) with the prestigious Carl Friedrich von Siemens Research Award, in recognition of his research contributions. 3.12.2018 Maybe you are an eager bitcoin miner? Maybe you are a fan of quantum computing too, and you wonder what will change in the mining competition when done by quantum computers? Find some answers in a paper coauthored by Miklos Santha (IRIF) to be presented at ITCS’19. 19.11.2018 IRIF has the great pleasure to welcome Mahsa Shirmohammadi, researcher scientist (CNRS) from LIS, who is visiting IRIF for six months and who is an expert in the analysis and verification of timed, counter and probabilistic systems. 7.10.2018 Jean-Eric Pin, CNRS senior researcher at IRIF, is awarded the Arto Salomaa prize for his outstanding contribution to the field of Automata Theory. 20.11.2018 Two papers coauthored by IRIF members will be presented at QIP’19, the main conference for theoretical quantum information research. Topics include efficient quantum algorithms for both algebraic and distributed problems. 20.11.2018 One paper coauthored by Laurent Feuilloley while he was PhD student at IRIF will be presented at SODA’19, the main conference in algorithm design. The paper provides lower bounds for the fundamental problem of text indexing with mismatches and differences using the Strong Exponential Time Hypothesis. 21.11.2018 Two papers coauthored by IRIF members will be presented at ITCS’19, a prestigious conference to promote research that carries a strong and innovative conceptual message in TCS. Topics include communication complexity and quantum dueling algorithms. toutes les actualités Événements Preuves, programmes et systèmes jeudi 13 décembre 2018, 10h30, ENS Lyon Journée Chocola () ENS Lyon http://chocola.ens-lyon.fr/events/meeting-2018-12-13/ Automates vendredi 14 décembre 2018, 14h30, Salle 3052 Colin Riba (École Normale Supérieure de Lyon) tba tba Catégories supérieures, polygraphes et homotopie vendredi 14 décembre 2018, 14h00, Salle 1007 Cameron Calk (ENS Lyon) L'homotopie dirigée et l'inversion temporelle Graphes mardi 18 décembre 2018, 15h30, Salle 3052 Bergougnoux Benjamin (IRIF) Rank Based Approach on Graphs with Structured Neighborhood In this talk, I will present a framework combining the rank-based approach with the notion of $d$-neighbor equivalence. The rank-based approach is a technique introduced by Bodlaender et al. in 2015 to obtained $2^{O(k)}\cdot n$ time algorithms, $k$ the treewidth of the input graph, for a wide range of connectivity problems. The $d$-neighbor equivalence is a tools introduced by Bui-Xuan et al. in 2013 to obtained efficient parameterized algorithms for many width measures (clique-width, rank-width, mim-width,…) and for many problems with a locally checkable constraint (Dominating Set, Independent Set,…). By combining these two notions, we obtain efficient algorithms for several connectivity problems such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, $\mathbb{Q}$-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the best time complexity for Vertex Cover and Dominating Set. Paper available on HAL : https://hal.archives-ouvertes.fr/hal-01799573v2/document Combinatoire énumérative et analytique jeudi 20 décembre 2018, 11h45, Salle 1007 Cyrille Chenavier (INRIA (Lille)) Quotients of the magmatic operad: lattice structures and convergent rewrite systems