2 citations · 2 across the 5 of their papers we have counts for
5 papers
Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries
François Le Gall, Oran Nadler, Harumichi Nishimura +1
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public random…
Classical versus quantum queries in quantum PCPs with classical proofs
Harry Buhrman, François Le Gall, Jordi Weggemans
We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for quantum queries to a polynomially-sized classical proof ($\mat…
On the Group and Color Isomorphism Problems
François Le Gall, David J. Rosenbaum
In this paper, we prove results on the relationship between the complexity of the group and color isomorphism problems. The difficulty of color isomorphism problems is known to be…
Quantum Communication Complexity of Distributed Set Joins
Stacey Jeffery, François Le Gall
Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in t…
Solving Laplacian Systems in Logarithmic Space
François Le Gall
We investigate the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of linear equations i…