La pause estivale approche, la lettre hebdomadaire s'adaptera en conséquence avec un nouveau rythme et un contenu basé sur les actualités du moment.

A retenir avant de partir en vacances : les dates de fermeture de l'Université de Paris et du secrétariat de l'IRIF et la date du pot de rentrée (7 septembre).

Côté actualités scientifiques, le Hcéres annonce la réalisation d'une Synthèse Nationale des Mathématiques et l'Université de Paris lance l'appel à candidature pour le programme PAUSE.

Et enfin Zoom sur ICALP 2021 où quelques membres de l'IRIF ont présenté des papiers acceptés dans le cadre de cette conférence.

Bonne lecture !

• Fermeture estivale : Le site des Grands Moulins sera fermé du vendredi 23 juillet 2021 au soir au lundi 16 août 2021 au matin.
  • Fermeture du secrétariat de l'IRIF du 2 au 6 août. Activité réduite du 9 au 13 août.
  • Tous les services de l'Université de Paris seront fermés du 26 juillet au 13 août.

• Pot de la rentrée / Save the date : l'UFR d'Informatique et l'IRIF organisent un pot commun pour la rentrée le 7 septembre. Ci-dessous, l'horaire prévisionnel.
  • 10h00 - 12h30 : Présentation des nouveaux membres permanents (personnel en soutien à l'enseignement et à la recherche, chercheurs et enseignants-chercheurs).
  • 12h30 - 13h00 : Buffet
  • 14h00 - 15h00 : Accueil des nouveaux doctorants, post doctorants et ATER.

• Semaine de rentrée L1 informatique : Du 6 au 10 septembre 2021 se tiendra la rentrée des L1 informatique. A cette occasion, des anciens étudiants de L ou de M présenteront des projets réalisés dans le cadre de leurs études. Vous êtes étudiant.e et vous souhaitez faire une présentation ? Vous êtes chercheur.euse / enseignant.e-chercheur.euse et vous avez en tête des étudiant.es qui pourraient être intéressé.es à présenter ? Merci de bien vouloir contacter arnaud.sangnier@irif.fr.

• Stages scolaires d'observation / Appel à manifestation d'intérêt
  • L'IRIF se joint à cette initiative globale de l'Université de Paris. Si vous souhaitez vous associez à ce projet et accueillir des collégiens.ennes dans le cadre de leur stage scolaire d'observation, vous pouvez manifester votre intérêt auprès de cadet@irif.fr en indiquant le nombre d'élèves que vous souhaiteriez accueillir.
  • Nous vous rappelons qu'une page de l'intranet dédiée existe. Si vous voyez des éléments à modifier pour améliorer cette procédure d'accueil, n'hésitez pas à nous les partager.

• Informations salles : Veuillez noter certains changements concernant les salles 4033 et 3055.
• La salle 4033 n'est plus disponible à la réservation car elle est en train d'être transformée en bureau pour les doctorants.
• La salle 3055 sera transformée, pour la rentrée, en bureau pour le nouveau personnel administratif venant rejoindre l'UFR (en charge d'une partie de la scolarité).

• Réalisation d'une Synthèse Nationale des Mathématiques : Le Hcéres lance la réalisation d’une synthèse disciplinaire nationale consacrée aux mathématiques. Valérie Berthé (IRIF) fait partie du comité des 16 personnalités chargées de rédiger un rapport de synthèse sur les mathématiques françaises. Lire le communiqué de presse à ce sujet.

• CCC 2021 : One accepted paper from Miklos Santha (IRIF), Troy Lee, Tongyang Li and Shengyu Zhang will be presented at the annual Computational Complexity Conference July 20–23.
  Let G=(V,w) be a weighted undirected graph with m edges. The cut dimension of G is the dimension of the span of the characteristic vectors of the minimum cuts of G, viewed as vectors in {0,1}m. For every n≥2 we show that the cut dimension of an n-vertex graph is at most 2n−3, and construct graphs realizing this bound. Full article available here.

Toute cette semaine s'est déroulée l'édition 2021 de l'International Colloquium on Automata, Languages, and Programming (ICALP).

5 papiers co-écrits par des membres de l'IRIF ont été présentés dans le cadre de cette conférence. Retour sur les articles.

