0000000000512486

AUTHOR

François Le Gall

showing 3 related works from this author

Fast Matrix Multiplication

2015

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every e > 0, …

Class (set theory)Conjecturepeople.profession0102 computer and information sciences02 engineering and technology01 natural sciencesIdentity (music)Matrix multiplicationRunning timeCombinatorics010201 computation theory & mathematicsTensor (intrinsic definition)0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingCoppersmithpeopleMathematicsCoppersmith–Winograd algorithmProceedings of the forty-seventh annual ACM symposium on Theory of Computing
researchProduct

The quantum query complexity of certification

2009

We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

FOS: Computer and information sciencesDiscrete mathematicsQuantum Physics0209 industrial biotechnologyNuclear and High Energy PhysicsQuantum queryComputer scienceDirect sumFOS: Physical sciencesGeneral Physics and AstronomyStatistical and Nonlinear Physics0102 computer and information sciences02 engineering and technologyCertificationComputational Complexity (cs.CC)Certificate01 natural sciencesTheoretical Computer ScienceComputer Science - Computational Complexity020901 industrial engineering & automationComputational Theory and Mathematics010201 computation theory & mathematicsQuantum Physics (quant-ph)QuantumMathematical PhysicsQuantum Information and Computation
researchProduct

Fast Matrix Multiplication: Limitations of the Laser Method

2014

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.3729})$. These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time $O(n^{2.3725})$, and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078})$; in particular, this approach cannot prove the conjecture that f…

FOS: Computer and information sciencesComputer Science - Computational ComplexityComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)Computational Complexity (cs.CC)
researchProduct