Program

Spring 2017

# Pseudorandomness

Jan. 10–May 12, 2017

What does it mean for a fixed object to be “random-like”? Is it possible to turn existence proofs that use the probabilistic method into explicit constructions? Is it possible to simulate randomized algorithms deterministically? When can heuristic arguments that treat the primes as a random set of integers be turned into rigorous proofs?

Notions of pseudorandomness and quasirandomness have been developed and investigated in several areas of theoretical computer science, combinatorics and number theory (including complexity theory, cryptography, graph theory, additive combinatorics and analytic number theory) to answer such questions. At a very high level, the appeal of such notions is that one can easily prove that certain properties are true for random objects, using probabilistic methods, and then transfer such properties to pseudorandom objects, provided that the pseudorandomness “fools” the probabilistic techniques.

These different research communities have developed, independently, different concepts of pseudorandomness, and different technical approaches to proving that specific objects are pseudorandom. In the past, interactions between these communities have led to unified ways of thinking about such definitions and techniques, and new ideas were enabled by such unified views. Recently, there have been a number of breakthroughs in the areas to be covered by this program, for example in the construction of expanders and extractors, or the understanding of pseudorandomness properties of the primes. Other areas are ripe for the next breakthrough, for example the construction of complexity-theoretic pseudorandom generators, or a better quantitative understanding of higher-order non-uniformity over finite fields.

The goal of the semester, which will gather researchers in theoretical computer science, combinatorics and number theory, is threefold: to make recent ideas more broadly understood beyond the community in which they originated; to make a concerted effort toward the long-standing open problems in this area; and to explore new questions generated during the program by the interaction between different communities. In addition, concurrently with this program MSRI will be hosting two semester-long programs with a thematic connection, on Analytic Number Theory (http://www.msri.org/programs/297 ) and Harmonic Analysis (http://www.msri.org/programs/300 ). We expect there to be fruitful interactions and synergies between all three programs.

## Organizers:

Julia Wolf
(University of Bristol; chair),
Jacob Fox
(Stanford University),
Ben Green
(University of Oxford),
Russell Impagliazzo
(UC San Diego),
Luca Trevisan
(Simons Institute, UC Berkeley),
David Zuckerman
(University of Texas, Austin)

## Long-Term Participants (including Organizers):

Noga Alon
(Tel Aviv University),
Eli Ben-Sasson
(Technion Israel Institute of Technology),
Arnab Bhattacharyya
(Indian Institute of Science),
Andrej Bogdanov
(Chinese University of Hong Kong),
Jop Briët
(CWI; Visiting Scientist),
Fan Chung
(UC San Diego),
David Conlon
(University of Oxford),
Anindya De
(Northwestern University),
Yevgeniy Dodis
(New York University),
Jacob Fox
(Stanford University),
Ben Green
(University of Oxford),
Russell Impagliazzo
(UC San Diego),
Valentine Kabanets
(Simon Fraser University),
Daniel Kane
(UC San Diego),
Xin Li
(Johns Hopkins University),
Shachar Lovett
(UC San Diego),
Freddie Manners
(Stanford University),
Toni Pitassi
(University of Toronto),
Sean Prendiville
(University of Manchester),
Prasad Raghavendra
(UC Berkeley),
Omer Reingold
(Stanford University),
Amin Saberi
(Stanford University),
Michael Saks
(Rutgers University),
Tom Sanders
(University of Oxford),
Xuancheng Shao
(University of Oxford),
Amir Shpilka
(Tel Aviv University),
Olof Sisask
(KTH Royal Institute of Technology),
Nikhil Srivastava
(UC Berkeley),
Thomas Steinke
(IBM Almaden),
Amnon Ta-Shma
(Tel Aviv University),
Luca Trevisan
(Simons Institute, UC Berkeley),
Madhur Tulsiani
(Toyota Technological Institute at Chicago),
Thomas Vidick
(California Institute of Technology; Visiting Scientist),
Avi Wigderson
(Institute for Advanced Study, Princeton),
Julia Wolf
(University of Bristol; chair),
Mary Wootters
(Stanford University),
David Zuckerman
(University of Texas, Austin)

## Research Fellows:

Thomas Bloom
(University of Bristol),
Eshan Chattopadhyay
(Institute for Advanced Study, Princeton; Microsoft Research Fellow),
Michael Forbes
(Princeton University),
Mika Göös
(University of Toronto),
Siyao Guo
(New York University),
Abbas Mehrabian
(University of British Columbia),
Caroline Terry
(University of Maryland),
Yufei Zhao
(University of Oxford)

## Visiting Graduate Students and Postdocs:

Pierre Bienvenu
(University of Bristol),
Xue Chen
(University of Texas, Austin),
Dean Doron
(Tel Aviv University),
Mrinalkanti Ghosh
(Toyota Technological Institute at Chicago),
Kaave Hosseini
(UC San Diego),
Joonkyung Lee
(University of Oxford),
Fu Li
(University of Texas, Austin),
Laszlo Miklos Lovasz
(Massachusetts Institute of Technology),
Zhenjian Lu
(Simon Fraser University),
Jarrod Millman
(UC Berkeley),
Luka Rimanic
(University of Bristol),
Lisa Sauermann
(Stanford University),
Fan Wei
(Stanford University)

## Workshops

Tuesday, Jan. 17–Friday, Jan. 20, 2017

## Organizers:

Jacob Fox
(Stanford University),
Ben Green
(University of Oxford),
Russell Impagliazzo
(UC San Diego),
Luca Trevisan
(Simons Institute, UC Berkeley),
Julia Wolf
(University of Bristol),
David Zuckerman
(University of Texas, Austin)

Monday, Jan. 30–Friday, Feb. 3, 2017

## Organizers:

Noga Alon
(Tel Aviv University; chair),
Ben Green
(University of Oxford),
Peter Sarnak
(Princeton University),
David Zuckerman
(University of Texas, Austin)

Monday, Mar. 6–Friday, Mar. 10, 2017

## Organizers:

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

Monday, Apr. 10–Friday, Apr. 14, 2017

## Organizers:

Madhur Tulsiani
(Toyota Technological Institute at Chicago; chair),
Jacob Fox
(Stanford University),
Shachar Lovett
(UC San Diego),
Tom Sanders
(University of Oxford)

Monday, Jun. 18–Thursday, Jun. 21, 2018

## Organizers:

Julia Wolf
(University of Bristol; chair),
Jacob Fox
(Stanford University),
Ben Green
(University of Oxford),
Russell Impagliazzo
(UC San Diego),
Luca Trevisan
(Simons Institute, UC Berkeley),
David Zuckerman
(University of Texas, Austin)

Program image: "Πseudorandomness" by Luca Trevisan. (Binary expansion of π.)