Institut de Recherche en Informatique Fondamentale (IRIF)


image/svg+xml

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui héberge deux équipes-projets 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), cinq 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.

PARIS REGION

21.9.2020
Via DIMs of Math and Infos, IRIF is one of the lab of the Paris Region Fellowship Program, a project aimed at strengthening the research capacity and international influence of Paris region, attracting excellent researcher and fostering innovation.

Mikael Rabie

15.9.2020
IRIF has the great pleasure to welcome a new associate professor (Université de Paris): Mikael Rabie, an expert in Distributed Computing, in particular on population protocols and distributed models on graphs.

Thomas Vidick

18.8.2020
IRIF is very pleased to host for 12 months starting in September 2020, Thomas Vidick, professor of computer science and mathematics at the California Institute of Technology. His research is at the interface of theoretical computer science, quantum information and cryptography. The invitation is funded by an FSMP chair together with DIENS, Inria and IRIF. Meet him in office 4024.

Thomas Vidick

11.9.2020
Thomas Vidick will give a series of lectures on Interactive proofs with quantum devices during his stay at IRIF funded by an FSMP chair, starting on Sep. 22 at IHP.

perso-delia-kesner.jpeg

28.8.2020
Delia Kesner (IRIF) will be on the panel of a debate on the future of the conference system in theoretical computer science, and organized as a special event as part of the Online Worldwide Seminar on Logic and Semantics (OWLS). The event will take place September 2, 5pm on Zoom.

Numeration - OWNS

1.9.2020
The One World Numeration Seminar is an international online seminar on numeration systems and related topics organised by Wolfgang Steiner (IRIF). It has been well accepted by the community, and the second season starts with a talk by Bill Mance on September 1st.

Baptiste Louf

4.9.2020
Baptiste Louf (just graduated from IRIF) has a paper co-authored with Thomas Budzinski published in Inventiones Mathematicae that proves a conjecture of Benjamini & Curien in discrete random geometry.

Sylvain Schmitz

22.6.2020
Sylvain Schmitz (IRIF) co-organizes the 14th International Conference on Reachability Problems (RP'20), that is planned to take place either online or at IRIF on October 19-20.


(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

Algorithmes et complexité
Jeudi 1 octobre 2020, 14 heures, Salle 3052
Vera Traub (University of Bonn) An improved approximation algorithm for ATSP

In a recent breakthrough, Svensson, Tarnawski, and Végh gave the first constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). In this work we revisit their algorithm. While following their overall framework, we improve on each part of it.

Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. Moreover, we show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio.

Overall we improve the approximation ratio from 506 to 22 + ε for any ε > 0. We also improve the upper bound on the integrality ratio of the standard LP relaxation from 319 to 22.

This is joint work with Jens Vygen.

Live webcast of IGAFIT Algorithmic Colloquium