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 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. 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. 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”. 9.7.2024 Thomas Ehrhard est invité en tant qu'orateur à la 28ème rencontre de logique l'AILA qui aura lieu à Udine (Italie) du 3 au 6 septembre 2024. 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 : 11.7.2024 Notez la date du 16 septembre dans votre agenda. La Journée des Probabilités en Informatique Théorique se prépare ! 7 conférenciers invités couvriront un large éventail de domaines liés à l'informatique théorique et aux probabilités, notamment quantique, cryptographie, algorithmes, et plus encore. Pour nous rejoindre, inscrivez-vous (gratuit mais obligatoire) ici : 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 complexité Mardi 10 septembre 2024, 11 heures, Salle 3052 Ashwin Nayak (IQC, University of Waterloo) State distinguishability and learning A basic problem in quantum communication is that of recovering classical information encoded in quantum states. Several problems in learning theory may naturally be cast into this form. We will describe some problems of this nature, specifically the coupon collector problem and its variants. We will present more efficient algorithms as well as lower bounds for these problems, along with implications for learning. Based on work with Shima Bab Hadiashar and Pulkit Sinha. 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) Non encore annoncé. 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. Algorithmes et complexité Mercredi 25 septembre 2024, 11 heures, Salle 3052 Sanjeev Khanna (University of Pennsylvania) 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.