seminaires:irif:index

Séminaire

IRIF Distinguished Talks Series

Le calendrier des séances (format iCal).
Pour ajouter le calendrier des séances à votre agenda favori, souscrire au calendrier en indiquant ce lien.

Contact(s)

Adi Rosén

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.

Séances passées

Année 2024

IRIF Distinguished Talks Series
Mardi 3 décembre 2024, 11 heures, Amphi Turing
Dexter Kozen (Cornell University) Probability and Angelic Nondeterminism with Multiset Semantics (joint work with Shawn Ong and Stephanie Ma)

Many modern computational systems involve both probability and nondeterminism, but the combination of the two in a formal logic is a notoriously challenging problem. One would like to reason about the correctness of programs involving constructs for both probabilistic and nondeterministic choice, but it is known that the standard way of modeling nondeterministic choice as a set of possibilities does not interact well with probabilistic choice, chiefly due to the lack of a suitable distributive law between the two. Many researchers over the years have grappled with this issue and proposed a variety of workarounds.

In this talk I will describe an alternative approach that models nondeterministic choice as a multiset operator instead of a set operator. It turns out that this simple change makes everything work much more smoothly, as there is a distributive law between probability and multisets. I will describe a class of probabilistic automata with nondeterminism modeled by multisets, along with a corresponding class of expressions analogous to regular expressions in this context, and show that they are equivalent in expressive power. In these models, an input string is not just accepted with some probability, but accepted with some finite multiplicity with some probability. I will give several examples and describe exactly why multisets work where sets do not.

IRIF Distinguished Talks Series
Mardi 14 mai 2024, 11 heures, Amphi Turing
Omer Reingold (Stanford) The multitude of group affiliations: Algorithmic Fairness, Loss Minimization and Outcome Indistinguishability

We will survey a rather recent and very fruitful line of research in algorithmic fairness, coined multi-group fairness. We will focus on risk prediction, where a machine learning algorithm tries to learn a predictor to answer questions of the form “what is the probability that patient x will experience a particular medical condition?” Training a risk predictor to minimize a loss function fixed in advance is the dominant paradigm in machine learning. However, global loss minimization may create predictions that are mis-calibrated on sub-populations, causing harm to individuals of these populations. Multi-group fairness tries to prevent forms of discrimination to a rich (possibly exponential) collection of arbitrarily intersecting groups. In a sense, it provides a computational perspective on the meaning of individual risks and the classical tension between clinical prediction, which uses individual-level traits, and actuarial prediction, which uses group-level traits.

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
Mercredi 7 février 2024, 11 heures, 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

Electronic voting aims at guaranteeing apparently conflicting properties: no one should know how I voted and yet, I should be able to check that my vote has been properly counted. Electronic voting belongs to the large family of security protocols, that aim at securing communications against powerful adversaries that may read, block, and modify messages. In this talk, we will see how to design secure electronic voting protocols and how to analyze them using formal methods, in order to detect attacks at an early stage, or prove security, yielding a better understanding of the security guarantees and the threat model.

Année 2023

IRIF Distinguished Talks Series
Mercredi 8 novembre 2023, 11 heures, Amphi Turing
Simon Peyton Jones (Epic Games) Beyond functional programming: the Verse programming language

Since joining Epic Games in late 2021, I have been involved in the design and development of Verse, a new, declarative programming language that Epic plans to use as the language of themetaverse.

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.

Année 2020

IRIF Distinguished Talks Series
Vendredi 12 juin 2020, 10 heures 45, Amphi Turing
[Cancelled] Simon Peyton Jones (Microsoft Research [Cambridge, England]) IRIF Distinguished Talks Series: TBA

IRIF Distinguished Talks Series
Vendredi 20 mars 2020, 10 heures 30, 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

A fundamental class of combinatorial optimization problems involve packing and covering. Examples include maximum independent set, dominating set, set cover, hitting set, etc. Motivated by applications in sensor networks and robotics, natural instances of such problems arise in geometric situations, such as covering points with a small number of disks, viewing “art galleries” with a small number of guards or with a mobile guard on a short route, packing disks or other shapes within a bounded domain, etc. Almost all of these problems are NP-hard even in simple two-dimensional settings. The problems get even harder when we take into account uncertain data, time constraints for scheduled coverage, and routing/connectivity problems in combination with coverage constraints. We discuss several of these geometric optimization problems from the perspective of approximation algorithms and we describe some techniques that have led to new or improved bounds or running times for selected packing, covering, and routing/coverage problems.

IRIF Distinguished Talks Series
Vendredi 24 janvier 2020, 10 heures 30, Amphi Turing
[Cancelled] Martin Grohe (RWTH Aachen University) IRIF Distinguished Talks Series: Symmetry and Similarity

Symmetry is a fundamental concept in mathematics, the sciences, and beyond. Understanding symme tries is often crucial for understanding structures. In computer science, we are mainly interes ted in the symmetries of combinatorial structures. Computing the symmetries of such a structure is essentially the same as deciding whether two structures are the same (“isomorphic”). Algori thmically, this is a difficult task that has received a lot of attention since the early days o f computing. It is a major open problem in theoretical computer science to determine the precis e computational complexity of this “Graph Isomorphism Problem”.

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.

Année 2019

IRIF Distinguished Talks Series
Vendredi 12 avril 2019, 10 heures 30, 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)

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.

