Lettre de l'IRIF du 16 juillet 2021

Edito

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 !

Annonces de la direction

  • 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é).

Actualités

  • 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.

Zoom sur ICALP 2021

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.
  • 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 !

Appels d'offres et informations des partenaires

  • 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.