Algorithms and complexity

Research interests

The theory of efficient algorithms is the common ground that brings together the research directions we investigate, in both classical computing and quantum computing.

In the area of classical computing, we study the complexity of various problems in several models of computation, designing efficient algorithms and proving lower bounds. The particular fields we study are approximation algorithms, property testing, streaming algorithms, online algorithms, algorithmic game theory, communication complexity, and theoretical cryptography. Many of the problems to be studied in these fields require, or can benefit from, probabilistic approaches.

In quantum computing our goals are to study the power of quantum algorithms, to enhance our understanding of the strength of quantum information for computational tasks, cryptography and interaction, and to explore the relation between classical and quantum communication complexity.

The flow of ideas and techniques between quantum and randomized computing, in the two directions, is an important characteristic of some of the research within our group.

In 2014, we co-founded the Paris Centre for Quantum Computing (PCQC) in Paris, France. PCQC brings together computer scientists, theoretical & experimental physicists and mathematicians that work in and around Paris.

National and international networks


We are seeking excellent candidates for permanent and postdoctoral positions in classical and quantum computing. We are also happy to welcome motivated and strong students to pursue a PhD or a Master thesis in our group.

Topics of interest include (but are not limited to): algorithms, online algorithms, streaming algorithms, approximation algorithms, communication complexity, cryptography, computational game theory, quantum computing, computational applications of logic, randomness in computing, privacy.

Further information may be obtained from any of the permanent members of the group.

Permanent positions

Every year, the CNRS (French National Center for Scientifc Research) has job openings, including some openings for researchers in Computer Science. The application deadline is usually in early January. Details are available on the CNRS website.

Faculty positions at the Université Paris Diderot may also be available. The application deadline is usually in March. Details are available on the University website.

For those interested in applying to such positions in order to join our group, we recommend to contact one of the permanent members at least two months before the deadline in order to discuss the possibilities and the application process.

Postdoctoral positions

Starting dates are usually in September but can be negotiated. To apply please send a CV, a summary of research and names of at least three references to Applications should be received by November 15th.

The position(s) will be financed either by group resources, or via joint applications of the candidate and the group to external funding sources.

PhD and Master Theses

For PhD applicants, please contact one of the permanent members no later than spring, since scholarships are allocated just before summer.

For Master internships, please contact permanent members individually with your CV, transcripts and a description of your research interests, at least three months before the start of the internship.


We actively participate in teaching algorithms, complexity and quantum computing at the undergraduate and masters level. In the Paris Computer Science Master's Programme (MPRI) we are currently involved in the following courses: Randomness in Complexity (short, long), Quantum information and applications, and Quantum Cryptography.


Boczkowski Lucas 4055 Doctorant.e Mail
Bredariol-Grilo Alex 4059 Doctorant.e Mail
Collet Simon 4001 Doctorant.e Mail
De-Rougemont Michel 01 57 27 94 48 4041 Professeur.e Mail
Feuilloley Laurent 4001 Doctorant.e Mail
Fraigniaud Pierre 01 57 27 92 60 4016 Directeur.rice de recherche - CNRS Mail
Guinard Brieuc 4060 Doctorant.e Mail
Hamoudi Yassine 4031 Doctorant.e Mail
KUMAR Niraj Doctorant.e Mail
Kempe Julia Directeur.rice de recherche - CNRS (en disponibilité) Mail
Kerenidis Iordanis 4025 Directeur.rice de recherche - CNRS Mail
Korman Amos 01 57 27 94 06 4028 Chargé.e de recherche Mail
Laplante Sophie 01 57 27 94 47 4040a Professeur.e Mail
Luongo Alessandro Doctorant.e Mail
Magniez Frédéric 01 57 27 94 02 4019 Directeur.rice de recherche Mail
Mathieu Claire 4009 Membre associé.e - DR CNRS Mail
Nolin Alexandre 4055 Doctorant.e - Moniteur Mail
Paz Ami Post-Doctorant.e Mail
Pitalua Garcia Damian Post-Doctorant.e Mail
Rosén Adi 01 57 27 94 40 4013 Directeur.rice de recherche - CNRS Mail
Santha Miklos 01 57 27 94 03 4024 Directeur.rice de recherche Mail
Shen Yixin Doctorant.e Mail
Urrutia Florent 4057 Doctorant.e Mail
Vimont Guillaume Doctorant.e Mail
Xiao David Chargé.e de recherche - CNRS (en disponibilité) Mail

Group calendars