IRIF Distinguished Talks Series
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

Finding the connected components of a graph is one of the most basic graph problems. Although it is easy to find components sequentially using graph search or a disjoint set union algorithm, some important applications require finding the components of huge graphs, making sequential algorithms too slow. We describe recent progress on concurrent algorithms for this problem. Some simple algorithms seem surprisingly hard to analyze, and claims made in the literature about some of them are false.

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

Please note unusual date and unusual location

Année 2018

IRIF Distinguished Talks Series
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

An atomic cross-chain swap is a distributed coordination task where multiple parties exchange assets across multiple blockchains, for example, trading bitcoin for ether. An atomic swap protocol guarantees (1) if all parties conform to the protocol, then all swaps take place, (2) if some coalition deviates from the protocol, then no conforming party ends up worse off, and (3) no coalition has an incentive to deviate from the protocol. A cross-chain swap is modeled as a directed graph D, whose vertexes are parties and whose arcs are proposed asset transfers. For any pair (D,L), where D=(V,A) is a strongly-connected directed graph and L⊂V a feedback vertex set for D, we give an atomic cross-chain swap protocol for D, using a form of hashed timelock contracts, where the vertexes in L generate the hashlocked secrets. We show that no such protocol is possible if D is not strongly connected, or if D is strongly connected but L is not a feedback vertex set.

IRIF Distinguished Talks Series
Vendredi 13 juillet 2018, 10 heures 30, Amphi Turing
Christos Papadimitriou (Columbia University) IRIF Distinguished Talks Series: A computer scientist thinks about the Brain

How does the Brain give rise to the Mind? How do neurons and synapses, molecules and genes, evolution and development, give rise to behavior and cognition, language and intelligence? Despite lightning progress in recording and molecular technology and a deluge of experimental data, we do not seem to get closer to an answer. This is a talk about admiring and appreciating the problem, and proposing a new approach based on a recognized but little studied intermediate level of Brain computation carried out by the synchronous firing of large and highly interconnected sets of neurons called assemblies. We show that assemblies give rise to a novel computational system, and we speculate that they may instrument higher cognitive functions, such as language and math.

IRIF Distinguished Talks Series
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

A dynamic graph algorithms is a data structure that maintains a property of a graph while it is modified by edge insertions and deletions. The last few years have seen exciting new developments in dynamic graph algorithms, namely strong conditional lower bounds and dynamic algorithm based on the primal-dual approach.

Année 2017

IRIF Distinguished Talks Series
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)

The undecidability of Hilbert's tenth problem (H10) about Diophantine equations turned out to be a powerful tool for establishing the undecidability of many other decision problems. The technique developed for proving the undecidability of H10 gave the possibility to find unexpected relationships between Diophantine equations and some other classical mathematical problems.

IRIF Distinguished Talks Series
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?

We revisit one of the most basic questions of database theory: the equivalence of first-order logic (FO), relational algebra (RA), and the core of SQL. Despite being at the heart of relational theory, these questions do not have satisfactory answers in the literature. The well known equivalence of FO and RA, and existing translations from SQL to RA, work only for simple models that fall short of what real databases use. Proving results about real SQL, rather than a theoretical reconstruction, is hampered by the lack of formal SQL semantics: the Standard is too vague for the purpose, and previous attempts at formalizing SQL's semantics made many simplifying assumptions that do not hold in real life. On the logic side, SQL mixes Boolean and 3-valued logics in a way that has never been properly studied.

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
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)

Probabilistic programming is en vogue. It is used to describe complex Bayesian networks, quantum programs, security protocols and biological systems. Programming languages like C, C#, Java, Prolog, Scala, etc. all have their probabilistic version. Key features are random sampling and means to adjust distributions based on obtained information from measurements and system observations. We show some semantic intricacies, argue that termination is more involved than the halting problem, and discuss recursion and run-time analysis.

Année 2016

IRIF Distinguished Talks Series
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

In software industry, engineers do formal logic day in and day out, even though they may not realize that. As a rule, they have not studied logic. Instead, they spent a lot of time studying calculus which they use rarely, if ever. I'll try to illustrate why logic is so relevant and why it is hard for software engineers to pick it up.

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
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)

A vast amount of modern scientific and technological knowledge relies on the software that we have been collectively writing: deep knowledge from fields like mathematics, physics, chemistry, biology, medicine, finance and social sciences is now inextricably embodied into complex software systems, which model it at a level of detail that goes way beyond that of the usual scientific publications.

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
Jeudi 28 janvier 2016, 10 heures 30, Amphi Turing
Nachum Dershowitz (Tel Aviv University) Ada and Computation

Ada Lovelace (born 200 years ago) wrote presciently about digital numerical calculations. She expressed its features poetically: “We may say most aptly that [Babbage's] Analytical Engine weaves algebraical patterns just as the Jacquard loom weaves flowers and leaves.” Ada explained the generality of digital computation, saying that “the engine can arrange and combine its numerical quantities exactly as if they were letters or any other general symbols.” We will discuss some of the expected and unexpected consequences of alternate representations of computational data. On the other hand, Ada wrote that “the engine [is] the material expression of any indefinite function of any degree of generality and complexity.” This we now know was overstating her case. We will discuss the formalization of the notion of effective computation and its consequences vis-a-vis computability and complexity of 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).