Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author François Le Gall:

TR23-117 | 9th August 2023
François Le Gall, Yupan Liu, Qisheng Wang

Space-bounded quantum state testing via space-efficient quantum singular value transformation

Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary coRQL) and two-sided error (BQL), approached from a quantum (mixed) state testing perspective:
- The first family of natural ... more >>>

TR20-030 | 9th March 2020
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

Barriers for Rectangular Matrix Multiplication

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>

ISSN 1433-8092 | Imprint