Frédéric Magniez

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 30

Top Venues

CoRR

Algorithmica

ACM Trans. Comput. Theory

ICALP

Publications

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

Frédéric Magniez.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Frédéric Magniez