Constant-error pseudorandomness proofs from hardness require majority

摘要

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.