## Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions

by Benny Applebaum

We continue the study of pseudorandom generators (PRG) in NC0 that stretch n-bits of input into m-bits of outputs. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\eps}$, it remains unclear whether achieving larger stretch such as $m=2n$ or even $m=n+n^2$ is possible. The existence of such PRGs, which was posed as an open question in previous works (e.g., [Cryan and Miltersen, MFCS 2001], [Mossel, Shpilka and Trevisan, FOCS 2003], and [Applebaum, Ishai and Kushilevitz, FOCS 2004]), has recently gained an additional motivation due to several interesting applications. We obtain NC0 constructions of linear-stretch PRGs and polynomial-stretch weak-PRGs where in the latter case the distinguishing advantage is $1/{\rm poly}(n)$ rather than negligible. These constructions are based on the one-wayness of random'' NC0 functions -- a variant of an assumption made by Goldreich (ECCC 2000). We also show that our constructions give rise to strong inapproximability results for the densest-subgraph problem in $d$-uniform hypergraphs for constant $d$. This allows us to improve the previous bounds of Feige (STOC 2002) and Khot (FOCS 2004) from constant inapproximability factor to $n^{\eps}$-inapproximability, at the expense of relying on stronger assumptions.