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é, et 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. Sept de ses membres ont été lauréats de l'European Research Council (ERC), trois 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.

Suivez nous sur Mastodon, Twitter/X et LinkedIn :

LinkedIn Twitter/X Mastodon

book_basics_of_programming_algorithms.jpeg

11.9.2024
Roberto Mantaci et Jean-Baptiste Yunès ont publié un livre intitulé « Basics of Programming and Algorithms, Principles and Applications ». Il fournit un contenu de base pour l'enseignement de la programmation et des algorithmes, couvrant l'analyse des performances des algorithmes et les connaissances essentielles en programmation Python.

formatsbestpaperaward2024.jpg

18.9.2024
Neha Rino (stagiaire MPRI à l'IRIF en 2023), Eugène Asarin et Mohammed Foughali ont remporté le Best Paper Award à FORMATS. Ce travail formule et résout par un algorithme efficace le problème du suivi quantitatif : calculer un nombre réel caractérisant dans quelle mesure la trace donnée d'un système temps réel satisfait sa spécification.

ashwin_nayak.jpg

2.9.2024
Ashwin Nayak (professeur à l'Université de Waterloo) sera en visite à l'IRIF de septembre à octobre 2024. Ses recherches portent sur les algorithmes quantiques, la complexité et la communication. Il a beaucoup collaboré avec le Dr Frédéric Magniez et d'autres membres de l'IRIF sur ces sujets. En s'appuyant sur leurs collaborations de recherche, le Dr. Magniez et lui-même ont dirigé un programme international d'échange d'étudiants entre le Canada et un certain nombre d'institutions de l'UE, ainsi qu'un projet PICS entre l'Institute for Quantum Computing de l'Université de Waterloo et l'IRIF. Ashwin se réjouit de renouer ces liens lors de sa prochaine visite.

perso-delia-kesner.jpg

26.8.2024
Delia Kesner est oratrice invitée à la conférence internationale Lambda World qui aura lieu à Cadiz (Espagne) du 2 au 4 octobre 2024.

perso_robinvacus.jpg

5.9.2024
Le comité du prix de thèse de doctorat 2024 Principles of Distributed Computing a décidé de partager le prix entre deux lauréats, dont Robin Vacus pour sa thèse « Algorithmic Perspectives to Collective Natural Phenomena » (Perspectives algorithmiques sur les phénomènes naturels collectifs). Il a effectué son doctorat sous la direction d'Amos Korman et de Pierre Fraigniaud, à l'Université Paris Cité. Sa thèse applique une approche de systèmes distribués à des problèmes et des modèles inspirés de la biologie et de la sociologie.

29.7.2024
Le logiciel de vidéoconférence «Galène», développé par Juliusz Chroboczek, membre de l'IRIF, a été utilisé pour la conférence LibrePlanet 2024, organisée par la Free Software Foundation (FSF). Un retour d'expérience a été publié sur leur site :


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

Preuves, programmes et systèmes
Jeudi 19 septembre 2024, 10 heures 30, ENS Lyon
Clovis Eberhart, Zeinab Galal, Vincent Moreau CHOCOLA seminar series

Please see https://chocola.ens-lyon.fr/events/meeting-2024-09-19/ for the talk abstracts.

Programmation
Lundi 23 septembre 2024, 10 heures, 3071
Gabriel Scherer (IRIF) Pattern-matching on mutable values: danger!

The OCaml pattern-matching compiler is unsound, it generates incorrect code in the obscure corner case where we match on a value with mutable fields, and those fields are mutated during pattern-matching – from when clauses, allocation callbacks, or an access race in concurrent execution.

We recall the overall compilation strategy of the OCaml compiler, and explain how to weaken its optimization information to remain correct on mutable data.

Algorithmes et complexité
Mercredi 25 septembre 2024, 11 heures, Salle 3052
Sanjeev Khanna (University of Pennsylvania) A Faster Combinatorial Algorithm for Maximum Bipartite Matching

The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp (1973) shows that maximum bipartite matching can be solved in $O(m \sqrt{n})$ time on a graph with $n$ vertices and $m$ edges. For the case of very dense graphs, a fast matrix multiplication based approach gives a running time of $O(n^{2.371})$. These results represented the fastest known algorithms for the problem until 2013, when Madry introduced a new approach based on continuous techniques achieving much faster runtime in sparse graphs. This line of research has culminated in a spectacular recent breakthrough due to Chen et al. (2022) that gives an $m^{1+o(1)}$ time algorithm for maximum bipartite matching (and more generally, for min cost flows).

This raises a natural question: are continuous techniques essential to obtaining fast algorithms for the bipartite matching problem? In this talk, I will describe a new, purely combinatorial algorithm for bipartite matching, that runs in $\tilde{O}(m^{1/3}n^{5/3})$ time, and hence outperforms both Hopcroft-Karp and the fast matrix multiplication based algorithms on moderately dense graphs. I will also briefly discuss some subsequent work that further improves this runtime.

This is joint work with Julia Chuzhoy (TTIC).

Preuves, programmes et systèmes
Jeudi 26 septembre 2024, 10 heures 30, Salle 3052 & online (Zoom link)
Xuejing Huang Non encore annoncé.

Catégories supérieures, polygraphes et homotopie
Vendredi 27 septembre 2024, 14 heures, Salle 3071
Thibaut Benjamin Naturalité dans les omega-catégories faibles et cellules d'Eckmann-Hilton en dimension supérieure

Dans cet exposé, je vais présenter des travaux concernant le calcul de témoins de naturalité des opérations dans les omega-catégories faibles. Intuitivement, les témoins de naturalité traduisent du fait que chacune des opération d'une omega-catégorie faible se doit d'être un omega-foncteur faible. Bien que l'on manque d'outils pour exprimer formellement cette intuition, on peut explorer ce que cela signifie en petite dimension, ce qui amène à une notion que l'on a appelée la fonctorialité des opération, puis dans un second temps à la notion de naturalité. Je vais esquisser une construction permettant d'obtenir un témoin de naturalité associé à chacune des opérations d'une omega-catégorie, en m'appuyant sur la combinatoire des carrés et de leur composition. J'illustrerai ensuite cette construction en introduisant les cellules d'Eckmann-Hilton, et en montrant que la construction des témoins de naturalité permet de déduire des cellules d'Eckmann-Hilton en dimension supérieures à partir de celles en petites dimension.

Formath
Lundi 30 septembre 2024, 14 heures, 3052
Dominik Kirst (Picube, IRIF) Non encore annoncé.

Algorithmes et complexité
Mardi 1 octobre 2024, 11 heures, Salle 3052
Philips George John (NUS, Singapore) Distribution Learning meets Graph Structure Sampling

One world numeration seminar
Mardi 1 octobre 2024, 14 heures, Online
Dong Han Kim (Dongguk University) Uniform Diophantine approximation on the Hecke group $H_4$

Dirichlet's uniform approximation theorem is a fundamental result in Diophantine approximation that gives an optimal rate of approximation. We study uniform Diophantine approximation properties on the Hecke group $H_4$ in terms of the Rosen continued fractions. For a given real number $\alpha$, the best approximations are convergents of the Rosen continued fraction and the dual Rosen continued fraction of $\alpha$. We give analogous theorems of Dirichlet uniform approximation and the Legendre theorem with optimal constants. This is joint work with Ayreena Bakhtawar and Seul Bee Lee.

Preuves, programmes et systèmes
Jeudi 3 octobre 2024, 10 heures 30, Salle 3052
Jonas Frey (Université Sorbonne Paris Nord) Duality for generalized algebraic theories

Gabriel-Ulmer duality is a contravariant biequivalence between small finite-limit categories and locally finitely presentable categories, which in the spirit of Lawvere's functorial semantics can be viewed as a *theory-model duality*: small finite-limit categories C are viewed as theories, and the lfp category FL(C, Set) of finite-limit preserving Set-valued functors is viewed as category of models of of C. The opposite of C can be reconstructed up to equivalence from Lex(C,Set) as full subcategory of *compact* objects.

The talk presents a *refinement* of Gabriel-Ulmer duality which is motivated by dependent type theory: finite-limit categories are replaced by *clans*, ie categories with a terminal object and a pullback-stable class of maps which is closed under composition, reflecting the structure of syntactic categories of *generalized algebraic theories* (GATs). The category of models of every GAT/clan is lfp, and to be able to reconstruct the clan we equip it with a *weak factorization system*, which in the classical case of ordinary algebraic theories (groups, rings, …) consists of projective extensions on the left, and regular epimorphisms on the right.

Details can be found in the following preprint:

https://arxiv.org/abs/2308.11967

Soutenances de thèses
Vendredi 4 octobre 2024, 14 heures, Amphithéâtre Turing, Bâtiment Sophie Germain
Klara Nosan Zero problems in polynomial models

Polynomial models are ubiquitous in computer science, arising in the study of automata and formal languages, optimisation, game theory, control theory, and numerous other areas. In this thesis, we consider models described by polynomial systems of equations and difference equations, where the system evolves through a set of discrete time steps with polynomial updates at every step. We explore three aspects of “zero problems” for polynomial models: zero testing for algebraic expressions given by polynomials, determining the existence of zeros for polynomial systems and determining the existence of zeros for sequences satisfying recurrences with polynomial coefficients.

In the first part, we study identity testing for algebraic expressions involving radicals. That is, given a k-variate polynomial represented by an algebraic circuit and k real radicals, we examine the complexity of determining whether the polynomial vanishes on the radical input. We improve on the existing PSPACE bound, placing the problem in coNP assuming the Generalised Riemann Hypothesis (GRH). We further consider a restricted version of the problem, where the inputs are square roots of odd primes, showing that it can be decided in randomised polynomial time assuming GRH.

We next consider systems of polynomial equations, and study the complexity of determining whether a system of polynomials with polynomial coefficients has a solution. We present a number-theoretic approach to the problem, generalising techniques used for identity testing, showing the problem belongs to the complexity class AM assuming GRH. We discuss how the problem relates to determining the dimension of a complex variety, which is also known to belong to AM assuming GRH.

In the final part of this thesis, we turn our attention to sequences satisfying recurrences with polynomial coefficients. We study the question of whether zero is a member of a polynomially recursive sequence arising as a sum of two hypergeometric sequences. More specifically, we consider the problem for sequences where the polynomial coefficients split over the field of rationals Q. We show its relation to the values of the Gamma function evaluated at rational points, which allows to establish decidability of the problem under the assumption of the Rohrlich-Lang conjecture. We propose a different approach to the problem based on studying the prime divisors of the sequence, allowing us to establish unconditional decidability of the problem.