Frédéric Magniez

Biography

Former student of the Ecole Normale Supérieure de Cachan, Frédéric Magniez is graduated both in mathematics (agrégation) and computer science (PhD). His PhD thesis was awarded by the Association Française d’Informatique Théorique in 2000. He then became a CNRS researcher and worked at the Université Paris Sud, before joining the Institut de Recherche en Informatique Fondamentale (IRIF) at the Université de Paris in 2010. His research focuses on the design and analysis of randomized algorithms for processing large data sets, as well as the development of quantum computing, particularly algorithms, cryptography and its interactions with physics.

Professor at the École Polytechnique from 2003 to 2015, Frédéric Magniez co-initiated the first course dedicated to quantum computing of the institution. In 2006, he founded and led the national working group for quantum computing, that currently brings together 20 research groups. From 2013 to 2017, he ran the Algorithms and Complexity group, whose research in quantum computing is recognized worldwide. In 2015, he became Deputy Director of the Fondation des Sciences Mathématiques de Paris, a network of excellence bringing together 1,200 researchers in mathematics and computer science, before taking over as Director of IRIF in 2018. Professor at the Collège de France, he has held the Annual Chair in Informatics and Digital Sciences from 2020 to 2021.

Research

• Quantum computing: algorithms, self-testing, cryptography
• Sublinear algorithms: property testing, streaming algorithms

• Algorithms and Complexity group at IRIF
• Paris Center for Quantum Computing

Collège de France

• Interviews: Collège de France, ENS Paris-Saclay
• Inaugural lecture: Article, Book, Video
• Lectures & Seminars: Presentation, Videos and slides

Teaching

• Parisian Master of Research in Computer Science (2002-)
  • Randomness in Complexity
  • Quantum information and applications
• Ecole Polytechnique (2003-15, archive site)

• Graphs, algorithms and randomness (CIMPA, 2019), Quantum physics and computer science (CNRS, 2014), Communication complexity (GDR IM & CNRS, 2014), Randomized algorithms (EPIT & CNRS, 2012), New computation paradigms (ENS Lyon, 2010), Quantum computing (2009), Computational complexity (EPIT & CNRS, 2005)

Management

• Director of IRIF (2018-)
• Deputy director of Fondation Sciences Mathématiques de Paris (2015-17)
• Leader of Algorithms and Complexity group (2013-17)

• Special issue on Quantum Computation, Algorithmica (2009)

• TQC'22, PODC'22, ICALP'22, HALG'22, ITCS'22, SODA'21, FCT'17, ICALP'17, PQCRYPTO'17, CSR'17, IPDPS'17, ICALP'15, TAMC'15, MFCS'14, SOFSEM'12, STOC'11, STACS'08, FCT'07, QIP'06, SOFSEM'05

• Regional network for computer sciences (2019-)
• CNRS research network for theoretical computer science (2009-17)
• National committee for scientific research (CoNRS, section 06, 2012-16)
• French spring school EPIT (2011-16)

Main grants

• Coordinator: QUDATA (ANR Générique 2019-22), RDAM (ANR Blanc 2013-17), QRAC (ANR Defis 2009-12)
• Participant: AlgoriDAM (ANR Générique 2020-23), CRYQ (ANR JCJC 2010-13)

• Coordinator: HPCQS (EuroHPC 2021-24, local PI for CNRS), IRIF-IQC collaboration on QIP (CNRS PICS 2017-19), CSQIP (EU-Canada TEP 2009-11)
• Participant: PARQ (ERC Advanced 2020-25), QUANTALGO (QuantERA ERA-NET Cofund 2018-21), QALGO (FP7/ICT/FET 2013-16), DIQIP (CHIST-ERA ERA-NET Cofund 2011-14), QCS (FP7/ICT/FET 2010-13)

Students

Postdoc offers

Several openings are available in my group in classical and quantum computing.
For quantum computing, topics of interest include quantum algorithms for massive data, optimization, machine learning and cryptography. In case of interest, there will be also opportunities to collaborate with industrial partners.
For more information, please contacting me or visit the IRIF postdoc call webpage.

PhD/Master Thesis offers

If you woud like to apply for a thesis or an internship under my advising, please read the following intructions before contacting me.

• Read some papers of my recent papers

• Attend some of the Master courses of the group or equivalent ones in other institutions

• Select one of the following topics you would like to work on
• Quantum computing: Introduction
• Streaming algorithms: Survey
• Property testing: Survey

Current and former students

• Dániel Szabó, Property testing, quantum computing and their connection
• Simona Etinski (co-advised with André Chailloux and Anthony Leverrier), Quantum protocols and algorithms
• 2021, Yassine Hamoudi (co-advised with Miklos Santha), Quantum Algorithms for the Monte Carlo Method
• 2021, Yixin Shen, Classical and Quantum Cryptanalysis for Euclidean Lattices and Subset Sums
• 2020, Alessandro Luongo (co-advised with Iordanis Kerenidis, Industrial PhD Thesis (CIFRE) with ATOS), Quantum machine learning algorithms
• 2015, Nathanaël François: Algorithms and Lower Bounds for variants of the Streaming Model
• 2014, Stacey Jeffery (informally co-advised with Michele Mosca): Frameworks for Quantum Algorithms
• 2013, Christian Konrad: Computations on Massive Data Sets: Streaming Algorithms and Two-Party Communication (PhD grant provided by CFM Fondation)
• 2011, Loïck Magnin (co-advised with Nicolas Cerf): Two-player interaction in quantum computing: cryptographic primitives & query complexity
• 2003, Sylvain Peyronnet (partly involved in the advising with Michel de Rougemont): Model checking et vérification probabiliste

• 2021 (M2 MPRI), Maël Luce: Avantage quantique dans le modèle CONGEST du calcul distribué
• 2011 (M2 MPRI), Nathanaël François: Vérification des files de priorité dans le modèle de streaming
• 2010 (U. Waterloo, EU-Canada exchange program), Stacey Jeffery: Collision finding with many classical or quantum processors
• 2008 (M2 MPRI), Omar Fawzi: Couplage maximum dans les modèles de streaming
• 2007 (M2 IF ENS-Lyon), Loïck Magnin: Mise en gage quantique avec des variables continues
• 2006 (M2 MPRI), Basile Couëtoux: Bornes inférieures de fonctions booléennes
• 2003 (DEA DIF ENS-Lyon), Pierre Philipps: Bornes inférieures en calcul quantique: Méthode par adversaire vs. méthode des polynômes
• 2002 (DEA Algo), Ke-Fong Lin: Calcul quantique par évolution adiabatique

• 2015 (MIM1 ENS-Lyon), Titouan Carette : Arbres de décision quantiques
• 2011 (L3 U. Montréal), Cynthia Beauchemin: Arbres de décision probabilistes, approche pratique et théorique
• 2010 (L3 ENS-Cachan), Elisa Rebolini: Alternative au théorème adabatique pour l'algorithme de Grover
• 2006 (MIM1 ENS-Lyon), Omar Fawzi: Primitives cryptographiques quantiques
• 2002 (MIM1 ENS-Lyon), Sylvain Périfel: Autour de la transformée de Fourier quantique
• 2001 (MIM1 ENS-Lyon), Pierre Philipps: Algorithmes de recherche et problème des collisions en calcul quantique