Frédéric Magniez

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

Collaborative distances:

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

2024

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

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

CoRR, 2024

2023

Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs.

Yassine Hamoudi, Frédéric Magniez

ACM Trans. Comput. Theory, June, 2023

2022

Quantum Distributed Complexity of Set Disjointness on a Line.

Frédéric Magniez, Ashwin Nayak

ACM Trans. Comput. Theory, 2022

2020

Quantum Time-Space Tradeoffs by Recording Queries.

Yassine Hamoudi, Frédéric Magniez

CoRR, 2020

Extended Learning Graphs for Triangle Finding.

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

Algorithmica, 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

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

Optimal Parallel Quantum Query Algorithms.

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

Algorithmica, 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

Streaming Communication Protocols.

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

Electron. Colloquium Comput. Complex., 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

Stable Matching with Evolving Preferences.

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

Proceedings of the Approximation, 2016

2015

Streaming Property Testing of Visibly Pushdown Languages.

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

Electron. Colloquium Comput. Complex., 2015

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

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

Validating XML documents in the streaming model with external memory.

Christian Konrad, Frédéric Magniez

ACM Trans. Database Syst., 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

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

Streaming Complexity of Checking Priority Queues.

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

Electron. Colloquium Comput. Complex., 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

On the Hitting Times of Quantum Versus Random Walks.

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

Algorithmica, 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

Search via Quantum Walk.

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

SIAM J. Comput., 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

2010

Approximate Satisfiability and Equivalence.

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

SIAM J. Comput., 2010

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

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

Electron. Colloquium Comput. Complex., 2010

The Streaming Complexity of Validating XML Documents

Christian Konrad, Frédéric Magniez

CoRR, 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

Quantum Testers for Hidden Group Properties.

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

Fundam. Informaticae, 2009

Recognizing well-parenthesized expressions in the streaming model.

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

Electron. Colloquium Comput. Complex., 2009

Foreword from the Guest Editors.

Frédéric Magniez, Ashwin Nayak

Algorithmica, 2009

2008

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

Sophie Laplante, Frédéric Magniez

SIAM J. Comput., 2008

2007

Probabilistic abstraction for model checking: An approach based on property testing.

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

ACM Trans. Comput. Log., 2007

Quantum Algorithms for the Triangle Problem.

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

SIAM J. Comput., 2007

Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates.

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

SIAM J. Comput., 2007

Property Testing of Regular Tree Languages.

Frédéric Magniez, Michel de Rougemont

Algorithmica, 2007

Quantum Complexity of Testing Group Commutativity.

Frédéric Magniez, Ashwin Nayak

Algorithmica, 2007

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 Element Distinctness.

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

SIAM J. Comput., 2005

Multi-Linearity Self-Testing with Relative Error.

Frédéric Magniez

Theory Comput. Syst., 2005

2004

Property and Equivalence Testing on Strings

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

Electron. Colloquium Comput. Complex., 2004

2003

Approximate testing with error relative to input size.

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

J. Comput. Syst. Sci., 2003

Efficient Quantum Algorithms For Some Instances Of The Non-Abelian Hidden Subgroup Problem.

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

Int. J. Found. Comput. 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

2001

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

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

Electron. Colloquium Comput. Complex., 2001

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