• Mathieu Mari, Chien-Chung Huang, Claire Mathieu and Jens Vygen. Approximating maximum integral multiflows on bounded genus graphs.
  En combinant des techniques de topologie algorithmique et de programmation linéaire, il est possible de construire un algorithme d’approximation pour un cas — à savoir, quand l’instance peut être plongée sur une surface de genre borné — plus général que précédemment connu, pour le problème classique du multiflot entier : on se donne un ensemble de sommets, un graphe d’arêtes de routage avec capacités, et un ensemble de paires de sommets (les requêtes), et on souhaite satisfaire le maximum de requêtes par des chemins empruntant des arêtes de routage et respectant les capacités.

• Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter and Ronald de Wolf. Quantum algorithms for matrix scaling and matrix balancing.
  Matrix scaling and balancing are two basic linear-algebraic problems (applications include pre-conditioning linear systems). We study the power and limitations of quantum algorithms for these problems, proving matching upper and lower bounds in the poly(1/eps)-regime.

• Antonio Casares, Thomas Colcombet and Nathanaël Fijalkow. Optimal Transformations of Games and Automata using Muller Conditions.
  In this paper, we are interested in automata over infinite words and infinite duration games, that we view as general transition systems. We study transformations of systems using a Muller condition into ones using a parity condition, extending Zielonka's construction. We introduce the alternating cycle decomposition transformation, and we prove a strong optimality result: for any given deterministic Muller automaton, the obtained parity automaton is minimal both in size and number of priorities among those automata admitting a morphism into the original Muller automaton. We give two applications. The first is an improvement in the process of determinisation of Büchi automata into parity automata by Piterman and Schewe. The second is to present characterisations on the possibility of relabelling automata with different acceptance conditions.

• Thomas Colcombet and Arthur Jaquard. A Complexity Approach to Tree Algebras: the Bounded Case.
  In this paper, we initiate a study of the expressive power of tree algebras, and more generally infinitely sorted algebras, based on their asymptotic complexity. We provide a characterization of the expressiveness of tree algebras of bounded complexity.

• Alexandre Goy, Daniela Petrisan and Marc Aiguier. Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces.
  The powerset monad on the category of sets does not distribute over itself. Nevertheless a weaker form of distributive law of the powerset monad over itself exists and it essentially stems from the canonical Egli-Milner extension of the powerset to the category of relations. On the other hand, any regular category yields a category of relations, and some regular categories also possess a powerset-like monad, as is the Vietoris monad on compact Hausdorff spaces. We derive the Egli-Milner extension in three different frameworks : sets, toposes, and compact Hausdorff spaces. We prove that it corresponds to a monotone weak distributive law in each case by showing that the multiplication extends to relations but the unit does not. We provide an application to coalgebraic determinization of alternating automata.

Rendez-vous en 2022 pour les 50 ans de la conférence et de la création de l'EATCS. Nous vous en dirons davantage prochainement !

• Université de Paris / Appel à candidature PAUSE : Le département Internationalisation Pédagogique et Scientifique du Pôle SRI a ouvert l’appel à candidature du programme PAUSE porté par le Collège de France pour la troisième session du calendrier 2021. Ce programme national alloue des financements incitatifs aux universités et aux organismes de recherche non universitaires projetant d’accueillir un.e scientifique ou un.e artiste-enseignant.e en danger contraint.e l’exil. En cas d'intérêt, contactez la direction@irif.fr. Date limite des dossiers de candidatures : 26 août 2021 à 11h00.

• Université de Paris / Fonctionnement estival du Crous de Paris : Le Crous de Paris a organisé son fonctionnement durant la période estivale afin de continuer à accompagner les étudiants parisiens. Une page spécifique pour cette période a été mise en ligne sur le site internet de l'Université de Paris.

• Newsletter des partenaires : Les lettres arrivent sporadiquement aux membres de l'IRIF. Elles sont donc listées ci-dessous.
  • Newsletter étudiante du 02/07/2021
  • Université de Paris Infos du 05/07/2021 avec à la une, une interview croisée de Christine Clerici et Nicolas Jeanjean
  • Gazette du GDRim du 06/07/2021 avec à lire, les entretiens de Marthe Bonamy et Ludovic Patey
  • CNRS Hebdo du 08/07/2021
  • Lettre de l'INSMI du 09/07/2021
  • Lettre n°63 CNRS Le journal avec à la une Jean Dalibard médaille d'or 2021 du CNRS.
  • Fil info Recherche de l'Université de Paris du 12/07/2021 avec une annonce sur la 20e édition du prix Irène Joliot-Curie