IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, also hosting two Inria project-teams.

The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences.

IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), five are members of the Institut Universitaire de France IUF), and two are members of the Academia Europæa.

13.1.2020
Iordanis Kerenidis, CNRS senior researcher (IRIF) and director of the Paris Centre for Quantum Computing, is one of the three authors of the report about Quantum Technologies requested by the French government.

15.1.2020
IRIF has the great pleasure to welcome a new starting researcher (Inria): Emilio J. Gallego Arias, an expert in interactive theorem proving and the Coq proof assistant.

7.1.2020
Guillaume Ducoffe (Bucarest Univ. and ICI) will present at SODA’20 a result obtained with Michel Habib (IRIF) and Laurent Viennot (IRIF and Inria) showing that diameter can be computed in truly sub-quadratic time in any H-minor free graph. This extends a recent breakthrough on planar graphs.

7.1.2020
Claire Mathieu and Simon Mauras (IRIF) will present at SODA’20 several approximation algorithms for top-list aggregation, an optimization problem from the field of information retrieval: compute the output full-ranking which is closest to a collection of input top-lists.

6.1.2020
We are delighted to host as part of our IRIF Distinguished Talks Series Martin Grohe (RWTH Aachen University) on Friday January 24, 2020, 10:30am for a talk entitled “Symmetry and Similarity”.

10.1.2020
Université de Paris has opened one permanent associate professor position in Computer Science. Recruited researcher will join IRIF.

10.1.2020
IRIF has the great pleasure to welcome a new research scientist (CNRS): Matthieu Josuat-Vergès, an expert in enumerative combinatorics and algebraic combinatorics.

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.

(These news are displayed using a randomized-priority ranking.)

Algorithms and complexity
Tuesday January 21, 2020, 11AM, Salle 1007
Tatiana Starikovskaya (ENS) Sliding window property testing for regular languages

We discuss the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window n and a stream of symbols. At each time instant, we must decide whether the suffix of length n of the current stream (the window'') belongs to a given regular language.

In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We consider deterministic and randomized sliding window property testers with one-sided and two-sided errors. In particular, we show that for any regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

The talk is based on a joint work with Ganardi, Hucke, and Lohrey published in ISAAC 2019.

Semantics
Wednesday January 22, 2020, 10:30AM, Salle 3014
John Bourke (Masaryk University (Brno)) Weak adjoint functor theorems and accessible infinity-cosmoi

The General Adjoint Functor Theorem of Freyd has a straightforward extension to the enriched setting. There is also a Weak Adjoint Functor Theorem, due to Kainen, and providing a sufficient condition for the existence of a weak left adjoint, where weakness refers to the existence but not uniqueness of factorizations. I will report on recent joint work with Steve Lack and Lukas Vokrinek, in which we prove a weak adjoint functor theorem in the enriched context. This actually contains the other three theorems as special cases. Our base for enrichment will be a monoidal model category. Our motivating example involves simplicially enriched categories, where the base category of simplicial sets is equipped with the Joyal model structure. The theorem then has applications to the Riehl-Verity theory of infinity-cosmoi.

Enumerative and analytic combinatorics
Thursday January 23, 2020, 2PM, Salle 1007
Sergey Dovgal (Université Paris 13) The critical point of phase transition in random objects

We will discuss the emerging substructures in graphs with degree constraints, digraphs, acyclic digraphs, and 2-CNF below the point of their respective phase transitions. While long time ago, probabilistic method allowed to establish the location of the transition points, sometimes without establishing the fine structure inside the window, more and more refined methods gradually become available. With analytic combinatorics as a main tool, we will see what exactly is happening when a random structure approaches its boiling point. Based on joint works with Elie de Panafieu and Vlady Ravelomanana.

Proofs, programs and systems
Thursday January 23, 2020, 10:30AM, Salle 3052
Robert Atkey (University of Strathclyde) To be announced.

Algorithms and complexity
Thursday January 23, 2020, 11AM, Salle 1007
Moni Naor (Weizmann Institute) Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency matrix. You are given as an “untrusted hint” an isomorphic copy of the graph. You must always be correct, but the number of queries made is only measured when the hint is correct. Do such unlabeled certificates help? In the worst case? Per instance?

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of instance optimality“. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

Algorithms and discrete structures
Thursday January 23, 2020, 11AM, Salle 1007
Moni Naor (Weizmann Institute) Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency matrix. You are given as an “untrusted hint” an isomorphic copy of the graph. You must always be correct, but the number of queries made is only measured when the hint is correct. Do such unlabeled certificates help? In the worst case? Per instance?

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of instance optimality”. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

IRIF seminar
Friday January 24, 2020, 10:30AM, Amphi Buffon
Martin Grohe (RWTH Aachen University) IRIF Distinguished Talks Series: Symmetry and Similarity

Symmetry is a fundamental concept in mathematics, the sciences, and beyond. Understanding symmetries is often crucial for understanding structures. In computer science, we are mainly interested 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”). Algorithmically, this is a difficult task that has received a lot of attention since the early days of computing. It is a major open problem in theoretical computer science to determine the precise computational complexity of this “Graph Isomorphism Problem”.

One of the earliest applications of isomorphism testing was in chemistry, more precisely chemical information systems. Today, applications of isomorphism testing and symmetry detection are ubiquitous in computing. Prominent examples appear in optimisation, malware detection, and machine learning. However, in many of these applications, we only need to decide if two structures are sufficiently similar, rather than exactly the same. It turns out that determining how similar two structures are is an even harder computational problem than deciding whether they are isomorphic.

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 optimisation and machine learning.

Higher categories, polygraphs and homotopy
Friday January 24, 2020, 2PM, Salle 1007
Sebastian Posur (Universität Siegen) Methods of constructive category theory

Categorical abstraction is a powerful organizing principle in computer algebra. In this talk, we explain the concept of constructive category theory and how we implement this concept in our software project CAP-Categories, algorithms, programming. In CAP it is possible to implement higher algorithms and data structures using basic categorical operations as primitives, which in turn often rely on classical algorithms in computer algebra like the computation of Gröbner bases. As an example, we show how our categorical framework can be used for computing with finitely presented functors.

Automata
Friday January 24, 2020, 2:30PM, Salle 3052
Olivier Bournez (LIX) Caractérisation de classes de complexité et calculabilité avec des équations différentielles.

We will discuss the expressive and computational power of Ordinary Differential Equations (ODEs). We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes.