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 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), 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. Présentation Annuaire Contacts Suivre @IRIF_Paris Chaine IRIF Notion du jour Actualités 15.1.2021 V. Berthé (IRIF) & J. Barral spearhead the creation of 𝘎𝘋𝘙 Multifractal analysis and self-similarity as a renewal of `GDR Multifractal analysis' with a move towards symbolic dynamic systems. 5.1.2021 Geoffroy Couteau (IRIF), Pooya Farshim (University of York), and Mohammad Mahmoody (University of Virginia) will present at ITCS 2021 a new framework for proving black-box separations in cryptography in a composable way. 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. 4.1.2021 P. Fraigniaud (IRIF), F. Le Gall (Nagoya University), H. Nishimura (Nagoya University), and A. Paz (Universität Wien) will present at ITCS 2021 a quantum approach of distributed certification, for checking the consistency of large data sets replicated at several nodes of a network. 21.10.2020 A paper by Troy Lee, Miklós Santha (IRIF CNRS member), and Shengyu Zhang on quantum algorithms for graph problems with cut queries will be presented at SODA2021. 6.11.2020 A paper by C. Mathieu (IRIF CNRS member) with R. Rajaraman, N. Young, and A. Yousefi will be presented at SODA2021 on dynamization policies in the competitive analysis framework for log-structured merge trees underpinning industrial NoSQL databases. 22.12.2020 Ugo Dal Lago (Univ. Bologna), Claudia Faggian (IRIF), and Simona Ronchi Della Rocca (Univ. Torino) will present at POPL 2021 a type system to characterize probabilistic termination and (exact) expected runtime of programs in the context of higher-order probabilistic computation. 21.12.2020 Damiano Mazza (LIPN) and Michele Pagani (IRIF) will present at POPL 2021 the first proof of the almost everywhere correctness of automatic differentiation in the context of a higher-order, Turing-complete programming language. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Événements Vérification Lundi 18 janvier 2021, 11 heures, BBB link Léo Henry (IRISA, Université de Rennes I) Active learning of timed automata with unobservable resets Active learning of timed languages is concerned with the inference of timed automata from observed timed words. The agent can query for the membership of words in the target language, or propose a candidate model and verify its equivalence to the target. The major difficulty of this framework is the inference of clock resets, central to the dynamics of timed automata, but not directly observable. Interesting first steps have already been made by restricting to the subclass of event-recording automata, where clock resets are tied to observations. In order to advance towards learning of general timed automata, we generalize this method to a new class, called reset-free event-recording automata, where some transitions may reset no clocks. This offers the same challenges as generic timed automata while keeping the simpler framework of event-recording automata for the sake of readability. Central to our contribution is the notion of invalidity, and the algorithm and data structures to deal with it, allowing on-the-fly detection and pruning of reset hypotheses that contradict observations, a key to any efficient active-learning procedure for generic timed automata. Algorithmes et complexité Mardi 19 janvier 2021, 11 heures, Online Christian Konrad (University of Bristol) Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams In this talk, I will discuss simple optimal lower bounds on the one-way two-party communication complexity of approximate Maximum Matching and Minimum Vertex Cover with deletions. In this model, Alice holds a set of edges and sends a single message to Bob. Bob holds a set of edge deletions, which form a subset of Alice's edges, and needs to report a large matching or a small vertex cover in the graph spanned by the edges that are not deleted. Our results imply optimal space lower bounds for insertion-deletion streaming algorithms for Maximum Matching and Minimum Vertex Cover. An optimal space lower bound for Maximum Matching was previously given by Assadi et al. [SODA 2016], however, this lower bound only holds for the subclass of streaming algorithms that are able to process very long (at least triple exponential in n) input streams. This work appeared at CCC'20. Joint work with Jacques Dark. One world numeration seminar Mardi 19 janvier 2021, 14 heures 30, Online Tom Kempton (University of Manchester) Bernoulli Convolutions and Measures on the Spectra of Algebraic Integers Combinatoire énumérative et analytique Jeudi 21 janvier 2021, 14 heures, Virtuelle Oswin Aichholzer (TU Graz) Crossing Numbers of complete graphs for Geometric and Topological Drawings In the area of crossing numbers we ask for minimizing the number of edge intersections in a drawing of a graph. There is a rich variety of crossing number problems: Which graphs do we consider, what exactly is a drawing of a graph and on which surface is it drawn, and how are intersections counted? In this talk we will concentrate on the crossing number of complete graphs drawn in the plane, including their rich history around Hill's conjecture. We will have a look at geometric drawings (vertices are points in the plane and edges of the graph are straight line segments), and simple drawings (edges are simple Jordan arcs with at most one pairwise intersection), which are also called simple topological graphs. Our results ar based on a representation of the complete graph with order types (for geometric graphs) and rotation systems (for simple drawings). We will presen recent developements, as well as (old and new) open questions.