Frédéric Magniez

CNRS Research Director at IRIF

Director of IRIF for 2018-22
Professor at Collège de France for 2020-21



 

About me

I have been a CNRS researcher since 2000. My research focuses on the design of algorithms, whether randomized or quantum, as well as the study of their limitations. I was also professor at the École Polytechnique from 2003 to 2015, deputy director of the Fondation des Sciences Mathématiques de Paris from 2015 to 2018, professor at the Collège de France from 2020 to 2021 to teach quantum algorithms, and director of the Institut de Recherche en Informatique Fondamentale from 2018 to 2022.

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 algorithmics and 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 until 2022. 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.

Research

Topics Groups Current research projects

Collège de France

Quantum algorithms (Annual Chair 2020-21, in French) Related but independent event
Main lectures Research schools
Responsibilities Steering committees Editorial committee Program committees Main grants

Publications

External sources

Books
2021
[1]Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing (), Collège de France / Fayard, . [url]
Journal articles
2023
[28]Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs ( and ), In ACM Transactions on Computation Theory, volume 15, . [pdf] [doi]
2022
[27]Quantum Distributed Complexity of Set Disjointness on a Line ( and ), In ACM Transactions on Computation Theory, volume 14, . [pdf] [doi]
2020
[26]Extended Learning Graphs for Triangle Finding (, and ), In Algorithmica, volume 82, . [pdf] [doi]
2018
[25]Streaming Communication Protocols (, and ), In ACM Transactions on Computation Theory, volume 10, . [pdf] [doi]
2017
[24]Improved quantum query algorithms for triangle finding and associativity testing (, and ), In Algorithmica, volume 77, . [pdf] [doi]
[23]Optimal parallel quantum query algorithms (, and ), In Algorithmica, volume 79, . [pdf] [doi]
2016
[22]Improved bounds for the randomized decision tree complexity of recursive majority (, , , , and ), In Random Structures & Algorithms, volume 48, . [pdf] [doi]
[21]Quantum walks can find a marked element on any graph (, , and ), In Algorithmica, volume 74, . [pdf] [doi]
[20]Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision (, , and ), In Algorithmica, volume 76, . [pdf] [doi]
2014
[19]Recognizing well-parenthesized expressions in the streaming model (, and ), In SIAM Journal on Computing, volume 43, . [pdf]
[18]Hidden translation and orbit coset in quantum computing (, , , and ), In SIAM Journal on Computing, volume 43, . [pdf]
2013
[17]Validating XML documents in the streaming model with external memory ( and ), In ACM Transactions on Database Systems, volume 38, , Special issue of ICDT'12. [pdf]
2012
[16]On the hitting times of quantum versus random walks (, , and ), In Algorithmica, volume 63, . [pdf]
[15]A learning graph based quantum query algorithm for finding constant-size subgraphs (, and ), In Chicago Journal of Theoretical Computer Science, . [pdf]
2011
[14]Search via quantum walk (, , and ), In SIAM Journal on Computing, volume 40, . [pdf]
2010
[13]Strong no-go theorem for gaussian quantum bit commitment (, , and ), In Physical Review A, volume 81, . [pdf]
[12]Approximate satisfiability and equivalence (, and ), In SIAM Journal on Computing, volume 39, . [pdf]
2009
[11]Quantum testers for hidden group properties (, , and ), In Fundamenta Matematicae, volume 91, , Special issue on Machines on Computations and Universality. [pdf]
2008
[10]Lower bounds for randomized and quantum query complexity using Kolmogorov arguments ( and ), In SIAM Journal on Computing, volume 38, . [pdf]
2007
[9]Quantum algorithms for the triangle problem (, and ), In SIAM Journal on Computing, volume 37, . [pdf]
[8]Property testing of regular tree languages ( and ), In Algorithmica, volume 49, . [pdf]
[7]Quantum complexity of testing group commutativity ( and ), In Algorithmica, volume 48, . [pdf]
[6]Probabilistic abstraction for model checking: An approach based on property testing (, , , and ), In ACM Transactions on Computational Logic, volume 8, . [pdf]
[5]Self-testing of universal and fault-tolerant sets of quantum gates (, , and ), In SIAM Journal on Computing, volume 37, . [pdf]
2005
[4]Multi-linearity self-testing with relative error (), In Theory of Computing Systems, volume 38, . [pdf]
[3]Quantum algorithms for element distinctness (, , , , , and ), In SIAM Journal on Computing, volume 34, . [pdf]
2003
[2]Approximate testing with error relative to input size (, and ), In Journal of Computer and System Sciences, volume 66, . [pdf]
[1]Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem (, and ), In International Journal of Foundations of Computer Science, volume 14, . [pdf]
Conference papers
2021
[39]Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs ( and ), In Proceedings of 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, , TQC Outstanding Paper Prize. [pdf] [doi]
2020
[38]Quantum Distributed Complexity of Set Disjointness on a Line ( and ), In Proceedings of 47th International Colloquium on Automata, Languages and Programming, , 82:1–82:18. [pdf] [doi]
[37]Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model (, and ), In Proceedings of 37th International Symposium on Theoretical Aspects of Computer Science, , Also presented at TQC'20. [pdf] [doi]
2019
[36]Quantum Chebyshev's Inequality and Applications ( and ), In Proceedings of 46th International Colloquium on Automata, Languages and Programming, . [pdf] [doi]
2018
[35]Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks ( and ), In Proceedings of 37th ACM Symposium on Principles of Distributed Computing, , Also presented at QIP'19 as a contributed talk. [pdf] [doi]
[34]Improved bounds for testing Dyck languages (, and ), In Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms, . [pdf] [doi]
2017
[33]Extended Learning Graphs for Triangle Finding (, and ), In Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science, . [pdf] [doi]
[32]Streaming Communication Protocols (, and ), In Proceedings of 44th International Colloquium on Automata, Languages, and Programming, . [pdf] [doi]
2016
[31]Stable Matching with Evolving Preferences (, and ), In Proceedings of 20th International Workshop on Randomization and Computation, . [pdf] [doi]
[30]Streaming Property Testing of Visibly Pushdown Languages (, , and ), In Proceedings of 24rd European Symposium on Algorithms, . [pdf] [doi]
2014
[29]Optimal parallel quantum query algorithms (, and ), In Proceedings of 22nd European Symposium on Algorithms, . [pdf]
[28]Unidirectional Input/Output Streaming Complexity of Reversal and Sorting (, and ), In Proceedings of 18th International Workshop on Randomization and Computation, . [pdf]
2013
[27]Improved quantum query algorithms for triangle finding and associativity testing (, and ), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, , Also presented at QIP'13 as a contributed talk. [pdf]
[26]Nested quantum walks with quantum data structures (, and ), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, , Also presented at QIP'14 as a contributed talk. [pdf]
[25]Streaming complexity of checking priority queues ( and ), In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, . [pdf]
[24]Time-Efficient Quantum Walks for 3-Distinctness (, , , and ), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, , Also presented at QIP'14 as a contributed talk. [pdf]
2012
[23]Maximum matching in semi-streaming with few passes (, and ), In Proceedings of 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, . [pdf]
[22]Validating XML documents in the streaming model with external memory ( and ), In Proceedings of 15th International Conference on Database Theory, , Best Newcomer Paper. [pdf]
[21]Improving quantum query complexity of boolean matrix multiplication using graph collision (, and ), In Proceedings of 39th International Colloquium on Automata, Languages and Programming, . [pdf]
2011
[20]The complexity of approximate Nash equilibrium in congestion games with negative delays (, , and ), In Proceedings of 7th Workshop on Internet & Network Economics, . [pdf]
[19]Improved bounds for the randomized decision tree complexity of recursive majority (, , and ), In Proceedings of 38th International Colloquium on Automata, Languages and Programming, . [pdf]
2010
[18]Recognizing well-parenthesized expressions in the streaming model (, and ), In Proceedings of 42nd ACM Symposium on Theory of Computing, . [pdf]
[17]Finding is as easy as detecting for quantum walks (, , and ), In Proceedings of 37th International Colloquium on Automata, Languages and Programming, , Also presented at QIP'11 as a featured talk. [pdf]
2009
[16]On the hitting times of quantum versus random walks (, , and ), In Proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms, . [pdf]
2007
[15]Search via quantum walk (, , and ), In Proceedings of 39th ACM Symposium on Theory of Computing, , Also presented at QIP'07 as a contributed talk. [pdf]
2006
[14]Self-testing of quantum circuits (, , and ), In Proceedings of 33rd International Colloquium on Automata, Languages and Programming, , Also presented at QIP'06 as a contributed talk. [pdf]
[13]Approximate satisfiability and equivalence (, and ), In Proceedings of 21st IEEE Symposium on Logic in Computer Science, . [pdf]
2005
[12]Quantum algorithms for the triangle problem (, and ), In Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms, , Also presented at QIP'04 as an invited talk. [pdf]
[11]Quantum complexity of testing group commutativity ( and ), In Proceedings of 32nd International Colloquium on Automata, Languages and Programming, . [pdf]
2004
[10]Property testing of regular tree languages ( and ), In Proceedings of 31st International Colloquium on Automata, Languages and Programming, . [pdf]
[9]Lower bounds for randomized and quantum query complexity using Kolmogorov arguments ( and ), In Proceedings of 19th IEEE Conference on Computational Complexity, . [pdf]
2003
[8]Quantum testers for hidden group properties (, , and ), In Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, . [pdf]
[7]Hidden translation and orbit coset in quantum computing (, , , and ), In Proceedings of 35th ACM Symposium on Theory of Computing, , Also presented at QIP'03 as an invited talk. [pdf]
2002
[6]Probabilistic abstraction for model checking: An approach based on property testing (, , , and ), In Proceedings of 17th IEEE Symposium on Logic in Computer Science, . [pdf]
2001
[5]Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem (, and ), In Proceedings of 13th ACM Symposium on Parallelism in Algorithms and Architectures, . [pdf]
[4]Quantum algorithms for element distinctness (, , , , , and ), In Proceedings of 15th IEEE Conference on Computational Complexity, . [pdf]
2000
[3]Multi-linearity self-testing with relative error (), In Proceedings of 17th Symposium on Theoretical Aspects of Computer Science, . [pdf]
[2]Self-testing of universal and fault-tolerant sets of quantum gates (, , and ), In Proceedings of 32nd ACM Symposium on Theory of Computing, . [pdf]
1999
[1]Approximate testing with relative error (, and ), In Proceedings of 31st ACM Symposium on Theory of Computing, . [pdf]
Other publications
2015
[8]La physique quantique réinvente les algorithmes ( and ), Chapter in La Recherche, volume 501, .
2014
[7]Complexité de communication (, and ), Chapter in Informatique Mathématique - Une photographie en 2014, Presses Universitaires de Perpignan, . [pdf]
2013
[6]Some approximations in Model Checking and Testing (, , and ), Technical report arXiv:1304.5199, arXiv.org, , Survey. [pdf]
2009
[5]Special issue in Quantum Computation, Algorithmica 55(3) ( and ), Springer, .
2007
[4]Vérification approchée - Calcul quantique (), Habilitation, Université Paris-Sud, France, , Record number 1018. [pdf]
2006
[3]Comment calculer quantique (, and ), Chapter in La Recherche, volume 398, . [pdf]
2000
[2]Auto-test pour les calculs approché et quantique (), PhD thesis, Université Paris-Sud, France, , Record number 6076. [pdf]
[1]Exact and approximate testing/correcting of algebraic functions: A survey (, and ), Chapter in Proceedings of 1st Summer School on Theoretical Aspects of Computer Science, , Also ECCC Report TR01-014. [pdf]

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.

PhD Thesis Master Thesis and Internship
PhD Theses Master Theses Internships (Licence 3 / Master 1)

Contact

Email

Phone

Office