Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Francois Le Gall:

TR17-036 | 22nd February 2017
Dean Doron, Francois Le Gall, Amnon Ta-Shma

Probabilistic logarithmic-space algorithms for Laplacian solvers

A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system $L x=b$, where $L$ is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem.
more >>>

TR14-154 | 20th November 2014
Andris Ambainis, Yuval Filmus, Francois Le Gall

Fast Matrix Multiplication: Limitations of the Laser Method

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 ... more >>>

ISSN 1433-8092 | Imprint