### Institut de Recherche en Informatique Fondamentale

** Research Institute for Foundations of Computer Science **

The scientific objectives of the laboratory are at the core of computer science, focusing on: the mathematical foundations of computer science; computational models and proofs; models, algorithms and system design.

#### Upcoming seminars

Mardi 02 mai 2017 · 14h00 · Salle 1007

Algorithmique distribuée et graphes · Pierre Aboulker (ULB) · TBA

Mardi 02 mai 2017 · 11h00 · Salle 3052

Analyse et conception de systèmes · Joachim Breitner (University of Pennsylvania) · Who needs theorem provers when we have compilers?

But one powerful tool capable of doing (some of) these proofs is hidden in plain sight: GHC, the Haskell compiler! Its optimization machinery, in particular the simplifier, can prove many simple equations all by himself, simply by compiling both sides and noting that the result is the same. Furthermore, and crucially to make this approach applicable to more complicated equations, the compiler can be instructed to do almost arbitrary symbolic term rewritings by using Rewrite Rules.

In this rather hands-on talk I will show a small GHC plugin that I can use to prove the monad laws for a non-trivial functor. I am looking forward to a discussion of the merits, limits and capabilities of this approach.

Mardi 02 mai 2017 · 11h00 · Salle 1007

Algorithmes et complexité · Pierre Senellart (DI/ENS) · Tree decompositions for probabilistic data management

In this talk, we review recent work on the problem of efficiently querying probabilistic databases, i.e., compact representations of probability distributions over databases, by exploiting the structure of the data. In the deterministic setting, a celebrated result by Courcelle shows that any monadic second-order query can be evaluated in linear-time on instances of bounded treewidth. We show that this result generalizes to probabilistic instances through the use of provenance. In the probabilistic setting, we show that a bound on the treewidth is necessary for query evaluation to be tractable, in sharp contrast with the deterministic setting. This leads us to studying which real-world databases actually have low treewidth, and to propose practical algorithms for query evaluation in databases that can be partially decomposed in a low-treewidth part and a high-treewidth core.

Pierre Senellart is a Professor in the Computer Science Department at the École normale supérieure in Paris, France, and the head of the Valda team of Inria Paris. He is an alumnus of ENS and obtained his M.Sc. (2003) and Ph.D. (2007) in computer science from Université Paris-Sud, studying under the supervision of Serge Abiteboul. He was awarded an Habilitation à diriger les recherches in 2012 from Université Pierre et Marie Curie. Before joining ENS, he was an Associate Professor (2008–2013) then a Professor (2013–2016) at Télécom ParisTech. He also held secondary appointments as Lecturer at the University of Hong Kong in 2012–2013, and as Senior Research Fellow at the National University of Singapore from 2014 to 2016. His research interests focus around practical and theoretical aspects of Web data management, including Web crawling and archiving, Web information extraction, uncertainty management, Web mining, and intensional data management.

Mercredi 03 mai 2017 · 11h00 · Salle 3052

Séminaire des doctorants · Alexandre Nolin · Quantum, a look through nonlocality

Jeudi 04 mai 2017 · 11h00 · Salle 1007

Combinatoire énumérative et analytique · Svetlana Puzynina (IRIF) · Combinatoire additive basée sur les mots uniformémement récurrents

Vendredi 05 mai 2017 · 14h30 · Salle 1006

Automates · Sebastián Barbieri (ENS Lyon) · TBA

#### Events

Vendredi 9 décembre 2016 · 14h · Salle des thèses

Dimanche 15 - Vendredi 20 Janvier 2017 · Jussieu

44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017)