81 citations · 408 across the 33 of their papers we have counts for
38 papers
Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
Frédéric Magniez, Sebastian Zur
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function , the BHT algorithm finds a collision using $O(N^{1/3})…
Even-Cycle Detection in the Randomized and Quantum CONGEST Model
Pierre Fraigniaud, Mael Luce, Frederic Magniez +1
We show that, for every , -freeness can be decided in rounds in the \CONGEST{} model by a randomized Monte-Carlo distributed algorithm with one-side…
Quantum Distributed Complexity of Set Disjointness on a Line
Frederic Magniez, Ashwin Nayak
Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario with processors arranged on a path of length . It was introduce…
Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
Yassine Hamoudi, Frédéric Magniez
We study the problem of finding collision pairs in a random function by using a quantum computer. We prove that the number of queries to the function…
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model
Taisuke Izumi, François Le Gall, Frédéric Magniez
This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and…
Quantum Chebyshev's Inequality and Applications
Yassine Hamoudi, Frédéric Magniez
In this paper we provide new quantum algorithms with polynomial speed-up for a range of problems for which no such results were known, or we improve previous algorithms. First, we…