Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Superconcentrators:
TR95-058 | 20th November 1995
Amnon Ta-Shma

On Extracting Randomness From Weak Random Sources

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

TR05-122 | 31st October 2005
Pavel Pudlak

A nonlinear bound on the number of wires in bounded depth circuits

We shall prove a lower bound on the number of edges in some bounded
depth graphs. This theorem is stronger than lower bounds proved on
bounded depth superconcentrators and enables us to prove a lower bound
on certain bounded depth circuits for which we cannot use
superconcentrators: we prove that ... more >>>

ISSN 1433-8092 | Imprint