
PreviousNext
We consider here a large network of $n$ nodes which supports
only the following unreliable basic communication primitive:
when a node requests communication then this request
{\em may fail}, independently of other requests, with probability
$f<1$. Even if it succeeds, the request is answered by returning
a stable link to ...
more >>>
A {\em supermodel} is a satisfying assignment of a boolean formula
for which any small alteration, such as a single bit flip, can be
repaired by another small alteration, yielding a nearby
satisfying assignment. We study computational problems associated
with super models and some generalizations thereof. For general
formulas, ...
more >>>
We give the first construction of a pseudo-random generator with
optimal seed length that uses (essentially) arbitrary hardness.
It builds on the novel recursive use of the NW-generator in
a previous paper by the same authors, which produced many optimal
generators one of which was pseudo-random. This is achieved ...
more >>>
PreviousNext