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.

École de Printemps d’Informatique Théorique 2023

24.3.2023
The 50th edition of EPIT (École de Printemps d’Informatique Théorique) will have as theme The Kaleidoscope of Complexity Theory and will take place on June 12-16, 2023 at the Vieille Perrotine CAES/CNRS holiday center on the Oléron Island, in France.

Interview PhD thesis Farzad Jafarrahmani

6.3.2023
Farzad Jafarrahmani, former PhD student at IRIF explains his thesis Fixpoints of Types in Linear Logic from a Curry-Howard-Lambek Perspective in this written interview.

JACM Articles from 2022

7.3.2023
The paper “Decentralized Asynchronous Crash-resilient Runtime Verification” authored by Borzoo Bonakdarpour (MSU), Pierre Fraigniaud (IRIF), Sergio Rajsbaum (UNAM), David Rosenblueth (UNAM), and Corentin Travers (LIS) has been selected in the “sample of [eight] exciting [..] articles on a diverse range of topics that were published in 2022” in the Journal of the ACM (JACM).

Journées Nationales du GDR IM 2023

10.3.2023
Les prochaines Journées Nationales du GDR IM (JNIM 2023) auront lieu à l'Université Paris Cité du 4 avril au 7 avril et sont organisées par l'IRIF. Programme et inscription ici.

Conférence vidéo “Manuel de Cryptanalyse à l’usage de la NSA”

6.3.2023
“Manuel de Cryptanalyse à l’usage de la NSA” est une conférence ludique, présentée par Sylvain Perifel – Maître de conférences (Université Paris Cité/IRIF) à l’occasion de l’édition 2022 de la Fête de la Science. Elle retrace et met en pratique les différentes avancées historiques de cette science, du code de César à RSA en passant par les substitutions mono-alphabétiques et par le chiffre de Vigenère.

Appel à manifestation d'intérêt 2023 - Médiation scientifique

7.3.2023
Pour la troisième année consécutive, la Faculté des Sciences d’Université Paris Cité lance un appel à manifestation d’intérêt pour accompagner et soutenir ses membres dans leurs initiatives ayant vocation à rendre accessible un sujet de recherche scientifique à un public non spécialiste. Date limite 20 mars 2023 minuit.

L’Oréal-UNESCO Young Talents award 2023

10.2.2023
The deadline to apply to the prestigious L’Oréal-UNESCO Young Talents award 2023 is February 27, 2023.


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

Algorithmes et complexité
Lundi 3 avril 2023, 14 heures, Salle 3052
Gabriel Le Bouder (LIP6) Memory-Optimization for Self-Stabilizing Distributed Algorithms

Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it will return a normal behavior in finite time. Several constraints concern algorithms designed for distributed systems. Asynchrony is one emblematic example. With the development of networks of connected, autonomous devices, it also becomes crucial to design algorithms with a low energy consumption, and not requiring much in terms of resources.

One way to address these problems is to aim at reducing the size of the messages exchanged between the nodes of the network. This thesis focuses on the memory optimization of the communication for self-stabilizing distributed algorithms. We will present a negative results, proving the impossibility to solve some problems under a certain limit on the size of the exchanged messages, and a particularly efficient algorithms in terms of memory for one fundamental problem in distributed systems: the token circulation.

Vérification
Lundi 3 avril 2023, 11 heures, 1007 and Zoom link
Thomas Nowak (ENS Paris-Saclay) Reaching Consensus in Hostile Environments

Reaching consensus in a distributed system is one of the most fundamental problems studied in distributed computing. It is non-trivial due to uncertainties related to unsuccessful communication and process faults. In particular, the celebrated FLP impossibility result shows why scheduling an event via an asynchronous communication medium such as email is difficult. In this talk, I will present our recent results on exact and approximate consensus in hostile environments such as dynamic networks (e.g., due to mobility of agents) and synthetic bacterial cultures

