FM
Frédéric Magniez
quant-phcs.DScs.CCcs.DCcs.CRcs.GTcs.DBcs.LOcs.SEstat.CO
On Valency
published · living versionsW_5u3wmuhv·v1 · currentpublished
Quantum Query Lower Bounds from Classical Moment Matching
with Chandrima Kayal, Sayantan Sen, Dániel Szabó
1 version
Preprints & journals
38 papers in the corpus · 2000–2026Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry2609.10808v2 · Fr'ed'eric Magniez, Sebastian Zur2026 · 0 citationsarXiv
No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles2607.04852v2 · Pierre Fraigniaud, Fr'ed'eric Magniez, Isabella Ziccardi2026 · 0 citationsarXiv
Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model2602.15529v2 · Fabien Dufoulon, Fr'ed'eric Magniez, Gopal Pandurangan2026 · 0 citationsarXiv
Quantum Communication Advantage for Leader Election and Agreement2502.07416v1 · Fabien Dufoulon, Fr'ed'eric Magniez, Gopal Pandurangan2025 · 1 citationarXiv
Deterministic Even-Cycle Detection in Broadcast CONGEST2412.11195v3 · Pierre Fraigniaud, Mael Luce, Fr'ed'eric Magniez et al.2024 · 0 citationsarXiv
Quantum property testing in sparse directed graphs2410.05001v3 · Simon Apers, Fr'ed'eric Magniez, Sayantan Sen et al.2024 · 0 citationsarXiv
Even-Cycle Detection in the Randomized and Quantum CONGEST Model2402.12018v2 · Pierre Fraigniaud, Mael Luce, Frederic Magniez et al.2024 · 5 citationsarXiv
Quantum Distributed Complexity of Set Disjointness on a Line2002.11795v5 · Frederic Magniez, Ashwin Nayak2020 · 10 citationsACM Transactions on Computation Theory, Volume 14, Issue 1, March 2022, Article No.: 5, pp 1-22
Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs2002.08944v5 · Yassine Hamoudi, Fr'ed'eric Magniez2020 · 13 citationsACM Transactions on Computation Theory, vol. 15(1-2), (2023)
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model1908.11488v2 · Taisuke Izumi, Francois Le Gall, Fr'ed'eric Magniez2019 · 18 citationsProceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), 23:1-23:13, 2020
Quantum Chebyshev's Inequality and Applications1807.06456v3 · Yassine Hamoudi, Fr'ed'eric Magniez2018 · 16 citationsProceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132 of LIPIcs, pages 69:1-99:16, 2019
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks1804.02917v3 · Francois Le Gall, Fr'ed'eric Magniez2018 · 36 citationsProceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), pp. 337-346, 2018
Improved bounds for testing Dyck languages1707.06606v2 · Eldar Fischer, Fr'ed'eric Magniez, Tatiana Starikovskaya2017 · 1 citationarXiv
Extended Learning Graphs for Triangle Finding1609.07786v2 · Titouan Carette, Mathieu Lauriere, Fr'ed'eric Magniez2016 · 5 citationsarXiv
Streaming Communication Protocols1609.07059v1 · Lucas Boczkowski, Iordanis Kerenidis, Fr'ed'eric Magniez2016 · 1 citationarXiv
Stable Matching with Evolving Preferences1509.01988v2 · Varun Kanade, Nikos Leonardos, Fr'ed'eric Magniez2015 · 10 citationsarXiv
Streaming Property Testing of Visibly Pushdown Languages1505.03334v4 · Nathanael Francois, Fr'ed'eric Magniez, Michel de Rougemont et al.2015 · 10 citationsarXiv
Improved bounds for the randomized decision tree complexity of recursive majority1309.7565v1 · Frederic Magniez, Ashwin Nayak, Miklos Santha et al.2013 · 22 citationsarXiv
Optimal parallel quantum query algorithms1309.6116v2 · Stacey Jeffery, Frederic Magniez, Ronald de Wolf2013 · 24 citationsarXiv
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting1309.0647v5 · Nathanael Francois, Rahul Jain, Frederic Magniez2013 · 1 citationarXiv
Some approximations in Model Checking and Testing1304.5199v1 · M.C. Gaudel, R. Lassaigne, F. Magniez et al.2013 · 3 citationsarXiv
A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates1302.7316v1 · Andrew M. Childs, Stacey Jeffery, Robin Kothari et al.2013 · 5 citationsarXiv
Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing1210.1014v1 · Troy Lee, Frederic Magniez, Miklos Santha2012 · 33 citationsarXiv
Nested Quantum Walks with Quantum Data Structures1210.1199v1 · Stacey Jeffery, Robin Kothari, Frederic Magniez2012 · 50 citationsProceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1474-1485 (2013)
Streaming Complexity of Checking Priority Queues1209.4971v1 · Nathanael Francois, Frederic Magniez2012 · 4 citationsarXiv
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision1112.5855v2 · Stacey Jeffery, Robin Kothari, Fr'ed'eric Magniez2011 · 21 citationsProceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Lecture Notes in Computer Science 7391, pp. 522-532
Maximum Matching in Semi-Streaming with Few Passes1112.0184v3 · Christian Konrad, Fr'ed'eric Magniez, Claire Mathieu2011 · 77 citationsarXiv
A learning graph based quantum query algorithm for finding constant-size subgraphs1109.5135v3 · Troy Lee, Frederic Magniez, Miklos Santha2011 · 21 citationsarXiv
The complexity of approximate Nash equilibrium in congestion games with negative delays1102.1161v1 · Frederic Magniez, Michel de Rougemont, Miklos Santha et al.2011 · 2 citationsarXiv
Validating XML Documents in the Streaming Model with External Memory1012.3311v3 · Christian Konrad, Frederic Magniez2010 · 10 citationsarXiv
Quantum walks can find a marked element on any graph1002.2419v2 · Hari Krovi, Fr'ed'eric Magniez, Maris Ozols et al.2010 · 80 citationsAlgorithmica 74(2), pp. 851-907 (2016)
Recognizing well-parenthesized expressions in the streaming model0911.3291v1 · F. Magniez, C. Mathieu, A. Nayak2009 · 36 citationsarXiv
Strong no-go theorem for Gaussian quantum bit commitment0905.3419v2 · Loick Magnin, Fr'ed'eric Magniez, Anthony Leverrier et al.2009 · 37 citationsPhys. Rev. A 81, 010302 (2010)
On the hitting times of quantum versus random walks0808.0084v1 · Frederic Magniez, Ashwin Nayak, Peter C. Richter et al.2008 · 90 citationsarXiv
Search via Quantum Walkquant-ph/0608026v4 · Fr'ed'eric Magniez, Ashwin Nayak, J'er'emie Roland et al.2006 · 294 citationsSIAM Journal on Computing, 40(1):142-164, 2011
Quantum Complexity of Testing Group Commutativityquant-ph/0506265v4 · Frederic Magniez, Ashwin Nayak2005 · 87 citationsarXiv
Hidden Translation and Translating Coset in Quantum Computingquant-ph/0211091v4 · K. Friedl, G. Ivanyos, F. Magniez et al.2002 · 22 citationsSIAM Journal on Computing 43:1 (2014)
Quantum Algorithms for Element Distinctnessquant-ph/0007016v2 · Harry Buhrman, Christoph Durr, Mark Heiligman et al.2000 · 101 citationsSIAM Journal on Computing, 34(6), 1324-1330, 2005
Career total: 131 works. 38 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.