#### Milestone Year

### 1984

#### Pseudorandomness: Objects that look random although they are not

The study of pseudorandomness refers to objects that look random
although they are not necessarily random. The key notion here
is of ``looking random'' and it can be defined with respect
to various classes of observers. The archetypical case
of pseudorandomness refers to the class of all efficient observers,
which is identified as the class of all polynomial-time algorithms.
Still, other cases of pseudorandomness that refer to more restricted
classes of observers are also of great interest and have numerous applications.

In general, WIS scientists made numerous important contributions
to the study of pseudorandomness. Some of them are mentioned next.
In 1984, WIS scientists and their collaborator showed
how to construct huge objects that look random to any efficient observer
that inspects a feasible portion of them, although these huge objects
are derived deterministically from a very short random seed.
In 1989, a WIS scientist and his collaborator showed that
any computationally hard problem has a ``core'' bit
that is very hard to predict;
that is, if it is infeasible to compute $F(x)$ given $x$,
then there exists an easy to compute Boolean function $B$
such that the bit $B(x)$ looks random to any efficient observer
that is given $x$, although $B(x)$ is totally determined by $x$.

Whereas the notion of pseudorandomness referred to in the prior paragraph
is related to computational difficulty, other notions are not.
For example, in 1990, a WIS scientist and his collaborator
presented an algorithm that stretches its input by an exponential amount
such that the output sequence fools all linear tests
(i.e., any linear combination
of some designated locations in the sequence is random).
This algorithm also implies one with double-exponential stretch
that has an output sequence in which every constant number of bits
are almost random.