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. 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. 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 : 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. 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”. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Algorithmes et structures discrètes Vendredi 13 septembre 2024, 14 heures, Salle 3052 Shuichi Hirahara (National Institute of Informatics, Japan) Planted Clique Conjectures Are Equivalent Planted Clique Conjecture states that no polynomial-time algorithm can find a k-clique in an n-vertex Erdős-Rényi random graph with a k-clique planted for $k << n^{1/2}$. We present the equivalence among many variants of planted clique conjectures, including search versions of a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k-clique problem on incompressible graphs), and decision versions with small and large probabilities. In particular, this equivalence identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k-clique planted with probability $k^2/n$ for any $k \le n^{1/2}$. We show that for *any* k, no polynomial-time algorithm can distinguish these two random graphs with probability significantly larger than $k^2/n$ *if and only if* the planted clique conjecture holds. Joint work with Nobutaka Shimizu. Paper: https://eccc.weizmann.ac.il/report/2024/058/ 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) 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. 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.