Institut de Recherche en Informatique Fondamentale (IRIF)

CNRS

Université Paris Cité

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, qui héberge une équipe-projet Inria.

Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques.

L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), six sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences.

Postdoc position ANR-VeSyAM

27.1.2023
A full-time research associates position is available to work on the ​VeSyAm research project. The position will start in July 2023. Deadline to apply: 12 noon on 15 Feb 2023. Further information in the job description.

Emission Arrêt sur Images

25.1.2023
Claire Mathieu, membre de l’IRIF et spécialiste des algorithmes, est intervenue à l’émission Arrêt sur Images autour du ChatGPT. Comment cette IA construit-elle ses textes ? Pourquoi parvient-elle à couvrir à peu près n’importe quel sujet ?

Internship proposal at LS2N and IRIF

13.1.2023
Internship proposal for Masters student in computer science at LS2N and IRIF in Real-time analysis and verification of ROS2 robotic applications. To apply, please refer to the internship description.

Découpage électoral des circonscriptions législatives en France : Déséquilibres démographiques et contraintes territoriales

16.1.2023
Claire Mathieu and 8 other authors co-authored the article "Découpage électoral des circonscriptions législatives en France : Déséquilibres démographiques et contraintes territoriales" about a new perspective for understanding electoral maps, using computational social science to study the criteria which shape how electoral districts are drawn up in France.

Workshop LAFI'23

11.1.2023
LAFI'23, a workshop affiliated to POPL’23 about Languages for Inference, will be held on January 15, 2023, as a bi-located event in Boston and at Université Paris Cité. The Paris antenna will take place in salle Leduc, at the first floor of Saints-Pères building, 45 rue des Saints-Pères, 75006 Paris, from 3pm to 9:30pm Paris time. The The talks of V. Blanchi, G. Caylak, M. Pagani (IRIF), F. Zaiser will happen physically in Paris. Registration is mandatory.

Portrait Marie Albenque

14.12.2022
We are very pleased to welcome Marie Albenque, Senior Research Scientist at CNRS. Learn more about her and her work in this written interview.

One-year visitor - Lauren K. Williams

6.12.2022
We are happy to host Lauren K. Williams for a one-year visit at IRIF. To know more about her and her research, read her interview.

Prix de thèse de la chancellerie des Universités de Paris

12.12.2022
Jonas Landman, former PhD student at IRIF, is the 2022 winner of a thesis Prize from Chancellerie des Universités de Paris. His thesis “Quantum Algorithms for Unsupervised Machine Learning and Neural Networks” was awarded in the All Specialties Science Prize Category.


