Computer Science Colloquia: Sun, Feb 12 at 11:00 - Benny Applebaum
Niv Buchbinder
Dear all,
Next week we are happy to have Benny Applebaum from School of Electrical Engineering, Tel-Aviv University.
You can view the upcoming talks of the seminar at:
See you,
Niv Buchbinder.
%%%%%%%%%%%%%%%%%%%%%%
Computer Science Colloquia - Open University of Israel
%%%%%%%%%%%%%%%%%%%%%%
Time: Sunday, February 12, at 11:00-12:00
Place: Visitor center 194, Open University.
Speaker: Benny Applebaum, School of Electrical Engineering, Tel-Aviv University.
-------
Title: Pseudorandomness of Goldreich's Function.
-----
Abstract:
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 will present two new results that support the existence of such generators based on random local functions (aka Goldreich's one-way function).
The talk does not assume prior knowledge of cryptography.