The Taub Faculty of Computer Science Events and Talks

Locally-computable pseudorandom generators (PRGs) map n random input bits into m>n pseudorandom bits such that each of the m outputs depend on a small number of d inputs. While it is known that such generators are likely to exist for the case of small sub-linear stretch m=n+n^{0.9}, 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, has recently gained an additional motivation due to several interesting applications in cryptography and complexity. 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). We will also show that our constructions give rise to strong inapproximability results for the densest-subgraph problem in d-uniform hypergraphs for constant d.

The talk does not assume prior knowledge of cryptography.