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

by Benny Applebaum

Oded's comments

This work addresses two questions that have puzzled me for a decade. The first question (or rather project) is to better understand the candidate one-way functions based on expander graphs and the second refers to the existence of pseudorandom generators of significant (e.g., linear) stretch in NC0. An obvious question left open by this work is whether the assumptions used in this work suffice fo the existence of pseudorandom generators of polynomial stretch in NC0 (rather than such weak-PRGs).

See additional comments, Nov. 2011.

The original abstract

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.

Back to list of Oded's choices.