Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Pseudorandom Generators with Large Stretch and Low Locality from Random Local One-Way Functions
event speaker icon
Benny Applebaum, Tel-Aviv University
event date icon
Sunday, 22.04.2012, 13:00
event location icon
Taub 201
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.