Bienvenue 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. Notion du jour Réseaux Sociaux Suivez nous sur Mastodon, Twitter/X et LinkedIn : Actualités 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. 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. 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. 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. 19.7.2024 Les vacances ont commencé et la science vous manque déjà ? La rediffusion de la conférence d'Omer Reingold est maintenant disponible. Son exposé était intitulé “The multitude of group affiliations: Algorithmic Fairness, Loss Minimization and Outcome Indistinguishability”. 16.7.2024 Giuseppe Castagna, Pierre-Louis Curien et Jean-Jacques Lévy ont tous les trois participé à la rédaction d'un chapitre du nouveau livre “The French School of Programming”. A travers un chapitre, chacun des 13 chercheurs a pu aborder le sujet de son choix autours de la programmation et du génie logiciel. 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 : edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Formath Lundi 16 septembre 2024, 14 heures, 3052 Marc Bezem (University of Bergen, Norway) The Max-Atom Problem applied to Universe Polymorphism in Type Theory We give a short introduction to the Max-Atom Problem and its connection to type theory. Then we generalize to join-semilattices with an inflationary endomorphism and we explain how this generalization can be reformulated with Horn clauses (using an idea of Lorenzen). The key problems connected to universe polymorphism in type theory can now be formulated as loop checking problems and uniform word problems for this kind of lattices. Both can be solved by the computation of least Herbrand models of the corresponding Horn clauses. In the second half of the talk we propose a type theory with explicit universe polymorphism, featuring level-indexed product types and constraint-indexed product types. In this type theory, loop checking and uniform word problems in the above mentioned lattices play a crucial role. Efficiency and complexity issues will briefly be addressed throughout the talk. The research presented here is joint work with many people: Nieuwenhuis, Rodríguez-Carbonell, Coquand, Dybjer, Escardó. Algorithmes et complexité Mardi 17 septembre 2024, 11 heures, Salle 3052 Paul Hermouet (LIP6) Towards Unclonable Cryptography in the Plain Model Properties of quantum mechanics have enabled the emergence of quantum cryptographic protocols achieving important goals which are proven to be impossible classically. Perhaps one of the most striking examples of such protocols are the unclonable primitives, which allows different cryptographic “objects” (such as keys, ciphertexts, signatures, programs, etc.) to be encoded in a quantum state in a manner that permits the “object” to be used but not copied. Recent works have shown how to construct some of these primitives, by using different assumptions and models. In this talk, I will present some of these unclonable primitives, and discuss how to leverage coset states to construct them. I will subsequently elaborate on my recent efforts in constructing two of these primitives - copy-protection for point functions and unclonable encryption - in the plain model. Finally, and if time allows, I will discuss show how to construct coset-state-based primitives in a semi-quantum way, that is without a quantum channel. Based on joint works with Huy Vu and Céline Chevalier: “Semi-quantum Copy-Protection and More” (TCC 2023: https://eprint.iacr.org/2023/244), “Towards Unclonable Cryptography in the Plain Model” (preprint: https://eprint.iacr.org/2023/1825). One world numeration seminar Mardi 17 septembre 2024, 14 heures, Online Simon Kristensen (Aarhus Universitet) On the distribution of sequences of the form $(q_n y)$ The distribution of sequences of the form $(q_n y)$ with $(q_n)$ a sequence of integers and $y$ a real number have attracted quite a bit of attention, for instance due to their relation to inhomogeneous Littlewood type problems. In this talk, we will provide some results on the Lebesgue measure and Hausdorff dimension on the set of points in the unit interval approximated to a certain rate by points from such a sequence. A feature of our approach is that we obtain estimates even in the case when the sequence $(q_n)$ grows rather slowly. This is joint work with Tomas Persson. 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. 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 1007 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.