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

摘要

We continue the study of pseudorandom generators (PRG) G:01n01m in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch m=n+n1?, it remains unclear whether achieving larger stretch such as m=2n or even m=n+n2 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 make progress towards resolving this question by obtaining NC0 constructions of linear-stretch PRGs and polynomial-stretch weak-PRGs (where the distinguishing advantage is inverse polynomial 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). Our techniques also show that some of the previous heuristic candidates can be based on one-way assumptions. We interpret these results as an evidence for the existence of NC0 PRGs of polynomially-long stretch. 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-inapproximability, at the expense of relying on stronger assumptions