## IRIF Distinguished Talks Series

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

#### Contact(s)

**Description of the event**

The IRIF Distinguished Talks Series is back on track with a new season of talks and other seasons to follow.

What is the IRIF Distinguished Talks Series?

The IRIF Distinguished Talks Series is a series of invited talks given 3 to 4 times a year by prominent scientists in the field of Theoretical Computer Science and Mathematics.

The speakers will deliver inspiring talks describing a recent scientific breakthrough, or a currently active research field or their vision for the development of a new research direction, all within the area of Theoretical Computer Science and Mathematics.

Who is the targeted audience?

Talks of the IRIF Distinguished Talks Series are mainly intended for members of the Theoretical Computer Science and Mathematics communities of the Île-de-France area but any other interested person is welcome to attend as well. The talks are targeted to an informed, but not necessarily specialized, audience.

Where does it take place?

The IRIF Distinguished Talks Series take place at Université Paris Cité, in the Sophie Germain building on the Grands Moulins campus in Paris. Each talk is not available live but will be recorded and later made available online, on the event website: https://www.irif.fr/en/seminaires/irif/index.

### Next talk

IRIF Distinguished Talks Series

Tuesday December 3, 2024, 11AM, Amphi Turing

**Dexter Kozen** (Cornell University) *To be announced.*

### Previous talks

#### Year 2024

IRIF Distinguished Talks Series

Tuesday May 14, 2024, 11AM, Amphi Turing

**Omer Reingold** (Stanford) *The multitude of group affiliations: Algorithmic Fairness, Loss Minimization and Outcome Indistinguishability*

While motivated in fairness, this alternative paradigm for training an indistinguishable predictor is finding a growing number of appealing applications, where the same predictor can later be used to optimize one of a large set of loss functions, under a family of capacity and fairness constraints and instance distributions.

Based on a sequence of works joint with (subsets of) Cynthia Dwork, Shafi Goldwasser, Parikshit Gopalan, Úrsula Hébert-Johnson, Lunjia Hu, Adam Kalai, Christoph Kern, Michael P. Kim, Frauke Kreuter, Guy N. Rothblum, Vatsal Sharan, Udi Wieder, Gal Yona and others.

IRIF Distinguished Talks Series

Wednesday February 7, 2024, 11AM, Amphi Turing, Bâtiment Sophie Germain

**Véronique Cortier** (Laboratoire lorrain de recherche en informatique et ses applications (LORIA)) *Electronic voting: design and formal verification*

#### Year 2023

IRIF Distinguished Talks Series

Wednesday November 8, 2023, 11AM, Amphi Turing

**Simon Peyton Jones** (Epic Games) *Beyond functional programming: the Verse programming language*

Verse is extremely ambitious: we want it to allow millions of programmers who have never met towrite code that inter-operates to build a shared virtual 3D simulation in which billions of users can interact. My current focus is on formally specifying the technical heart of Verse. At its core, Verse is a functional logic language, up to now rather a niche subject. In the talk I will give you a sense of what a functional logic language is; I will describe the challenges with giving it a formal definition; and I will sketch our progress in addressing this challenge using denotational semantics, rewrite rules, and a reference interpreter.

#### Year 2020

IRIF Distinguished Talks Series

Friday June 12, 2020, 10:45AM, Amphi Turing

**[Cancelled] Simon Peyton Jones** (Microsoft Research [Cambridge, England]) **IRIF Distinguished Talks Series**: TBA

IRIF Distinguished Talks Series

Friday March 20, 2020, 10:30AM, Amphi Turing

**[Cancelled] Joseph Mitchell** (State University of New York at Stony Brook) **IRIF Distinguished Talks Series**: Approximation Algorithms for Some Geometric Packing/Covering/Routing Problems

IRIF Distinguished Talks Series

Friday January 24, 2020, 10:30AM, Amphi Turing

**[Cancelled] Martin Grohe** (RWTH Aachen University) **IRIF Distinguished Talks Series**: Symmetry and Similarity

One of the earliest applications of isomorphism testing was in chemistry, more precisely chemic al information systems. Today, applications of isomorphism testing and symmetry detection are u biquitous in computing. Prominent examples appear in optimisation, malware detection, and machi ne learning. However, in many of these applications, we only need to decide if two structures a re sufficiently similar, rather than exactly the same. It turns out that determining how simila r two structures are is an even harder computational problem than deciding whether they are iso morphic.

My talk will be an introduction to algorithmic aspects of symmetry and similarity, ranging from the fundamental complexity theoretic “Graph Isomorphism Problem” to applications in optimisati on and machine learning.

#### Year 2019

IRIF Distinguished Talks Series

Friday April 12, 2019, 10:30AM, Amphi Turing

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

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.

IRIF Distinguished Talks Series

Monday March 18, 2019, 5PM, 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.

Please note unusual date and unusual location

#### Year 2018

IRIF Distinguished Talks Series

Friday November 16, 2018, 10:30AM, Amphithéâtre Pierre-Gilles de Gennes, Bât. Condorcet

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

IRIF Distinguished Talks Series

Friday July 13, 2018, 10:30AM, Amphi Turing

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

IRIF Distinguished Talks Series

Friday April 13, 2018, 10:30AM, Amphi Turing

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

#### Year 2017

IRIF Distinguished Talks Series

Friday November 10, 2017, 10:30AM, 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)

IRIF Distinguished Talks Series

Tuesday April 11, 2017, 10:30AM, 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.

IRIF Distinguished Talks Series

Friday March 3, 2017, 10:30AM, Amphi Turing

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

#### Year 2016

IRIF Distinguished Talks Series

Friday October 28, 2016, 10:30AM, 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 .

IRIF Distinguished Talks Series

Friday September 16, 2016, 10:30AM, 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.

IRIF Distinguished Talks Series

Thursday January 28, 2016, 10:30AM, Amphi Turing

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

Nachum Dershowitz has been a professor of computer science at Tel Aviv University since 1998. Prior to that, he was on the faculty of the University of Illinois at Urbana-Champaign. He coauthored the book, Calendrical Calculations (Cambridge University Press, 1997), with Edward Reingold, which won Choice's Outstanding Academic Title Award (2002) and is about to go into its fourth edition. He is also the author of The Evolution of Programs (Birkhäuser, 1983), coauthor of Calendrical Tabulations (Cambridge University Press, 2002), and editor of a dozen other volumes. His research interests include foundations of computing, computational logic, computational humanities, and combinatorial enumeration. He has received the Herbrand Award (2011), LICS Test-of-Time Award (2006), RTA Test-of-Time Award (2014) and Skolem Award (2015) and has been elected to Academia Europaea (2013).