Proving and Using Pseudorandomness

Monday, Mar 6, 2017 to Friday, Mar 10, 2017

Add to Calendar

Program:

Pseudorandomness

View schedule & video »

View abstracts »

Organizers:

David Conlon (University of Oxford), Russell Impagliazzo (UC San Diego), Luca Trevisan (Simons Institute, UC Berkeley)

One theme of this workshop will be how to leverage weak pseudorandomness properties, fooling simple classes of tests, in order to derive stronger pseudorandomness properties related to more complex tests. In the setting of additive combinatorics, what is the minimal set of tests that primes have to satisfy in order to guarantee that they contain arithmetic progressions (or other structures)? For example, recent work of Conlon, Fox and Zhao shows that a “correlation condition” initially imposed in the work of Green and Tao is not necessary.

In complexity theory, most unconditional constructions of pseudorandom generators ultimately all rely on various combinations of four basic tools: k-wise independence, small-bias distributions, error-correcting codes, and random walks in expanders. The technical core of the analysis of known pseudorandom generators is to show that pseudorandomness against simple tests implies pseudorandomness against more complex tests (see for example Braverman’s theorem). Explicit constructions of pseudorandom objects have been essential to derandomize algorithms such as primality testing and undirected connectivity, and they have been applied in cryptography, distributed systems, complexity theory, streaming algorithms and learning theory. This workshop will explore unconditional constructions of pseudorandom objects at the frontier of progress, such as pseudorandom generators for small-space computations, small-depth circuits with modular gates, threshold circuits and DNFs.

Invited Participants:

Adi Akavia (Tel-Aviv Yaffo Academic College), Arnab Bhattacharyya (Indian Institute of Science), Abhishek Bhowmick (UT Austin), Pierre Bienvenu (Univeresity of Bristol), Thomas Bloom (University of Bristol), Julia Boettcher (London School of Economics), Andrej Bogdanov (The Chinese University of Hong Kong), Eshan Chattopadhyay (University of Texas at Austin), Xue Chen (University of Texas at Austin), Fan Chung (UC San Diego), David Conlon (University of Oxford), Anindya De (Northwestern University), Yevgeniy Dodis (NYU), Dean Doron (Tel Aviv University), Michael Forbes (Princeton University), Jacob Fox (Stanford University), Mrinalkanti Ghosh (Toyota Technological Institute at Chicago), Mika Göös (University of Toronto), Parikshit Gopalan (Microsoft Research), Ron Graham (UC San Diego), Ben Green (University of Oxford), Siyao Guo (The Chinese University of Hong Kong), Rohit Gurjar (Tel Aviv University), Venkat Guruswami (Carnegie Mellon University), Hamed Hatami (McGill University), Russell Impagliazzo (UCSD), Piotr Indyk (MIT), Maya Jacobine Stein (University of Chile), Valentine Kabanets (Simon Fraser University), Daniel Kane (UCSD), Adam Klivans (University of Texas at Austin), Yoshiharu Kohayakawa (University of Sao Paulo), Joonkyung Lee (University of Oxford), Fu Li (University of Texas at Austin), Miklos Lovasz (MIT), Zhenjian Lu (Simon Fraser University), Tomasz Luczak (Adam Mickiewicz University in Poznan), Freddie Manners (Stanford University), Abbas Mehrabian (University of British Columbia), Raghu Meka (UCLA), Dana Moshkovitz (University of Texas at Austin), Toni Pitassi (University of Toronto), Prasad Raghavendra (UC Berkeley), Omer Reingold (Stanford University), Luka Rimanic (University of Bristol), Vojtech Rodl (Emory University), Lisa Sauermann (Stanford University), Mathias Schacht (University of Hamburg), Rocco Servedio (Columbia University), Fernando Shao (University of Oxford), Asaf Shapira (Tel Aviv University), Amir Shpilka (Tel Aviv University), Olof Sisask (KTH Royal Institute of Technology), Jozef Skokan (London School of Economics), Nikhil Srivastava (UC Berkeley), Thomas Steinke (IBM Almaden), Li-Yang Tan (TTI-Chicago), Amnon Ta-Shma (Tel Aviv University), Caroline Terry (University of Illinois at Chicago), Luca Trevisan (UC Berkeley), Madhur Tulsiani (Toyota Technological Institute at Chicago), Jacques Verstraete (UC San Diego), Thomas Vidick (California Institute of Technology), Fan Wei (Stanford University), Ryan Williams (MIT), Julia Wolf (University of Bristol), Mary Wootters (Stanford University), Amir Yehudayoff (Technion Israel Institute of Technology), Yufei Zhao (University of Oxford), David Zuckerman (UT Austin)