image/svg+xml Welcome IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, also hosting two Inria project-teams. The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences. IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), five are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences. More People Contact Follow @IRIF_Paris Notion of the day News 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. 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. 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. 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. 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. 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. 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. 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. edit all the past news (These news are displayed using a randomized-priority ranking.) Events Graphs Tuesday September 22, 2020, 3PM, Salle 3052 Rongxing Xu Multiple list colouring of $3$-choice critical graphs A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in 1998. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. It is true if $G=\Theta_{2,2,2,2}$, which was proved by Voigt and Tuza in 1996. However, this conjecture was disproved by Meng, Puleo, and Zhu in 2017. They showed that if $G=\Theta_{r,s,t}$ where $r,s,t$ have the same parity and $\min\{r,s,t\} \ge 3$, or $G=\Theta_{2,2,2,2p}$ with $p \ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo, and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.