Impagliazzo and Wigderson have recently shown that
if there exists a decision problem solvable in time 2^{O(n)}
and having circuit complexity 2^{Omega(n)}
(for all but finitely many n) then P=BPP. This result
is a culmination of a series of works showing
connections between the existence of hard predicates
and the existence of good pseudorandom generators.

The construction of Impagliazzo and Wigderson
goes through three phases of "hardness amplification"
(a multivariate polynomial encoding, a first derandomized
XOR Lemma, and a second derandomized XOR Lemma) that are composed
with the Nisan-Wigderson generator. In this paper we present
two different approaches to proving the main result of
Impagliazzo and Wigderson. In developing each approach, we
introduce new techniques and prove new results that could be useful in
future
improvements and/or applications of hardness-randomness trade-offs.

Our first result is that when (a modified version of) the Nisan-Wigderson
generator construction is applied with a "mildly" hard predicate,
the result is a generator that produces a distribution indistinguishable
from having large min-entropy. An extractor can then be used to
produce a distribution computationally indistinguishable from uniform.
This is the first construction of a pseudorandom generator that
works with a mildly hard predicate without doing hardness amplification.

We then show that in the Impagliazzo-Wigderson construction
only the first hardness-amplification phase
(encoding with multivariate polynomial) is necessary, since it
already gives the required average-case hardness. We prove this
result by (i) establishing a connection between the hardness-amplification
problem and a list-decoding problem for error-correcting codes; and
(ii) presenting a
list-decoding algorithm for error-correcting codes based on multivariate
polynomials that improves and simplifies a previous
one by Arora and Sudan.

Impagliazzo and Wigderson have recently shown that
if there exists a decision problem solvable in time 2^{O(n)}
and having circuit complexity 2^{Omega(n)}
(for all but finitely many n) then P=BPP. This result
is a culmination of a series of works showing
connections between the existence of hard predicates
and the existence of good pseudorandom generators.

The construction of Impagliazzo and Wigderson
goes through three phases of "hardness amplification"
(a multivariate polynomial encoding, a first derandomized
XOR Lemma, and a second derandomized XOR Lemma) that are composed
with the Nisan-Wigderson generator. In this paper we present
two different approaches to proving the main result of
Impagliazzo and Wigderson. In developing each approach, we
introduce new techniques and prove new results that could be useful in
future
improvements and/or applications of hardness-randomness trade-offs.

Our first result is that when (a modified version of) the Nisan-Wigderson
generator construction is applied with a "mildly" hard predicate,
the result is a generator that produces a distribution indistinguishable
from having large min-entropy. An extractor can then be used to
produce a distribution computationally indistinguishable from uniform.
This is the first construction of a pseudorandom generator that
works with a mildly hard predicate without doing hardness amplification.

We then show that in the Impagliazzo-Wigderson construction
only the first hardness-amplification phase
(encoding with multivariate polynomial) is necessary, since it
already gives the required average-case hardness. We prove this
result by (i) establishing a connection between the hardness-amplification
problem and a list-decoding problem for error-correcting codes; and
(ii) presenting a
list-decoding algorithm for error-correcting codes based on multivariate
polynomials that improves and simplifies a previous
one by Arora and Sudan.

Impagliazzo and Wigderson have recently shown that
if there exists a decision problem solvable in time $2^{O(n)}$
and having circuit complexity $2^{\Omega(n)}$
(for all but finitely many $n$) then $\p=\bpp$. This result
is a culmination of a series of works showing
connections between the existence of hard predicates
and the existence of good pseudorandom generators.

The construction of Impagliazzo and Wigderson
goes through three phases of ``hardness amplification''
(a multivariate polynomial encoding, a first derandomized
XOR Lemma, and a second derandomized XOR Lemma) that are composed
with the Nisan-Wigderson generator. In this paper we present
two different approaches to proving of the main result of
Impagliazzo and Wigderson. In developing each approach, we
introduce new techniques and prove new results that could be
useful in future improvements and/or applications of
hardness-randomness trade-offs.

Our first result is that when (a modified version of) the
Nisan-Wigderson generator construction is applied with a
``mildly'' hard predicate, the result is a generator that
produces a distribution indistinguishable from having large
min-entropy. An extractor can then be used to produce a
distribution computationally indistinguishable from uniform.
This is the first construction of a pseudorandom generator
that works with a mildly hard predicate without doing
hardness amplification.

We then show that in the Impagliazzo--Wigderson construction
only the first hardness-amplification phase (encoding with
multivariate polynomial) is necessary, since it already
gives the required average-case hardness. We prove this
result by (i) establishing a connection between the
hardness-amplification problem and a list-decoding problem
for error correcting codes based on multivariate polynomials;
and (ii) presenting a list-decoding algorithm that improves
and simplifies a previous one by Arora and Sudan~\cite{AroraSu97}.