23.12.2019 IRIF is proud to announce that Claire Mathieu, senior research scientist at IRIF, has been elected at the Académie des sciences for the section of mechanical engineering and computer science. 13.12.2019 Raphaëlle Crubillé (former student at IRIF) was awarded the Gilles Kahn 2019 prize for her PhD thesis entitled « Behavioral Distances for Probabilistic Higher-order Programs » supervised by Thomas Ehrhard (IRIF) and Ugo Dal Lago. 11.12.2019 Two papers coauthored by IRIF members will be presented at POPL’20, the main conference on programming languages and programming systems. The papers' topics are reflecting Coq in Coq and how to differentiate higher-order programs. 10.12.2019 Michele Pagani (IRIF), Alois Brunel (Deepomatic) and Damiano Mazza (LIPN) will present at POPL'20 an effect-free extension of the backpropagation algorithm to higher-order functional programming, allowing for a logical understanding of its dynamics thanks to linear logic. 20.11.2019 Yann Regis-Gianas (IRIF) co-organizes at IRIF the workshop “Tezos Smart Contrat Languages and Formal Verification” on the 21 and 22 of November. Registration is free but mandatory. 7.11.2019 What are near-term quantum computers good for? Iordanis Kerenidis (IRIF) will give a talk on 11/29 in a meeting organized by the DIM Sirteq where Google will present its recent results about quantum supremacy. Registration is free but mandatory. 1.11.2019 IRIF hosts the annual meeting of the molecular bioinformatics research group of CNRS (GDR BIM) from 11-05 to 11-07. 29.10.2019 Walter FONTANA (MedSchool Harvard) holds the annual chair of Collège de France on the theme “Life and the Computer: The Challenge of a Science of Organization”. The lectures and seminars started since the 10-24. Jean Krivine (IRIF) will give a seminar the 11-22. 23.10.2019 Marie Kerjean (former IRIF PhD student) is one of the recipients of the L'Oréal-Unesco award for women in science. Marie is building a bridge between logic, programming, and physics using functional analysis to model proofs, and types to understand analysis. 16.10.2019 On December 16th, a half-day of talks aimed at a non-specialized audience will take place at IRIF in celebration of Algorithms, the research domain of Claire Mathieu, 2019 recipient of a CNRS Silver Medal. The event will conclude with a discussion of new research directions in Algorithms. Free Registration before November 30th. 8.10.2019 Talks of the IRIF Distinguished Talks Series for the coming academic year have been scheduled. Save the dates: January 24, March 20 and June 20. Speakers will be Martin Grohe (RWTH Aachen University), Joseph Mitchell (State University of New York at Stony Brook), Simon Peyton Jones (Microsoft Research at Cambridge, England). 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 Researchers of IRIF are participating in the “Fête de la Science”! Meet them at the University of Paris October 10-11 to better understand the first principles of computing! 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. 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. 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. 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. 25.9.2019 IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Sam Van Gool, an expert in algebraic and topological methods for automata, logic, and model theory. 24.9.2019 IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Valia Mitsou, an expert in algorithms and complexity, particularly in structural parameterizations and fine grained complexity. 24.9.2019 IRIF has the great pleasure to welcome a new professor (Université de Paris): Sylvain Schmitz, an expert in logic and verification, and especially in problems of astronomical computational complexity. 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. 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 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. 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. 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. 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 its associate members. He will be terribly missed by all his colleagues and it is a great loss for the whole scientific community. 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. 26.8.2019 The PPS days will happen in the Turing amphiteater the 2nd and 3rd of September. 14.7.2019 A workshop on Graph Compression and Compact Representations will take place at IRIF on September 9-10. Submit your talk proposal before the 25th of August. 14.7.2019 A scientific meeting in honor of Pierre-Louis Curien will take place at IRIF, in the amphiteater 4C, Halle aux Farines building on the 6th of September. Registration is free but mandatory. 28.6.2019 IRIF is celebrating the end of the academic year on the 4th of July at Amphi Pierre-Gilles de Gênes, building Condorcet with a talk at 4.00 by Emmanuelle Frenoux about computer science and the environment, and another at 5.00 by Anne Siegel about gender balance. 21.6.2019 A summer school CIMPA entitled “Algorithmic and statistical approaches to machine learning” co-organized by Vlady Ravelomanana will take place at the University of Antananarivo from the 16th to the 25th of July 2019. 11.6.2019 Kamil Khadiev from Kazan University, an expert in complexity and quantum computing, is visiting IRIF from June 10th to July 9th. 30.5.2019 Four papers coauthored by IRIF members will be presented at the prestigious conference CAV'19 in New York this summer. Topics include verifying weakly-consistent distributed databases, testing cache coherence protocols, and testing concurrent objects. 25.5.2019 Mikaël Rabie (Postdoc at IRIF) will present at ICALP'19 a new problem, about distributed reconfiguration of maximal independent sets, providing an optimal algorithm to produce a reconfiguration schedule in the LOCAL model. This work, receiving Best Paper award in Track C, is a joint work with Keren Censor-Hillel from the Technion (Haifa, Israël). 10.5.2019 IRIF is proud to announce that Constantin Enea, associate professor of Université de Paris and researcher at IRIF, was appointed junior member of IUF. This appointment will allow him to develop a research project concerning rigorous engineering of distributed databases. 9.5.2019 Claire Mathieu, Amaury Pouly and Yann Régis-Gianas from IRIF gave talks at the conference of French preparatory schools to science and engineering curriculum in May 6-10, contributing to the ongoing important changes in Computer Science education in French high-schools and higher-education systems. 7.5.2019 Claire Mathieu from IRIF explained what algorithms are and what is their history to a national French radio broadcast show about Philosophy. 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. 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. 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. 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. 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. 19.4.2019 Iordanis Kerenidis (IRIF) explains what we can expect from Quantum Computing in this interview of the CNRS journal. 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. 8.4.2019 Two IRIF members (Ahmed Bouajjani and Pierre Fraigniaud) will give a talk at the Workshop on Taking Stock of Distributed Computing at College de France, Friday April 12. 8.4.2019 We are very pleased to host as part of our IRIF Distinguished Talks Series Johan Håstad (Royal Institute of Technology, Stockholm) on April 12, 10:30 for a talk entitled “Switching lemmas in the 80ies and today”. 5.4.2019 Penny Haxell from University of Waterloo (Canada), a world wide expert in extremal combinatorics and graph theory, is visiting IRIF March 28th to May 2nd. Extremal combinatorics Extremal combinatorics studies how large or how small a collection of finite objects can be, if it has to satisfy certain restrictions. For instance, in an n-element set, what is the largest number of subsets of which none contains any other? The question is answered by Sperner's theorem, which gave rise to much of extremal set theory. Another kind of example: How many people can we invite to a party where among each three people there are two who know each other and two who don't know each other? Ramsey theory shows that at most five persons can attend such a party. 26.3.2019 The ANR project DISTANCIA about graph metrics is organizing a workshop at IRIF on the 27, 28 and 29 of March in room 366A of Bâtiment Condorcet. 17.3.2019 The Paris Region PhD2 program will grant 30 PhD projects on Digital Sciences and with an industrial partner. IRIF is an eligible hosting lab. Call for application is open until May, 15th 2019. 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. 14.3.2019 Université Paris Diderot has opened four permanent positions in Computer Science (1 professor and 3 assistant professors). Recruited researchers will join IRIF. 14.3.2019 FSMP offers 21 PhD student positions in Maths and TCS under H2020 COFUND project MathInParis. As a member of the FSMP network, IRIF is an eligible hosting lab. Call for application is open until April, 1st 2019. Applicants must be international students, but master students already in France for less than a year are eligible. 5.3.2019 The Collège de France and IRIF are delighted to host as part of our IRIF Distinguished Talks Series Robert Tarjan (Princeton) on March 18, 17:00 for a talk entitled “Concurrent Connected Components” 19.2.2019 Amaury Pouly (IRIF) with François Fages, Guillaume Le Guludec and Olivier Bournez were awarded the prize "La Recherche": they have shown that chemical reactions, as the ones taking place in cells, can simulate Turing machines. Chemical reactions are universal computers. 15.2.2019 Fabian Reiter (former student at IRIF) wrote a short popularisation article in the Blog Binaire of the newspaper Le Monde. This article explains (in French) some aspects of his PhD thesis, recently awarded the Honorable Mention of the Gilles Kahn prize. 15.2.2019 In collaboration with Yoav Rodeh (Weizmann Institute of Science), Pierre Fraigniaud and Amos Korman from IRIF published a paper in the Journal of the ACM entitled “Parallel Bayesian Search with no Coordination”. 4.2.2019 IRIF has the great pleasure to welcome Sandra Alves, assistant professor at University of Porto and expert in type-theory, rewriting, and fundamental calculi, who is visiting the IRIF until the 8th of February. 1.2.2019 Enrica Duchi and Guillaume Chapuy (IRIF) organise February the 15th in Amphi Turing, a map day (Journée cartes) dedicated to combinatorial and probabilistic aspects of maps. 1.2.2019 Carole Delporte (IRIF) will give a seminar at Collège de France as part of the annual Chair of Rachid Guerraoui (EPFL) on Distributed Algorithms, March 1. 1.2.2019 IRIF has the great pleasure to welcome Uri Zwick, professor at the Blavantik School of Computer Sience (University of Tel-Aviv), who is visiting for four months. His stay is financed by an FSMP chair. Uri is an expert in algorithms, data structures and games. Meet him in office 4048. 30.1.2019 The next meeting of the ANR project FREDDA (FoRmal mEthods for the Design of Distributed Algorithms) will happen at IRIF, Monday 4th and Tuesday 5th February 2019, room 3052. 23.1.2019 FILOFOCS (French-Israeli Laboratory on Foundations of Computer Science), the first International Joint Unit in Israel, was just created by CNRS, Univ. Paris Diderot, Tel-Aviv Univ., Hebrew Univ. of Jerusalem and Weizmann Institute. IRIF hosts its “mirror site” in France, and Adi Rosén from IRIF is deputy director. 23.1.2019 A CIMPA school on Graphs, Algorithms and Randomness is co-organized by Reza Naserasr from IRIF at Tabriz University, 15-22 June 2019. Three colleagues from IRIF, Pierre Fraigniaud, Michel Habib and Frédéric Magniez, are among the five lecturers from France. 17.1.2019 Pierre Fraigniaud from IRIF organizes the Workshop Complexity and Algorithms (CoA), in the framework of GdR IM, Roscoff, France, April 1-5, 2019. The objective of this workshop is to gather the French community on design and analysis of algorithms, of all forms. Deadlines: submission by 01/02/2019, registration by 02/03/2019. 17.1.2019 Guillaume Chapuy and Enrica Duchi from IRIF coorganize with Christina Goldschmidt (Oxford) the Journées Aléa 2019, a CNRS thematic school about discrete random structures, from 03-18 to 03-22 at CIRM. Register by January 23. 16.1.2019 Giuseppe Castagna, Victor Lanvin, Tommaso Petrucciani from IRIF present this week at POPL19 a paper coauthored with Jeremy Siek (Indiana university) about a new formal framework for gradual typing allowing a smoother and more declarative integration of gradual typing in existing programming languages. 10.1.2019 The day of the ASV pole will take place Monday January 21. 9.1.2019 IRIF has the great pleasure to welcome Jeremy Siek, professor at Indiana University Bloomingtom, who is visiting IRIF for five months. Jeremy is the creator of gradual typing and a world-renowed expert in typed programming languages. Meet him in office 4034a. 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. 8.1.2019 IRIF has the great pleasure to welcome a new researcher (CNRS), Amaury Pouly, an expert in continuous models of computations, and the analysis and verification of continuous/hybrid dynamical systems. 1.1.2019 Christine Tasson (IRIF) will give a seminar at Collège de France as part of the lectures of Xavier Leroy (Collège de France) on Software Science, January 23.