Pôle Algorithmes et structures discrètes

Pôle Automates, structures et vérification

Pôle Preuves, programmes et systèmes

Équipe-projet INRIA $\pi r^2$

Équipe thématique Algorithmes et complexité

Équipe thématique Algèbre et calcul

Équipe thématique Analyse et conception de systèmes

Équipe thématique Automates et applications

Équipe thématique Combinatoire

Équipe-projet INRIA GANG

Équipe thématique Modélisation et vérification

Équipe thématique Preuves et programmes

Équipe thématique Systèmes complexes, réseaux, calcul distribué

Équipe thématique Théorie et algorithmique des graphes

## Séminaire de l'IRIF

#### Jour, heure et lieu

#### Contact(s)

### Séances passées

#### Année 2019

Séminaire de l'IRIF

Vendredi 12 avril 2019, 10 heures 30, Amphi Turing (video available below in the full description of the event)

**Johan Håstad** (Royal Institute of Technology, Stockholm) **IRIF Distinguished Talks Series**: Switching lemmas in the 80ies and today

The first switching lemmas were proved in 1980ies and gave us lower bounds for the size of small-depth circuits. In particular they gave us optimal lower bounds for the size of circuits computing parity and proved that there are functions that have small circuits of depth d, but require (sub)-exponential size if the depth is restricted to d-1.

Some questions were left open in the 1980ies but have been resolved more recently. Two such questions are to establish sharp estimates for the best correlation with parity and to prove that the just mentioned hierarchy result can be established in an average case setting. Both these results used new variants of the switching lemma.

We survey these results and give an indication what modifications were needed to obtain the recent results.

If time permits we also discuss how yet other switching lemmas can be used to prove lower bounds for the length of Frege proofs using small-depth formulas.

Séminaire de l'IRIF

Lundi 18 mars 2019, 17 heures, Amphithéâtre Guillaume Budé - Marcelin Berthelot - Collège de France

**Robert Tarjan** (Princeton University and Intertrust Technologies) **IRIF Distinguished Talks Series**: Concurrent Connected Components

This talk is organized in collaboration with the Collège de France.

#### Année 2018

Séminaire de l'IRIF

Vendredi 16 novembre 2018, 10 heures 30, Amphithéâtre Pierre-Gilles de Gennes, Bât. Condorcet

**Maurice Herlihy** (Brown University) **IRIF Distinguished Talks Series**: Atomic Cross-Chain Swaps

Séminaire de l'IRIF

Vendredi 13 juillet 2018, 10 heures 30, Amphi Turing

**Christos Papadimitriou** (Columbia University) **IRIF Distinguished Talks Series**: A computer scientist thinks about the Brain

Séminaire de l'IRIF

Vendredi 13 avril 2018, 10 heures 30, Amphi Turing

**Monika Henzinger** (University of Vienna) **IRIF Distinguished Talks Series**: The state of the art in dynamic graph algorithms

#### Année 2017

Séminaire de l'IRIF

Vendredi 10 novembre 2017, 10 heures 30, Amphi Turing

**Yuri Matiyasevich** (Steklov Institute of Mathematics, St. Petersburg) **IRIF Distinguished Talks Series**: Hilbert's tenth problem and some other difficult problems ( click here for the slides)

Séminaire de l'IRIF

Mardi 11 avril 2017, 10 heures 30, Amphi Turing

**Leonid Libkin** (University of Edinburgh) **IRIF expository talks series**: Primordial database theory revisited: are relational algebra, calculus, and basic SQL really equivalent?

Our goal is to fill these surprising gaps in basic database theory. We provide a formal semantics of the core of SQL that captures the real language and accounts for many of its idiosyncrasies. To justify it as the correct semantics, we validate it experimentally on a large number of randomly generated queries. With this semantics, we formally prove the equivalence of core SQL and RA, as well as the extension of 3-valued FO with an operator that accounts for SQL's ability to switch back and forth between Boolean and 3-valued logics. Then, somewhat surprisingly, we show that this additional operator does not add expressiveness, and - even more surprisingly - that 3-valued logic does not add expressiveness even in the presence of nulls.

Based on joint work with with Paolo Guagliardo.

Séminaire de l'IRIF

Vendredi 3 mars 2017, 10 heures 30, Amphi Turing

**Joost-Pieter Katoen** (RWTH Aachen) **IRIF Distinguished Talks Series**: Principles of Probabilistic Programming (click here for the slides)

#### Année 2016

Séminaire de l'IRIF

Vendredi 28 octobre 2016, 10 heures 30, Salle 3052, Bâtiment Sophie Germain (SEE NOTE IN THE ABSTRACT)

**Yuri Gurevich** (Microsoft Research) **IRIF expository talks series **: Logic in Computer Science and Computer Engineering

IMPORTANT NOTE: For administrative reasons, those from outside of IRIF who wish to attend the seminar in “Salle 3052” should email by Wednesday 26/10 their name to Irène Guessarian at ig@liafa.univ-paris-diderot.fr .

Séminaire de l'IRIF

Vendredi 16 septembre 2016, 10 heures 30, Amphi Turing (Bâtiment Sophie Germain)

**Roberto di Cosmo** (IRIF) **IRIF expository talks series**: Preserving Software: challenges and opportunities for the reproductibility of Science (click here for the slides)

Preserving this software is of paramount importance to preserve our knowledge.

It is is a necessary prerequisite to allow the replication of experiments, which is the foundation of the scientific method, as well as to ensure our ability to modify and correct the software components that are constantly being incorporated into critical systems that need to stay in production for decades.

In this talk, we will review the challenges and opportunities we are facing, and discuss the role of Open Source as a key enabler.

The slides of the talk can be found here.

Séminaire de l'IRIF

Jeudi 28 janvier 2016, 10 heures 30, Amphi Turing

**Nachum Dershowitz** (Tel Aviv University) *Ada and Computation*