(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

One world numeration seminar
Mardi 31 janvier 2023, 14 heures, Online
Slade Sanderson (Universiteit Utrecht) Matching for parameterised symmetric golden maps

In 2020, Dajani and Kalle investigated invariant measures and frequencies of digits of signed binary expansions arising from a parameterised family of piecewise linear interval maps of constant slope 2. Central to their study was a property called ‘matching,’ where the orbits of the left and right limits of discontinuity points agree after some finite number of steps. We obtain analogous results for a parameterised family of ‘symmetric golden maps’ of constant slope $\beta$, with $\beta$ the golden mean. Matching is again central to our methods, though the dynamics of the symmetric golden maps are more delicate than the binary case. We characterize the matching phenomenon in our setting, present explicit invariant measures and frequencies of digits of signed $\beta$-expansions, and—time permitting—show further implications for a family of piecewise linear maps which arise as jump transformations of the symmetric golden maps.

Joint with Karma Dajani.

Algorithmes et complexité
Mercredi 1 février 2023, 14 heures, Salle 3052
Vincent Cohen-Addad (Google Research) Recent Progress on Correlation Clustering: The Power of Sherali-Adams and New Practical insights

Correlation clustering is a classic model for clustering with several applications in data mining and unsupervised machine learning. In this problem, we are given a complete graph where each edge is labeled + or -; and the goal is to find a partition of the vertex set so as to minimize the number of + edges across the parts of the partition plus the number of – edges within the parts of the partition.

We will first present a new result showing that a constant number of rounds of the Sherali-Adams hierarchy yields a strict improvement over the natural LP: we present the first better-than-two approximation for the problem, improving upon the previous approximation of 2.06 of Chawla, Makarychev, Schramm, Yaroslavtsev based on rounding the natural LP (which is known to have an integrality gap of 2). We will then review several recent ideas which have led to practical constant factor approximations to Correlation Clustering in various setups: distributed and parallel environments, differentially-private algorithms, dynamic algorithms, or sublinear time algorithms.

This is a combination of joint works with Euiwoong Lee, Alantha Newman, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski, Chenglin Fan and Andreas Maggiori.

Combinatoire énumérative et analytique
Jeudi 2 février 2023, 11 heures, IHP
Seminaire Flajolet (Vincent Juge, Jang Soo Kim, Olya Mandelshtam) IHP

Séminaire des doctorants
Jeudi 2 février 2023, 16 heures, 3052 and Zoom link
Aymeric Walch The categorical semantic iceberg finally explained

Denotational semantic is a field which consists in studying computation without computing. That is, a program P of type int → int can be seen on a high level as a function from the integers to the integers.

After a quick review of the idea behind denotational semantic, we will show that the word “denotational” can in fact be replaced by the word “categorical”. A program will not be interpreted as a mere function, but rather as a morphism in some category. This enlargement of perspective allows us to consider a lot more interesting interpretations for programs: relations, games, probability kernels…

We will then cover the basic categorical ingredients that makes a category a good candidate for interpreting computation. That is, a category must handle tupling and curryfication. If the time allows for it, we will then quickly introduce how those categorical ideas lead to the development of linear logic.

This talk *will not* assume any prior knowledge in category theory nor in denotational semantic.

Analyse et conception de systèmes
Jeudi 2 février 2023, 14 heures, salle séminaires au plateau SCAI +(Esclangon, 1er étage, campus Jussieu)
Marine Minier (Université de Lorraine) Comment les outils automatiques peuvent nous aider, nous cryptographes

Catégories supérieures, polygraphes et homotopie
Vendredi 3 février 2023, 14 heures, Salle 1007
Pierre-Louis Curien & Guillaume Laplante-Anfossi (IRIF & Melbourne University) Une preuve simple et connexe du théorème de cohérence de MacLane

Bien que le théorème de cohérence de MacLane pour les catégories monoïdales ait été prouvé initialement par une méthode proche de la réécriture, il présente un caractère topologique. C’est ce qui a poussé Kapranov à suggérer en 1993 une « preuve instantanée » de ce théorème basée sur l’existence d'une famille de polytopes qu’il nomme permutoassociaèdres. Dans la première partie, on formalisera cette idée, montrant que la cohérence de MacLane est une conséquence directe de la simple connexité des permutoassociaèdres. Cela suggère un lien combinatoire plus général entre cohérence n-catégorique et n-connexité de certains espaces, avatar « strict » de travaux infini-catégoriques récents de Shaul Barkan.

Dans la deuxième partie, on s'intéressera à l'instanciation du théorème général à la classe des “hypergraph polytopes” (aussi connus sous le nom de nestoèdres), dont les faces (et en particulier les sommets et les arêtes) sont décrits par des objets combinatoires appelés “constructs”. Les arêtes sont naturellement orientées à l'aide d'un ordre appelé ordre de Tamari généralisé, et lorsqu'on instancie encore davantage, à la classe des opéraèdres, on obtient un système de réécriture de termes convergent (sous-jacent au problème de cohérence des opérades catégorifiées de Dosen et Petric), ce qui permet dans ce cas d'obtenir la cohérence par des méthodes de réécriture (complétion de Squier). Les diagrammes obtenus sont légèrement différents de ceux de Dosen et Petric.

Automates
Vendredi 3 février 2023, 14 heures, Salle 3052
Florent Koechlin Two criteria to prove the inherent ambiguity of bounded context-free languages

A context-free language is inherently ambiguous if any grammar recognizing it is ambiguous, i.e. there is a word that is generated in two different ways. Deciding the inherent ambiguity of a context-free language is a difficult problem, undecidable in general. The first examples of inherently ambiguous languages were discovered in the 1960s, using iteration techniques on derivation trees. They belonged to a particular subfamily of context-free languages, called bounded context-free languages.
    Although they made it possible to prove the inherent ambiguity of several languages, as for example the language L = a^n b^m c^p with n=m or m=p, iteration techniques are still very laborious to implement, are very specific to the studied language, and seem even sometimes unadapted. For instance, the relative simplicity of the proof of inherent ambiguity of L completely collapses by replacing the constraint "n=m or m=p" by "n≠m or m≠p". 
    In this talk, I will present two useful criteria based on generating series to prove easily the inherent ambiguity of some bounded context-free languages. These languages, which have a rational generating series, resisted both the classical iteration techniques developed in the 1960’s and the analytic methods introduced by Philippe Flajolet in 1987.

Vérification
Lundi 6 février 2023, 11 heures, 1007 and Zoom link
Claudio Gomes (University of Aarhus) Application of formal methods to verification of self-adaptation loops in digital twins

The performance and reliability of Cyber-Physical Systems are increasingly aided through the use of digital twins, which mirror the static and dynamic behaviour of a Cyber-Physical System (CPS) in software. Digital twins enable the development of self-adaptive CPSs which reconfigure their behaviour in response to novel environments. It is crucial that these self-adaptations are formally verified at runtime, to avoid expensive re-certification of the reconfigured CPS. In this talk, I discuss formally verified self-adaptation in a digital twinning system, by constructing a non-deterministic model which captures the uncertainties in the system behaviour after a self-adaptation. We use Signal Temporal Logic to specify the safety requirements the system must satisfy after reconfiguration and employ formal methods based on verified monitoring over Flow* flowpipes to check these properties at runtime. This gives us a framework to predictively detect and mitigate unsafe self-adaptations before they can lead to unsafe states in the physical system.

Algorithmes et complexité
Mardi 7 février 2023, 11 heures, Salle 3052
Pierre Meyer (IRIF / Reichman University) On Low-End Obfuscation and Learning

Informally, obfuscation aims to compile programmes into unintelligible ones while preserving functionality. As a first approximation, this can be seen as trying to convert a programme to a “black-box representation”, which cannot be used for anything beyond obtaining its input/output behaviour. Learning, on the other hand, aims to generate the representation of a function given oracle access to it. In this talk, we will investigate new links between the two fields.

No specialised knowledge of cryptography or computational complexity is required, and the talk is aimed at a general TCS audience. For completeness however, we provide below a more technical description of our results.

Most recent works on cryptographic obfuscation focus on the high-end regime of obfuscating general circuits while guaranteeing computational indistinguishability between functionally equivalent circuits. Motivated by the goals of simplicity and efficiency, we initiate a systematic study of “low-end” obfuscation, focusing on simpler representation models and information-theoretic notions of security. We obtain the following results. 1) Positive results via “white-box” learning. We present a general technique for obtaining perfect indistinguishability obfuscation from exact learning algorithms that are given restricted access to the representation of the input function. We demonstrate the usefulness of this approach by obtaining simple obfuscation for decision trees and multilinear read-k arithmetic formulas. 2) Negative results via PAC learning. A proper obfuscation scheme obfuscates programs from a class C by programs from the same class. Assuming the existence of one-way functions, we show that there is no proper indistinguishability obfuscation scheme for k-CNF formulas for any constant k ≥ 3; in fact, even obfuscating 3-CNF by k-CNF is impossible. This result applies even to computationally secure obfuscation, and makes an unexpected use of PAC learning in the context of negative results for obfuscation. 3) Separations. We study the relations between different information-theoretic notions of indistinguishability obfuscation, giving cryptographic evidence for separations between them.

This is joint work with Elette Boyle, Yuval Ishai, Robert Robere, and Gal Yehuda, which was presented at ITCS 2023.

Combinatoire énumérative et analytique
Jeudi 9 février 2023, 14 heures, Salle 3052 et zoom
Groupe De Lecture Philippe Biane