Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR11-007 | 5th April 2012 16:35

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

RSS-Feed




Revision #3
Authors: Benny Applebaum
Accepted on: 5th April 2012 16:35
Downloads: 3253
Keywords: 


Abstract:

We continue the study of pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\epsilon}$, 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 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^{\epsilon}$-inapproximability, at the expense of relying on stronger assumptions.


Revision #2 to TR11-007 | 2nd November 2011 09:23

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





Revision #2
Authors: Benny Applebaum
Accepted on: 2nd November 2011 09:23
Downloads: 3044
Keywords: 


Abstract:

We continue the study of locally-computable pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ that each of their outputs depend on a small number of $d$ input bits. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\delta}$, it is less clear whether achieving larger stretch 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 several local constructions based on the one-wayness of ``random'' local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Specifically, we construct collections of PRGs with the following parameters:
(1) Linear stretch $m=n+\Omega(n)$ and constant locality $d=O(1)$.

(2) Polynomial stretch $m=n^{1+\delta}$ and \emph{any} (arbitrarily slowly growing) super-constant locality $d=\omega(1)$, e.g., $\log^{\star} n$.

(3) Polynomial stretch $m=n^{1+\delta}$, constant locality $d=O(1)$, and inverse polynomial distinguishing advantage (as opposed to the standard case of $n^{-\omega(1)}$).

Our constructions match the parameters achieved by previous ``ad-hoc'' candidates, and are the first to do this under a one-wayness assumption. At the core of our results lies a new search-to-decision reduction for random local functions. This reduction also shows that some of the previous PRG candidates can be based on one-wayness assumptions. Altogether, our results fortify the existence of local PRGs of long stretch.

As an additional contribution, we 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^{\epsilon}$-inapproximability, at the expense of relying on stronger assumptions.


Revision #1 to TR11-007 | 2nd November 2011 09:14

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





Revision #1
Authors: Benny Applebaum
Accepted on: 2nd November 2011 09:14
Downloads: 2747
Keywords: 


Abstract:

We continue the study of \emph{locally-computable} pseudorandom generators (PRG) $G:\nbit \ra \bit^m$ that each of their outputs depend on a small number of $d$ input bits. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\delta}$, it is less clear whether achieving larger stretch 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 several local constructions based on the one-wayness
of ``random'' local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Specifically, we construct collections of PRGs with the following parameters:

(1) Linear stretch $m=n+\Omega(n)$ and constant locality $d=O(1)$.

(2) Polynomial stretch $m=n^{1+\delta}$ and \emph{any} (arbitrarily slowly growing) super-constant locality $d=\omega(1)$, e.g., $\log^{\star} n$.

(3) Polynomial stretch $m=n^{1+\delta}$, constant locality $d=O(1)$, and distinguishing advantage bounded by $1/\poly(n)$ (as opposed to the standard case of $n^{-\omega(1)}$).

Our constructions match the parameters achieved by previous ``ad-hoc'' candidates, and are the first to do this under a one-wayness assumption. At the core of our results lies a new search-to-decision reduction for random local functions. %which may be of independent interest. This reduction also shows that some of the previous PRG candidates can be based on one-wayness assumptions. Altogether, our results fortify the existence of local PRGs of long stretch.

As an additional contribution, we 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.


Paper:

TR11-007 | 17th January 2011 15:25

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





TR11-007
Authors: Benny Applebaum
Publication: 21st January 2011 10:28
Downloads: 4591
Keywords: 

NC0

Abstract:

We continue the study of pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\epsilon}$, 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 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^{\epsilon}$-inapproximability, at the expense of relying on stronger assumptions.



ISSN 1433-8092 | Imprint