1 citations · 1 across the 9 of their papers we have counts for
16 papers
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
François Le Gall
We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separatio…
Constant-round quantum advantage in communication complexity for total functions
Atsuya Hasegawa, François Le Gall
We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a se…
An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
Ranitha Mataraarachchi, François Le Gall, Suguru Tamaki
Low-energy estimation and state preparation for general -local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et a…
Multi-Prover Interactive Proof Systems with Leakage
Vahid R. Asadi, Atsuya Hasegawa, François Le Gall
It is known that there exist multi-prover interactive protocols ( protocols) for the complexity class , succinct protocols for $\mathsf{…
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1
The local Hamiltonian (LH) problem is the canonical -complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that t…
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
We present an extremely simple polynomial-space exponential-time -approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomia…