## 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.