__
Revision #1 to TR18-133 | 11th March 2019 03:21
__
#### Constant-error pseudorandomness proofs from hardness require majority

**Abstract:**
Research in the 80's and 90's showed how to construct a pseudorandom

generator from a function that is hard to compute on more than $99\%$

of the inputs. A more recent line of works showed however that if

the generator has small error, then the proof of correctness cannot

be implemented in subclasses of TC$^{0}$, and hence the construction

cannot be applied to the known hardness results. This paper considers

a typical class of pseudorandom generator constructions, and proves

an analogous result for the case of large error.

**Changes to previous version:**
Please see ack.

__
TR18-133 | 26th July 2018 20:09
__

#### Constant-error pseudorandomness proofs from hardness require majority

**Abstract:**
Research in the 80's and 90's showed how to construct a pseudorandom

generator from a function that is hard to compute on more than $99\%$

of the inputs. A more recent line of works showed however that if

the generator has small error, then the proof of correctness cannot

be implemented in subclasses of TC$^{0}$, and hence the construction

cannot be applied to the known hardness results. This paper considers

a typical class of pseudorandom generator constructions, and proves

an analogous result for the case of large error.