Formath
Lundi 3 avril 2023, 14 heures, 1007
Olivier Laurent (Équipe Plume, Laboratoire de l'Informatique du Parallélisme (LIP), ENS Lyon) 1, 2, 3, Yalla: Linear Logic in Coq

We discuss the formalization of Linear Logic, through the development of the Yalla library for Coq:

https://perso.ens-lyon.fr/olivier.laurent/yalla/

The initial specification was to get a library which:

  • would provide standard results on the proof theory of Linear Logic;
  • could be reused, thus in particular able to deal with some variants of the system;
  • should be compatible with the Curry-Howard interpretation of proofs, thus faithful to their computational content.

We will describe the evolution of the project and how it matches this specification through the different versions of the library: Yalla 1, Yalla 2 (current version), Yalla 3 (future directions).

Following all previous known works, Yalla 1 defined proofs in Prop. It relies on an explicit exchange rule for dealing with the computational content of proofs. Yalla 2 corresponds to a move to Type to be able to extract computational informations from proofs. Yalla 3 will rely on a different way of approaching exchange to be able to deal with local transformations of proofs more easily.

Algorithmes et structures discrètes
Mardi 4 avril 2023, 15 heures, 3052
Roland Grappe (LIPN) On box-perfect graphs

Box-totally dual integral polyhedra are polyhedra hidden behind strong min-max relations, such as the MaxFlow-MinCut Theorem of Ford and Fulkerson. Box-perfect graphs are the perfect graphs whose stable set polytope is box-totally dual integral, and the question of their characterization, raised is 1982 by Cameron and Edmonds, is still open.

In this talk, we will survey recent characterizations of box-totally dual integral polyhedra, and discuss some consequences for box-perfect graphs. This is based on joint works with P. Chervet and L.-H. Robert.

Algorithmes et structures discrètes
Mercredi 5 avril 2023, 15 heures, 3052
Lélia Blin (LIP6) Self-Stabilizing Distributed Algorithms

In the context of large-scale networks, fault tolerance is a necessity. Self-stabilization is an algorithmic approach to fault tolerance in distributed systems. Its aim is to manage processors' memory corruption due to transient failures. The efficiency of a self-stabilizing algorithm is characterized by several parameters, including (1) the time taken by the system to return to a legal configuration after an arbitrary corruption of its processors' memory, and (2) the memory space used by the processors to execute the algorithm. Minimizing memory space is motivated by many aspects, such as networks (e.g. sensor networks) with limited memory space, minimizing data exchanges between processors, and limiting information storage to use redundancy techniques. This seminar will present self-stabilization through two main classical problems: constructing spanning trees, especially those of minimum weight, and electing a leader. It will cover the links between self-stabilization and distributed decision techniques, including computing lower bounds on memory space needed to solve the aforementioned problems using self-stabilizing algorithms.

Algorithmes et complexité
Jeudi 6 avril 2023, 11 heures, Salle 3052
Yuval Ishai (Technion) Cryptography from One-Way Noisy Communication

We consider the traditional goals of cryptography, including secure communication and secure computation, when allowing only one-way communication over noisy channels: - Can Alice transmit a message to Bob without Eve learning this message? - Can Alice transmit exactly one of two messages to Bob without Alice learning which message was received?

We show how to circumvent information-theoretic impossibility results by settling for computational security and using the power of cryptographic obfuscation. In particular, under plausible assumptions, we obtain a positive answer to the first question whenever Alice's channel to Bob is not a degradation of the channel to Eve, and a positive answer to the second question over simple channels such as a binary symmetric channel or a binary erasure channel.

The first part of the talk is based on joint work with Alexis Korb, Paul Lou, and Amit Sahai. The second part is based on joint work with Shweta Agrawal, Eyal Kushilevitz, Varun Narayanan, Manoj Prabhakaran, Vinod M. Prabhakaran, and Alon Rosen.

Séminaire des doctorants
Jeudi 6 avril 2023, 16 heures, 3052 and Zoom link
Avinandan Das Efficient Semi-Streaming Algorithms and Lower Bounds for Degeneracy Based Graph Coloring

In this talk, we will introduce a space constrained model of computation, aka the Streaming Model. In particular, we will look at a simple algorithm for degeneracy based graph coloring in this model, which was proposed in 2019 and is currently the state of the art (in terms of number of colors used). We will complement the algorithm with a corresponding lower bound which uses a reduction to the problem of indexing in communication complexity and end with an open problem.

No prerequisite is assumed and every notion used will defined in the talk.

This presentation is based on the paper “Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models” by Suman Kalyan Bera, Amit Chakrabarti and Prantar Ghosh.

Automates
Vendredi 7 avril 2023, 14 heures, Salle 3052
Mahsa Shirmohammadi Stochastic games and strategy complexity

This talk is about winning strategies in Markov decision processes and stochastic games and is aimed at a general computer science audience. We start by recalling some of the basic notions in game theory, such as values, strategies, and the memory requirements of optimal and ε-optimal strategies. We will describe a set of recent advances on strategy complexity of verification-centered objectives, such as subclasses of parity objectives, in terms of parameters such as the cardinality of the state space, branching factor of the transition function, and whether the game is concurrent or turn-based.

Algorithmes et complexité
Mardi 11 avril 2023, 11 heures, Salle 3052
Harold Nieuwboer (CWI, Amsterdam) Non encore annoncé.

Combinatoire énumérative et analytique
Jeudi 13 avril 2023, 11 heures, IHP
Seminaire Flajolet TBD