Welcome to IRIF IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and université Paris-Diderot, also hosting two INRIA project-teams. The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences. IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), five are members of the Institut Universitaire de France IUF), and two are members of the Academia Europæa. More People Contact Follow @IRIF_Paris Notion of the day News 8.10.2019 Researchers of IRIF are participating in the “Fête de la Science”! Meet them at the University of Paris this week to better understand the first principles of computing! 10.9.2019 IRIF is seeking excellent candidates for about 10 postdoctoral positions in all areas of the Foundations of Computer Science. Deadline for applications: Nov. 3, 2019. 8.10.2019 From ancient history to quantum, learn about cryptography at “Fête de la science” in an entertaining talk by Sylvain Perifel (IRIF) Friday October 11th, 11am at Amphitheater 4C, Halle aux farines. 8.10.2019 The SODA 2020 conference will include a paper by Vincent Cohen-Addad (LIP6), Frederick Mallmann-Trenn (King's College) and Claire Mathieu (IRIF) about computing with noisy data. The problem: select valuable objects in a setting where each assessment has a probability of error, using redundant assessments. 23.9.2019 Giuseppe Castagna (IRIF) and Jeremy Siek (Indiana) organize WGT 2020, the first ACM SIGPLAN Workshop on Gradual Typing, colocated with POPL. Submission deadline: Monday, October the 21st. gradual typing Gradual typing is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to gradually add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution. 1.10.2019 IRIF has the great pleasure to welcome a new research scientist (CNRS): Geoffroy Couteau, an expert in cryptography, with a focus on secure computation protocols and zero-knowledge proofs. 2.10.2019 IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Hugo Férée, an expert in various aspects of complexity theory, with interests in programming languages and formal proofs. 25.9.2019 Three papers coauthored by IRIF members will be presented at SODA’20, the main conference in algorithm design. Topics include the study of noisy models, aggregate rankings, and graph diameters. edit all the past news (These news are displayed using a randomized-priority ranking.) Events Verification Monday October 14, 2019, 11AM, Salle 1007 Laurent Doyen (LSV, ENS Paris-Saclay) Expected Finite Horizon A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon T, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping time distribution with expected stopping time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans. Algorithms and complexity Tuesday October 15, 2019, 11AM, Salle 1007 Zvi Lotker (Ben Gurion University) Variation on preferential-attachment In this talk, I will describe how preferential attachment arises from the first principle using game theory. Next, I will extend the model of preferential attachment into a general model, which allows for the incorporation of Homophily ties in the network. This talk is based on joint works with Prof. Chen Avin, Avi Cohen, Yinon Nahum, Prof. Pierre Fraigniaud, and Prof. David Peleg. Enumerative and analytic combinatorics Thursday October 17, 2019, 2PM, Salle 1007 Mark Skandera (Lehigh university) To be announced. Proofs, programs and systems Thursday October 17, 2019, 10:30AM, École normale supérieure de Lyon Eric Finster Séminaire Chocola http://chocola.ens-lyon.fr/events/ Higher categories, polygraphs and homotopy Friday October 18, 2019, 2PM, Salle 1007 Léonard Guetta (IRIF) Colimites homotopiques et tranches