“The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators G:{0,1}r→{0,1}m that fool circuits of size m, assuming the existence of explicit hard functions. … We study whether extreme high-end PRGs can be constructed from the following scaled version of the assumption which we call “the extreme high-end hardness assumption”, and in which β=1−o(1) and B=1+o(1). We give a partial negative answer, showing that certain approaches cannot yield a black-box proof.”

Find the paper and full list of authors at ArXiv.