Revision #2 Authors: Madhu Sudan, Luca Trevisan, Salil Vadhan

Accepted on: 18th May 2000 00:00

Downloads: 2496

Keywords:

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.

Revision #1 Authors: Madhu Sudan, Luca Trevisan, Salil Vadhan

Accepted on: 10th June 1999 00:00

Downloads: 2943

Keywords:

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.

TR98-074 Authors: Madhu Sudan, Luca Trevisan, Salil Vadhan

Publication: 17th December 1998 09:46

Downloads: 2496

Keywords:

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