Cette semaine, nouvelles arrivées à la rentrée et un rappel sur l'accès au bâtiment durant la fermeture estivale. Nous rappelons que la conférence ICALP commence la semaine prochaine avec les workshops le 4 juillet.

Du côté de nos partenaires, notez la session d'information Postdoctoral Fellowships 2022 proposée par Université Paris Cité.

Un focus sur un extrait d’article de QuantaMagazine intitulé ‘Absurdly Fast’ Algorithm for Network Flow .

Bonne lecture !

• Nouvelles arrivées à la rentrée : 3 nouveaux membres permanents de l’IRIF vont nous rejoindre à la rentrée. Ils nous présenterons leur recherche lors de la journée de rentrée de l’IRIF.
  • Marie Albenque, Directrice de Recherche CNRS dans l’équipe Combinatoire
  • Sylvain Douteau, Maître de Conférences UPC (à l’UFR de Mathématiques) dans l’équipe Algèbre et calcul
  • Marie Fortin, Chargée de Recherche CNRS dans l’équipe Automates et applications

• [Rappel] Accès bâtiment du mardi 26 juillet au lundi 15 août (inclus)
  • Fermeture totale : mardi 26 juillet (coupure des postes électriques), lundi 15 août (jour férié), week-end
  • Accès normal : mercredi 27 juillet
  • Sur demande motivée pour tous les membres de l'IRIF : du jeudi 28 juillet au vendredi 12 août (hors week-end). Durant cette période, les badges d'accès au bâtiment seront désactivés, pour réactiver votre badge, renseigner au plus tard le 8 juillet ce tableau. Pour les stagiaires, la demande doit être validée par l'encadrant qui doit être présent.

• [Rappel] Fermeture été
  • Services de l'Université fermés du jeudi 28 juillet au lundi 15 août (inclus) : les recrutements doivent être lancés au moins une semaine avant !
  • Les services de l'IRIF resteront ouverts, mais restreints : certains actes de gestion ne seront pas possibles

• ICALP 2022, July 4-8
  • 9 workshops: on July 4 at Campus Saint-Germain-des-Prés of Université Paris Cité. More informations about the workshops.
  • Conference ICALP: July 5-8 at la Halle aux Farines of Université Paris Cité. Programme and infos.
• The International Congress of Mathematicians 2022 (ICM 2022) will take place between 6 - 14 July 2022 as a virtual event. Free registration for the virtual ICM 2022 is open! There will be TCS talks from amazing scientists and speakers including as Gonthier, Hastings, LeCun, Mossel, Vazirani, Vidick, Wigderson, Williams etc. … More information here.

A team of computer scientists has come up with a dramatically faster algorithm for one of the oldest problems in computer science: maximum flow. The problem asks how much material can flow through a network from a source to a destination if the links in the network have capacity limits.

The new algorithm is “absurdly fast,” said Daniel Spielman of Yale University. “I was actually inclined to believe […] algorithms this good for this problem would not exist.”

Maximum flow has been studied since the 1950s, when it was formulated to study the Soviet railway system. “It’s older than maybe the theory of computer science,” said Edith Cohen of Google Research in Mountain View, California. The problem has many applications: internet data flow, airline scheduling and even matching job applicants to open positions. The new paper handles both maximum flow and a more general version of the problem in which you also want to minimize costs. Over the years, these two problems have inspired many of the biggest advances in algorithmic techniques. “They’re almost why we have a field of algorithms,” Spielman said.

The new algorithm solves these two problems in “almost linear” time, which means that the algorithm’s runtime is roughly proportional to the amount of time it takes merely to write down the details of the network in the first place. No other algorithm for these problems comes close to running this fast for all possible networks. The result made him “jump up and down,” said Satish Rao of the University of California, Berkeley. “It’s amazing.”

Now that we know we can do this really quickly, people will find all sorts of applications for it that they just weren’t thinking of before. Daniel Spielman, Yale University

For now, it’s primarily a theoretical advance, since the speed improvements kick in only for networks that are far larger than the ones we encounter in the real world, for which maximum flow problems can already be solved fairly quickly (at least, if they don’t involve minimizing costs). But pieces of the new algorithm might see practical use within a year, predicted Richard Peng of the University of Waterloo in Canada, one of the algorithm’s six creators. And in the coming years, researchers said, computer scientists will likely find ways to make it more practical and perhaps even slightly faster.

Even if improvements do come along, though, this new paper is the “slam dunk,” said Aleksander Mądry of the Massachusetts Institute of Technology. It’s “essentially the best possible,” he said.

Read the rest of this article on Quanta Magazine.

• Université Paris Cité / Session d'information Postdoctoral Fellowships 2022 : Université Paris Cité propose une formation et un accompagnement dédié dans le cadre de l’appel à projets « Postdoctoral Fellowships 2022 » d’Horizon Europe. Cette formation présentant les modalités de cet appel du programme de financement de la Commission Européenne : Horizon Europe. Celle-ci aura lieu le mardi 5 Juillet 2022 de 10 à 13h. Cette session se tiendra en langue anglaise et sera enregistrée.

Newsletter des partenaires : Les lettres arrivent sporadiquement aux membres de l'IRIF. Elles sont donc listées ci-dessous.

• Newsletter de l'INS2I #10 du 01/07/2022
• CNRS Le Journal [n°69] de juin 2022
• Lettre de l'INSMI du 30/06/2022
• CNRS interne du 30/06/2022