Frédéric Magniez

According to our database, Frédéric Magniez authored at least 59 papers between 1999 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Quantum Communication Advantage for Leader Election and Agreement.

Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

Deterministic Even-Cycle Detection in Broadcast CONGEST.

Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Quantum Property Testing in Sparse Directed Graphs.

Simon Apers, Frédéric Magniez, Sayantan Sen, Dániel Szabó

Proceedings of the Approximation, 2025

2024

Even-Cycle Detection in the Randomized and Quantum CONGEST Model.

Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca

Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

2021

Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs.

Yassine Hamoudi, Frédéric Magniez

Proceedings of the 16th Conference on the Theory of Quantum Computation, 2021

2020

Quantum Time-Space Tradeoffs by Recording Queries.

Yassine Hamoudi, Frédéric Magniez

CoRR, 2020

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model.

Taisuke Izumi, François Le Gall, Frédéric Magniez

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Quantum Distributed Complexity of Set Disjointness on a Line.

Frédéric Magniez, Ashwin Nayak

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Quantum Chebyshev's Inequality and Applications.

Yassine Hamoudi, Frédéric Magniez

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Improved bounds for testing Dyck languages.

Eldar Fischer, Frédéric Magniez, Tatiana Starikovskaya

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks.

François Le Gall, Frédéric Magniez

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

2017

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing.

Troy Lee, Frédéric Magniez, Miklos Santha

Algorithmica, 2017

Extended Learning Graphs for Triangle Finding.

Titouan Carette, Mathieu Laurière, Frédéric Magniez

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Streaming Communication Protocols.

Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Improved bounds for the randomized decision tree Complexity of recursive majority.

Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao

Random Struct. Algorithms, 2016

Quantum Walks Can Find a Marked Element on Any Graph.

Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland

Algorithmica, 2016

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.

Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez

Algorithmica, 2016

Streaming Property Testing of Visibly Pushdown Languages.

Nathanaël François, Frédéric Magniez, Michel de Rougemont, Olivier Serre

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Stable Matching with Evolving Preferences.

Varun Kanade, Nikos Leonardos, Frédéric Magniez

Proceedings of the Approximation, 2016

2014

Hidden Translation and Translating Coset in Quantum Computing.

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen

SIAM J. Comput., 2014

Optimal Parallel Quantum Query Algorithms.

Stacey Jeffery, Frédéric Magniez, Ronald de Wolf

Proceedings of the Algorithms - ESA 2014, 2014

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting.

Nathanaël François, Rahul Jain, Frédéric Magniez

Proceedings of the Approximation, 2014

2013

Some approximations in Model Checking and Testing

Marie-Claude Gaudel, Richard Lassaigne, Frédéric Magniez, Michel de Rougemont

CoRR, 2013

A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates

Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez

CoRR, 2013

Input/Output Streaming Complexity of Reversal and Sorting.

Nathanaël François, Frédéric Magniez

CoRR, 2013

Streaming Complexity of Checking Priority Queues.

Nathanaël François, Frédéric Magniez

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Improved quantum query algorithms for triangle finding and associativity testing.

Troy Lee, Frédéric Magniez, Miklos Santha

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Nested Quantum Walks with Quantum Data Structures.

Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Time-Efficient Quantum Walks for 3-Distinctness.

Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Learning graph based quantum query algorithms for finding constant-size subgraphs.

Troy Lee, Frédéric Magniez, Miklos Santha

Chic. J. Theor. Comput. Sci., 2012

Validating XML documents in the streaming model with external memory.

Christian Konrad, Frédéric Magniez

Proceedings of the 15th International Conference on Database Theory, 2012

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.

Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Maximum Matching in Semi-streaming with Few Passes.

Christian Konrad, Frédéric Magniez, Claire Mathieu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

A learning graph based quantum query algorithm for finding constant-size subgraphs

Troy Lee, Frédéric Magniez, Miklos Santha

CoRR, 2011

The Complexity of Approximate Nash Equilibrium in Congestion Games with Negative Delays.

Frédéric Magniez, Michel de Rougemont, Miklos Santha, Xavier Zeitoun

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority.

Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

The Streaming Complexity of Validating XML Documents

Christian Konrad, Frédéric Magniez

CoRR, 2010

Recognizing well-parenthesized expressions in the streaming model.

Frédéric Magniez, Claire Mathieu, Ashwin Nayak

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Finding Is as Easy as Detecting for Quantum Walks.

Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Foreword from the Guest Editors.

Frédéric Magniez, Ashwin Nayak

Algorithmica, 2009

On the hitting times of quantum versus random walks.

Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2007

Search via quantum walk.

Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Approximate Satisfiability and Equivalence.

Eldar Fischer, Frédéric Magniez, Michel de Rougemont

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Self-testing of Quantum Circuits.

Frédéric Magniez, Dominic Mayers, Michele Mosca, Harold Ollivier

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Quantum algorithms for the triangle problem.

Frédéric Magniez, Miklos Santha, Mario Szegedy

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Quantum Complexity of Testing Group Commutativity.

Frédéric Magniez, Ashwin Nayak

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

Property and Equivalence Testing on Strings

Eldar Fischer, Frédéric Magniez, Michel de Rougemont

Electron. Colloquium Comput. Complex., 2004

Property Testing of Regular Tree Languages.

Frédéric Magniez, Michel de Rougemont

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments.

Sophie Laplante, Frédéric Magniez

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Approximate testing with error relative to input size.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

J. Comput. Syst. Sci., 2003

Hidden translation and orbit coset in quantum computing.

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Quantum Testers for Hidden Group Properties.

Katalin Friedl, Frédéric Magniez, Miklos Santha, Pranab Sen

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002

Probabilistic Abstraction for Model Checking: An Approach Based on Property Testing.

Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont

Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

2001

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem.

Gábor Ivanyos, Frédéric Magniez, Miklos Santha

Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

Quantum Algorithms for Element Distinctness.

Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Self-testing of universal and fault-tolerant sets of quantum gates.

Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Multi-linearity Self-Testing with Relative Error.

Frédéric Magniez

Proceedings of the STACS 2000, 2000

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

Proceedings of the Theoretical Aspects of Computer Science, 2000

1999

Approximate Testing with Relative Error.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999