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), three 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 18.9.2019 From September 30th to October 21st, Leonid Libkin (University of Edinburgh) will give a series of 7 courses related to his FSMP Chair on the topic of A modern theory of database query languages each Friday 10:30-12:00 at IRIF, room 3052. 17.9.2019 IRIF is having its back-to-work-day on October 1st. In the morning, there will be a welcome session for new PhD students, postdocs and TA, and in the afternoon a series of talks given by new faculty and CNRS members. 17.9.2019 Giuseppe Castagna (IRIF) and his coauthors Mariangiola Dezani, Elena Giachino, and Luca Padovani (Università di Torino) will receive on October the 8th at PPDP 2019 the Most Influential Paper 10-Year Award for their paper Foundation of Session Types presented at PPDP 2009. Session Types Session types can be thought of as “types for protocols”, insofar as they describe all the possible sequences of interactions between services, together with the type of the information exchanged in these interactions. Programs can be checked to see if the processes they implement conform to the protocols described by a session type. 11.9.2019 A. Balliu and D. Olivetti (former IRIF PhD students), J. Hirvonen and M. Rabie (former IRIF postdocs), with S. Brandt and J. Suomela broke an old lower bound open question on Maximal Matchings. Their paper will be presented at FOCS as Best Paper. 3.9.2019 IRIF has the great pleasure to welcome Leonid Libkin, professor at University of Edinburgh, who is visiting for three months. His stay is financed by an FSMP chair. Leonid is an expert in data management and applications of logic in computer science. Meet him in office 4048. 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. 6.9.2019 It is with great sadness that we learnt the passing of our collegue Patrick Dehornoy on September the 4th. IRIF had the chance to count this exceptional mathematician amongst his associate members. He will be terribly missed by all his collegues and it is a great loss for the whole scientific community. edit all the news (These news are displayed using a randomized-priority ranking.) Events Verification Monday September 23, 2019, 11AM, Salle 1007 Stefan Kiefer (University of Oxford) Selective monitoring We study selective monitors for labelled Markov chains. Monitors observe the outputs that are generated by a Markov chain during its run, with the goal of identifying runs as correct or faulty. A monitor is selective if it skips observations in order to reduce monitoring overhead. We are interested in monitors that minimize the expected number of observations. We establish an undecidability result for selectively monitoring general Markov chains. On the other hand, we show for non-hidden Markov chains (where any output identifies the state the Markov chain is in) that simple optimal monitors exist and can be computed efficiently, based on DFA language equivalence. These monitors do not depend on the precise transition probabilities in the Markov chain. We report on experiments where we compute these monitors for several open-source Java projects. Proofs, programs and systems Thursday September 26, 2019, 10:30AM, École normale supérieure de Lyon Pierre Clairambault, Andrea Condoluci, Hugo Férée Séminaire Chocola http://chocola.ens-lyon.fr/events/ Algorithms and discrete structures Thursday September 26, 2019, 11:45AM, Salle 1007 Sophie Laplante (IRIF) The sensitivity conjecture and a recent proof of it Informal presentation.