Frédéric Magniez

110 papers A* 21A 11B 2Journal 65Unranked 10

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model. CoRR Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
2025	A*	`conf`	Deterministic Even-Cycle Detection in Broadcast CONGEST. ICALP Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca
2025	A*	`conf`	Quantum Communication Advantage for Leader Election and Agreement. PODC Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
2025	J	`jnl`	Quantum Communication Advantage for Leader Election and Agreement. CoRR Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
2025	A	`conf`	Quantum Property Testing in Sparse Directed Graphs. APPROX/RANDOM Simon Apers, Frédéric Magniez, Sayantan Sen, Dániel Szabó
2024	—	`ed.`	19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, Okinawa, Japan, September 9-13, 2024 TQC Frédéric Magniez, Alex Bredariol Grilo
2024	J	`jnl`	Deterministic Even-Cycle Detection in Broadcast CONGEST. CoRR Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca
2024	A*	`conf`	Even-Cycle Detection in the Randomized and Quantum CONGEST Model. PODC Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca
2024	J	`jnl`	Even-Cycle Detection in the Randomized and Quantum CONGEST Model. CoRR Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca
2024	J	`jnl`	Quantum property testing in sparse directed graphs. CoRR Simon Apers, Frédéric Magniez, Sayantan Sen, Dániel Szabó
2023	J	`jnl`	Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. ACM Trans. Comput. Theory Yassine Hamoudi, Frédéric Magniez
2022	J	`jnl`	Quantum Distributed Complexity of Set Disjointness on a Line. ACM Trans. Comput. Theory Frédéric Magniez, Ashwin Nayak
2021	—	`conf`	Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. TQC Yassine Hamoudi, Frédéric Magniez
2020	J	`jnl`	Extended Learning Graphs for Triangle Finding. Algorithmica Titouan Carette, Mathieu Laurière, Frédéric Magniez
2020	A	`conf`	Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. STACS Taisuke Izumi, François Le Gall, Frédéric Magniez
2020	A*	`conf`	Quantum Distributed Complexity of Set Disjointness on a Line. ICALP Frédéric Magniez, Ashwin Nayak
2020	J	`jnl`	Quantum Distributed Complexity of Set Disjointness on a Line. CoRR Frédéric Magniez, Ashwin Nayak
2020	J	`jnl`	Quantum Time-Space Tradeoffs by Recording Queries. CoRR Yassine Hamoudi, Frédéric Magniez
2019	A*	`conf`	Quantum Chebyshev's Inequality and Applications. ICALP Yassine Hamoudi, Frédéric Magniez
2019	J	`jnl`	Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. CoRR Taisuke Izumi, François Le Gall, Frédéric Magniez
2018	A*	`conf`	Improved bounds for testing Dyck languages. SODA Eldar Fischer, Frédéric Magniez, Tatiana Starikovskaya
2018	J	`jnl`	Quantum Chebyshev's Inequality and Applications. CoRR Yassine Hamoudi, Frédéric Magniez
2018	J	`jnl`	Streaming Communication Protocols. ACM Trans. Comput. Theory Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez
2018	A*	`conf`	Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. PODC François Le Gall, Frédéric Magniez
2018	J	`jnl`	Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. CoRR François Le Gall, Frédéric Magniez
2017	A	`conf`	Extended Learning Graphs for Triangle Finding. STACS Titouan Carette, Mathieu Laurière, Frédéric Magniez
2017	J	`jnl`	Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. Algorithmica Troy Lee, Frédéric Magniez, Miklos Santha
2017	J	`jnl`	Improved bounds for testing Dyck languages. CoRR Eldar Fischer, Frédéric Magniez, Tatiana Starikovskaya
2017	J	`jnl`	Optimal Parallel Quantum Query Algorithms. Algorithmica Stacey Jeffery, Frédéric Magniez, Ronald de Wolf
2017	A*	`conf`	Streaming Communication Protocols. ICALP Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez
2016	J	`jnl`	Extended Learning Graphs for Triangle Finding. CoRR Titouan Carette, Mathieu Laurière, Frédéric Magniez
2016	J	`jnl`	Improved bounds for the randomized decision tree Complexity of recursive majority. Random Struct. Algorithms Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao
2016	J	`jnl`	Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. Algorithmica Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez
2016	J	`jnl`	Quantum Walks Can Find a Marked Element on Any Graph. Algorithmica Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland
2016	—	`conf`	Stable Matching with Evolving Preferences. APPROX-RANDOM Varun Kanade, Nikos Leonardos, Frédéric Magniez
2016	J	`jnl`	Streaming Communication Protocols. CoRR Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez
2016	J	`jnl`	Streaming Communication Protocols. Electron. Colloquium Comput. Complex. Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez
2016	A	`conf`	Streaming Property Testing of Visibly Pushdown Languages. ESA Nathanaël François, Frédéric Magniez, Michel de Rougemont, Olivier Serre
2015	J	`jnl`	Stable Matching with Evolving Preferences. CoRR Varun Kanade, Nikos Leonardos, Frédéric Magniez
2015	J	`jnl`	Streaming Property Testing of Visibly Pushdown Languages. CoRR Nathanaël François, Frédéric Magniez, Michel de Rougemont, Olivier Serre
2015	J	`jnl`	Streaming Property Testing of Visibly Pushdown Languages. Electron. Colloquium Comput. Complex. Nathanaël François, Frédéric Magniez, Olivier Serre, Michel de Rougemont
2014	J	`jnl`	Hidden Translation and Translating Coset in Quantum Computing. SIAM J. Comput. Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen
2014	A	`conf`	Optimal Parallel Quantum Query Algorithms. ESA Stacey Jeffery, Frédéric Magniez, Ronald de Wolf
2014	J	`jnl`	Recognizing Well-Parenthesized Expressions in the Streaming Model. SIAM J. Comput. Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2014	—	`conf`	Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. APPROX-RANDOM Nathanaël François, Rahul Jain, Frédéric Magniez
2013	J	`jnl`	A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates CoRR Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
2013	J	`jnl`	Improved bounds for the randomized decision tree complexity of recursive majority. CoRR Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao
2013	A*	`conf`	Improved quantum query algorithms for triangle finding and associativity testing. SODA Troy Lee, Frédéric Magniez, Miklos Santha
2013	J	`jnl`	Input/Output Streaming Complexity of Reversal and Sorting. CoRR Nathanaël François, Frédéric Magniez
2013	A*	`conf`	Nested Quantum Walks with Quantum Data Structures. SODA Stacey Jeffery, Robin Kothari, Frédéric Magniez
2013	J	`jnl`	Optimal parallel quantum query algorithms. CoRR Stacey Jeffery, Frédéric Magniez, Ronald de Wolf
2013	J	`jnl`	Some approximations in Model Checking and Testing CoRR Marie-Claude Gaudel, Richard Lassaigne, Frédéric Magniez, Michel de Rougemont
2013	A	`conf`	Streaming Complexity of Checking Priority Queues. STACS Nathanaël François, Frédéric Magniez
2013	—	`conf`	Time-Efficient Quantum Walks for 3-Distinctness. ICALP (1) Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
2013	J	`jnl`	Validating XML documents in the streaming model with external memory. ACM Trans. Database Syst. Christian Konrad, Frédéric Magniez
2012	—	`conf`	Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. ICALP (1) Stacey Jeffery, Robin Kothari, Frédéric Magniez
2012	J	`jnl`	Learning graph based quantum query algorithms for finding constant-size subgraphs. Chic. J. Theor. Comput. Sci. Troy Lee, Frédéric Magniez, Miklos Santha
2012	—	`conf`	Maximum Matching in Semi-streaming with Few Passes. APPROX-RANDOM Christian Konrad, Frédéric Magniez, Claire Mathieu
2012	J	`jnl`	On the Hitting Times of Quantum Versus Random Walks. Algorithmica Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
2012	J	`jnl`	Streaming Complexity of Checking Priority Queues CoRR Nathanaël François, Frédéric Magniez
2012	J	`jnl`	Streaming Complexity of Checking Priority Queues. Electron. Colloquium Comput. Complex. Nathanaël François, Frédéric Magniez
2012	A	`conf`	Validating XML documents in the streaming model with external memory. ICDT Christian Konrad, Frédéric Magniez
2011	J	`jnl`	A learning graph based quantum query algorithm for finding constant-size subgraphs CoRR Troy Lee, Frédéric Magniez, Miklos Santha
2011	—	`conf`	Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. ICALP (1) Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao
2011	J	`jnl`	Maximum Matching in Semi-Streaming with Few Passes CoRR Christian Konrad, Frédéric Magniez, Claire Mathieu
2011	J	`jnl`	Search via Quantum Walk. SIAM J. Comput. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha
2011	—	`conf`	The Complexity of Approximate Nash Equilibrium in Congestion Games with Negative Delays. WINE Frédéric Magniez, Michel de Rougemont, Miklos Santha, Xavier Zeitoun
2011	J	`jnl`	The complexity of approximate Nash equilibrium in congestion games with negative delays CoRR Frédéric Magniez, Michel de Rougemont, Miklos Santha, Xavier Zeitoun
2010	J	`jnl`	Approximate Satisfiability and Equivalence. SIAM J. Comput. Eldar Fischer, Frédéric Magniez, Michel de Rougemont
2010	—	`conf`	Finding Is as Easy as Detecting for Quantum Walks. ICALP (1) Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland
2010	J	`jnl`	Improved bounds for the randomized decision tree complexity of recursive majority. Electron. Colloquium Comput. Complex. Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao
2010	A*	`conf`	Recognizing well-parenthesized expressions in the streaming model. STOC Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2010	J	`jnl`	The Streaming Complexity of Validating XML Documents CoRR Christian Konrad, Frédéric Magniez
2009	J	`jnl`	Foreword from the Guest Editors. Algorithmica Frédéric Magniez, Ashwin Nayak
2009	A*	`conf`	On the hitting times of quantum versus random walks. SODA Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
2009	J	`jnl`	Quantum Testers for Hidden Group Properties. Fundam. Informaticae Katalin Friedl, Miklos Santha, Frédéric Magniez, Pranab Sen
2009	J	`jnl`	Recognizing well-parenthesized expressions in the streaming model CoRR Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2009	J	`jnl`	Recognizing well-parenthesized expressions in the streaming model. Electron. Colloquium Comput. Complex. Frédéric Magniez, Claire Mathieu, Ashwin Nayak
2008	J	`jnl`	Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. SIAM J. Comput. Sophie Laplante, Frédéric Magniez
2008	J	`jnl`	On the hitting times of quantum versus random walks. CoRR Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
2007	J	`jnl`	Probabilistic abstraction for model checking: An approach based on property testing. ACM Trans. Comput. Log. Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont
2007	J	`jnl`	Property Testing of Regular Tree Languages. Algorithmica Frédéric Magniez, Michel de Rougemont
2007	J	`jnl`	Quantum Algorithms for the Triangle Problem. SIAM J. Comput. Frédéric Magniez, Miklos Santha, Mario Szegedy
2007	J	`jnl`	Quantum Complexity of Testing Group Commutativity. Algorithmica Frédéric Magniez, Ashwin Nayak
2007	A*	`conf`	Search via quantum walk. STOC Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha
2007	J	`jnl`	Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates. SIAM J. Comput. Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha
2006	A*	`conf`	Approximate Satisfiability and Equivalence. LICS Eldar Fischer, Frédéric Magniez, Michel de Rougemont
2006	J	`jnl`	Search via Quantum Walk. CoRR Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha
2006	—	`conf`	Self-testing of Quantum Circuits. ICALP (1) Frédéric Magniez, Dominic Mayers, Michele Mosca, Harold Ollivier
2005	J	`jnl`	Multi-Linearity Self-Testing with Relative Error. Theory Comput. Syst. Frédéric Magniez
2005	J	`jnl`	Quantum Algorithms for Element Distinctness. SIAM J. Comput. Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf
2005	A*	`conf`	Quantum Complexity of Testing Group Commutativity. ICALP Frédéric Magniez, Ashwin Nayak
2005	A*	`conf`	Quantum algorithms for the triangle problem. SODA Frédéric Magniez, Miklos Santha, Mario Szegedy
2004	A	`conf`	Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. CCC Sophie Laplante, Frédéric Magniez
2004	A*	`conf`	Property Testing of Regular Tree Languages. ICALP Frédéric Magniez, Michel de Rougemont
2004	J	`jnl`	Property and Equivalence Testing on Strings Electron. Colloquium Comput. Complex. Eldar Fischer, Frédéric Magniez, Michel de Rougemont
2003	J	`jnl`	Approximate testing with error relative to input size. J. Comput. Syst. Sci. Marcos A. Kiwi, Frédéric Magniez, Miklos Santha
2003	J	`jnl`	Efficient Quantum Algorithms For Some Instances Of The Non-Abelian Hidden Subgroup Problem. Int. J. Found. Comput. Sci. Gábor Ivanyos, Frédéric Magniez, Miklos Santha
2003	A*	`conf`	Hidden translation and orbit coset in quantum computing. STOC Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen
2003	B	`conf`	Quantum Testers for Hidden Group Properties. MFCS Katalin Friedl, Frédéric Magniez, Miklos Santha, Pranab Sen
2002	A*	`conf`	Probabilistic Abstraction for Model Checking: An Approach Based on Property Testing. LICS Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont
2001	B	`conf`	Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem. SPAA Gábor Ivanyos, Frédéric Magniez, Miklos Santha
2001	J	`jnl`	Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey Electron. Colloquium Comput. Complex. Marcos A. Kiwi, Frédéric Magniez, Miklos Santha
2001	J	`jnl`	Probabilistic abstraction for model checking: An approach based on property testing Electron. Colloquium Comput. Complex. Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont
2001	A	`conf`	Quantum Algorithms for Element Distinctness. CCC Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf
2000	A	`conf`	Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey. Theoretical Aspects of Computer Science Marcos A. Kiwi, Frédéric Magniez, Miklos Santha
2000	A	`conf`	Multi-linearity Self-Testing with Relative Error. STACS Frédéric Magniez
2000	A*	`conf`	Self-testing of universal and fault-tolerant sets of quantum gates. STOC Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha
1999	A*	`conf`	Approximate Testing with Relative Error. STOC Marcos A. Kiwi, Frédéric Magniez, Miklos Santha
1999	J	`jnl`	Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates CoRR Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha