Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR98-047 | 21st August 1998
Salil Vadhan

Extracting All the Randomness from a Weakly Random Source

Revisions: 1 , Comments: 1


In this paper, we give explicit constructions of extractors which work for
a source of any min-entropy on strings of length $n$. The first
construction extracts any constant fraction of the min-entropy using
O(log^2 n) additional random bits. The second extracts all the
min-entropy using O(log^3 n) additional random ... more >>>


TR98-045 | 17th July 1998
Detlef Sieling

A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

For (1,+k)-branching programs and read-k-times branching
programs syntactic and nonsyntactic variants can be distinguished. The
nonsyntactic variants correspond in a natural way to sequential
computations with restrictions on reading the input while lower bound
proofs are easier or only known for the syntactic variants. In this
paper it is shown ... more >>>


TR98-044 | 31st July 1998
Jiri Sgall

Bounds on Pairs of Families with Restricted Intersections


We study pairs of families ${\cal A},{\cal B}\subseteq
2^{\{1,\ldots,r\}}$ such that $|A\cap B|\in L$ for any
$A\in{\cal A}$, $B\in{\cal B}$. We are interested in the maximal
product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and $L$. We give
asymptotically optimal bounds for $L$ containing only elements
of $s<q$ residue classes modulo ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint