Amnon Ta-Shma

We deal with the problem of extracting as much randomness as possible

from a defective random source.

We devise a new tool, a ``merger'', which is a function that accepts

d strings, one of which is uniformly distributed,

and outputs a single string that is guaranteed ...
more >>>

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

The efficient construction of Hitting Sets for non trivial classes

of boolean functions is a fundamental problem in the theory

of derandomization. Our paper presents a new method to efficiently

construct Hitting Sets for the class of systems of boolean linear

functions. Systems of boolean linear functions ...
more >>>

Uri Zwick

We present two new algorithms for solving the {\em All

Pairs Shortest Paths\/} (APSP) problem for weighted directed

graphs. Both algorithms use fast matrix multiplication algorithms.

The first algorithm

solves the APSP problem for weighted directed graphs in which the edge

weights are integers of small absolute value in ...
more >>>

Dean Doron, Francois Le Gall, Amnon Ta-Shma

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