Skip to Main content
Number of documents

18

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é Paris Cité 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, before taking over as Director of IRIF in 2018. Professor at the Collège de France from 2020 to 2021, holder of the Annual Chair in Informatics and Digital Sciences, he taught quantum algorithms.


Journal articles9 documents

  • Frédéric Magniez, Ashwin Nayak. Quantum Distributed Complexity of Set Disjointness on a Line. ACM Transactions on Computation Theory, ACM, 2022, 14 (1), pp.1-22. ⟨10.1145/3512751⟩. ⟨hal-03752906⟩
  • Frédéric Magniez. Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing. Interstices, INRIA, 2021. ⟨hal-03220265⟩
  • Titouan Carette, Mathieu Laurière, Frédéric Magniez. Extended Learning Graphs for Triangle Finding. Algorithmica, Springer Verlag, 2020, 82 (4), pp.980-1005. ⟨10.1007/s00453-019-00627-z⟩. ⟨hal-02349981⟩
  • Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez. Streaming Communication Protocols. ACM Transactions on Computation Theory, ACM, 2018, 10 (4), pp.1-21. ⟨10.1145/3276748⟩. ⟨hal-02349992⟩
  • Frédéric Magniez, Troy Lee, Miklos Santha. Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. Algorithmica, Springer Verlag, 2017, 77, pp.459-486. ⟨10.1007/s00453-015-0084-9⟩. ⟨hal-03753536⟩
  • Stacey Jeffery, Frédéric Magniez, Ronald de Wolf. Optimal Parallel Quantum Query Algorithms. Algorithmica, Springer Verlag, 2017, 79 (2), pp.509-529. ⟨10.1007/s00453-016-0206-z⟩. ⟨hal-03752908⟩
  • Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, et al.. Improved bounds for the randomized decision tree Complexity of recursive majority. Random Structures & Algorithms, 2016, 48 (3), pp.612-638. ⟨10.1002/rsa.20598⟩. ⟨hal-03752910⟩
  • Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez. Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. Algorithmica, Springer Verlag, 2016, 76 (1), pp.1-16. ⟨10.1007/s00453-015-9985-x⟩. ⟨hal-03753527⟩
  • Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland. Quantum Walks Can Find a Marked Element on Any Graph. Algorithmica, Springer Verlag, 2016, 74 (2), pp.851-907. ⟨10.1007/s00453-015-9979-8⟩. ⟨hal-03752911⟩

Conference papers8 documents

  • Yassine Hamoudi, Frédéric Magniez. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, Jul 2021, Riga, Latvia. ⟨10.4230/LIPIcs.TQC.2021.1⟩. ⟨hal-03024755⟩
  • Taisuke Izumi, François Le Gall, Frédéric Magniez. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Mar 2020, Montpellier, France. pp.23:1--23:13, ⟨10.4230/LIPIcs.STACS.2020.23⟩. ⟨hal-02349998⟩
  • Frédéric Magniez, Ashwin Nayak. Quantum Distributed Complexity of Set Disjointness on a Line. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Jul 2020, Saarbrücken, Germany. pp.82:1--82:18, ⟨10.4230/LIPIcs.ICALP.2020.82⟩. ⟨hal-03024619⟩
  • Yassine Hamoudi, Frédéric Magniez. Quantum Chebyshev's Inequality and Applications. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Jul 2019, Patras, Greece. ⟨10.4230/LIPIcs.ICALP.2019.69⟩. ⟨hal-02349991⟩
  • François Le Gall, Frédéric Magniez. Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. 22nd Annual Conference on Quantum Information Processing (QIP 2019), Jan 2019, Boulder, United States. ⟨hal-02351393⟩
  • François Le Gall, Frédéric Magniez. Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018), Jul 2018, Egham, France. pp.337-346, ⟨10.1145/3212734.3212744⟩. ⟨hal-02349996⟩
  • Eldar Fischer, Frédéric Magniez, Tatiana Starikovskaya. Improved bounds for testing Dyck languages. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), Jan 2018, New Orleans, United States. ⟨10.1137/1.9781611975031.100⟩. ⟨hal-02349997⟩
  • Frédéric Magniez, Varun Kanade, Nikos Leonardos. Stable Matching with Evolving Preferences. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016, Paris, France. ⟨10.4230/LIPIcs.APPROX-RANDOM.2016.36⟩. ⟨hal-03753551⟩

Books1 document

  • Frédéric Magniez. Algorithmes quantiques: Quand la physique quantique défie la thèse de Church-Turing. Collège de France / Fayard, 2021, Leçons inaugurales du Collège de France, 978-2-213-72130-9. ⟨hal-03753516⟩