Bienvenue 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), 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 Twitter/X et LinkedIn pour suivre toute notre actualité : Actualités 14.9.2023 Après avoir eux-mêmes suivis la Fresque du Climat, des membres du laboratoire de l'IRIF formeront, en tant que facilitateurs, des élèves de L1 à la Fresque du Numérique vendredi 15 septembre. Cet atelier permet de comprendre en équipe et de manière ludique les enjeux environnementaux du numérique. 6.9.2023 L'IRIF est très fier d'annoncer que Geoffroy Couteau, chargé de recherche du CNRS, a obtenu un financement pour son projet ERC Starting Grant : “Overcoming Barriers and Efficiency Limitations in Secure Computation”. Pour en savoir plus sur son projet et ses ambitions : 5.9.2023 Toutes nos félicitations à Amélie Gheerbrant, maîtresse de Conférences, qui vient d'être nommée Vice-Doyenne (VD) Vies des campus et Vie étudiante au sein de l'Université Paris Cité ! 11.9.2023 Congratulations to Mohammed Foughali, who has published a paper titled “Compositional Verification of Embedded Real-Time Systems”, alongside Pierre-Emmanuel Hladik from Nantes Université/LS2N and Alexander Zuepke from the Technical University of Munich in the Journal of Systems Architecture. You can access the article here: 11.9.2023 IRIF is back to school! Today, we are welcoming our 12 new permanent members to our laboratory. As part of this day, they will present their research topics to us. edit toutes les anciennes actualités (Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.) Agenda Algorithmique distribuée et graphes Mardi 26 septembre 2023, 15 heures 30, 3052 Sophie Germain Binh-Minh Bui-Xuan (CNRS, LIP6, UPMC) Efficient algorithms using temporality and geometry on graphs. In graph theory, a dynamic network can be understood as a global underlying graph whose edges are allowed to become temporarily unavailable at times. Extending Courcelle-like meta theorems to such a temporal setting is an important and challenging open question. Without the consideration of temporality, a good number of width parameters has been introduced in the effort to better understand what lies between cliquewidth (number of different neighbourhoods) and treewidth (total size of neighbourhoods). We can cite rankwidth, bimodule-width, booleanwidth, and matching-width for the first category; and minor-based parameters such as Hajos/Hadwiger number and twinwidth for the second one. However, attempts in extending those parameters to temporal graphs are still scarce in the literature. Twins in a temporal context would refer to vertices which are substitutes for each other in the solution of a number of classical graph problems, e.g. matching, epidemic spreading, journeys of optimal (temporal) length, and so on. Although most of these problems become NP-hard to optimise on an arbitrary input, we present in this talk an example where reducing a spatiotemporal input into a timeless graph and using both geometric and decomposition properties help in obtaining a PTAS solution. We hope this kind of technique could help in solving problems beyond first order logic when exploiting the conformist nature of twins. Algorithmes et complexité Mercredi 27 septembre 2023, 11 heures, Salle 3052 Oded Regev (NYU Courant) An Efficient Quantum Factoring Algorithm We show that n-bit integers can be factorized by independently running a quantum circuit with $\tilde{O}(n^{3/2})$ gates for $\sqrt{n}+4$ times, and then using polynomial-time classical post-processing. In contrast, Shor's algorithm requires circuits with $\tilde{O}(n^2)$ gates. The correctness of our algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice. No background in quantum computation will be assumed. Based on the recent arXiv preprint: https://arxiv.org/abs/2308.06572 Combinatoire énumérative et analytique Jeudi 28 septembre 2023, 14 heures, IHP Vincent Bonzom Et Cédric Boutillier Séminaire Flajolet à l'IHP https://semflajolet.math.cnrs.fr/ Exceptionnellement à 14 heures. Preuves, programmes et systèmes Jeudi 28 septembre 2023, 10 heures 30, Lyon Antoine Allioux, Liseau Blondeau-Patissier, William Simmons Séminaire CHOCOLA Titles and abstracts available at: https://chocola.ens-lyon.fr/events/meeting-2023-09-28/ Séminaire des membres non-permanents Jeudi 28 septembre 2023, 16 heures, Salle 3052 Emily Clement Layered controller synthesis for dynamic multi-agent systems We present a layered approach to solve a multi-agent control problem. This methods mixes three domains: timed automata, SMT and reinforcement learning, in order to obtain the best of each: the method based on timed automata solves the combinatorial aspect of the problem, the SMT refine our model into a more realistic one and the two methods are combined into a SWA-SMT solver. Finally, the Reinforcment Learning trains the policy in order to show that the initial dataset generated with the the SWA-SMT solver is crucial for the overall success of the method. La syntaxe rencontre la sémantique Jeudi 28 septembre 2023, 14 heures, Salle 3052 Beniamino Accattoli (INRIA Saclay) Closure Conversion and Abstract Machines Closure conversion is a program transformation at work in compilers for functional languages to turn inner functions into global ones, by building 'closures' pairing the transformed functions with the 'environment' of their free variables. Abstract machines rely on similar and yet different concepts of 'closures' and 'environments'. In this talk, we analyze the relationship between the two approaches. We adopt a very simple lambda-calculus with tuples as source language and study abstract machines for both the source language and the target of closure conversion. We overview three contributions. Firstly, a new simple proof technique for the correctness of closure conversion, inspired by abstract machines. Secondly, we show how the closure invariants of the target language allow us to design a new way of handling environments in abstract machines, not suffering the shortcomings of other styles. Thirdly, we analyze the machines from the point of view of sharing and time complexity, dissecting how different aspects of closure conversion impact on the cost of the execution. Automates Vendredi 29 septembre 2023, 14 heures, Salle 3052 Alexander Rabinovich (Tel-Aviv University) The Church Synthesis Problem Over Continuous Time Church’s Problem asks for the construction of a procedure which, given a logical specification φ(I, O) between input ω-strings I and output ω-strings O, determines whether there exists an operator F that implements the specification in the sense that φ(I, F(I)) holds for all inputs I. Büchi and Landweber gave a procedure to solve Church’s problem for MSO specifications and operators computable by finite-state automata. We investigate a generalization of the Church synthesis problem to the continuous time of the non-negative reals. It turns out that in the continuous time there are phenomena which are very different from the canonical discrete time domain of the natural numbers. Combinatoire énumérative et analytique Mardi 3 octobre 2023, 11 heures, Salle 1007 Éric Fusy (CNRS & LIGM, Université Gustave Eiffel) Énumération de rectangulations Je présenterai des résultats sur l'énumération exacte et asymptotique de rectangulations génériques (partitions d'un rectangle en régions rectangulaires, sans point où 4 rectangles se rencontrent, et considérées selon deux relations d'équivalences, faible ou forte). Ces objets sont en correspondance avec certains modèles de cartes planaires orientées (orientations bipolaires dans le cas faible, structures transverses dans le cas fort), qui peuvent être encodées par certains chemins dans le quart de plan en appliquant une bijection due à Kenyon, Miller, Sheffield et Wilson. Je montrerai également une extension au cas de rectangulations non génériques, donnant un continuum de modèles de cartes planaires aléatoires qui s'approchent asymptotiquement du réseau régulier. Travaux en commun avec Erkan Narmanli et Gilles Schaeffer Algorithmes et complexité Mardi 3 octobre 2023, 11 heures, Salle 3052 Marcos Kiwi (Universidad de Chile) Label propagation on binomial random graphs We study a variant of the widely popular, fast, and often used family of community detection procedures referred to as label propagation algorithms. These mechanisms also exhibit many parallels with models of opinion exchange dynamics and consensus mechanisms in distributed computing. Initially, given a network, each vertex starts with a random label in the interval [0,1]. Then, in each round of the algorithm, every vertex switches its label to the majority label in its neighborhood (including its own label). At the first round, ties are broken towards smaller labels, while at each of the next rounds, ties are broken uniformly at random. We investigate the performance of this algorithm on the binomial random graph G(n,p). Via a technically delicate analysis, we show that for np>n^(5/8+epsilon), the algorithm terminates with a single label a.a.s. Moreover, we show that if np = omega(n^(2/3)), a.a.s., this label is the smallest one, whereas if n^(5/8+epsilon) < np = o(n^(2/3)), the surviving label is, a.a.s., not the smallest one. Joint work with Lyuben Lichev (Univ. Jean Monnet), Dieter Mitsche (Univ. Jean Monnet & Pontifícia Univ. Católica de Chile), and Pawel Pralat (Toronto Metropolitan Univ.). One world numeration seminar Mardi 3 octobre 2023, 14 heures, Online Manfred Madritsch (Université de Lorraine) Construction of absolutely normal numbers Let $b\geq2$ be a positive integer. Then every real number $x\in[0,1]$ admits a $b$-adic representation with digits $a_k$. We call the real $x$ simply normal to base $b$ if every digit $d\in\{0,1,\dots,b-1\}$ occurs with the same frequency in the $b$-ary representation. Furthermore we call $x$ normal to base $b$, if it is simply normal with respect to $b$, $b^2$, $b^3$, etc. Finally we call $x$ absolutely normal if it is normal with respect to all bases $b\geq2$. In the present talk we want to generalize this notion to normality in measure preserving systems like $\beta$-expansions and continued fraction expansions. Then we show constructions of numbers that are (absolutely) normal with respect to several different expansions.