Spring 2017

Structure vs. Randomness

Monday, Apr 10, 2017 to Friday, Apr 14, 2017 

Add to Calendar


Madhur Tulsiani (Toyota Technological Institute at Chicago; chair), Jacob Fox (Stanford University), Shachar Lovett (UC San Diego), Tom Sanders (University of Oxford)
This workshop focuses on a phenomenon observed in harmonic analysis, ergodic theory, analytic number theory, graph theory, complexity theory, additive combinatorics and cryptography, according to which arbitrary objects can be well approximated by a combination of a small number of pseudorandom objects. In the study of higher-order Fourier analysis, this corresponds to approximating every function by a combination of structured functions plus a function of small Gowers norm; in graph theory it corresponds to Szemeredi’s regularity lemma; in cryptography it corresponds to approximating distributions dominated by a pseudorandom distribution by distributions of high min-entropy; and so on.
The workshop brings together researchers working on such decomposition results in different areas and with different motivations, who often use technically similar methods.

Visit the schedule page link above for the archived videos. 

Invited Participants: 

Laci Babai (University of Chicago), Arnab Bhattacharyya (Indian Institute of Science), Abhishek Bhowmick (UT Austin), Pierre Bienvenu (University of Bristol), Thomas Bloom (University of Bristol), Andrej Bogdanov (The Chinese University of Hong Kong),  Jop Briët (CWI), Eshan Chattopadhyay (Institute for Advanced Study), Xue Chen (University of Texas at Austin), Fan Chung (UC San Diego), David Conlon (University of Oxford), Michael Forbes (Princeton University), Jacob Fox (Stanford University), Mika Göös (University of Toronto), Parikshit Gopalan (Microsoft Research), Ron Graham (UC San Diego), Siyao Guo (New York University), Hamed Hatami (McGill University), Kaave Hosseini (UC San Diego), Russell Impagliazzo (UC San Diego), Valentine Kabanets (Simon Fraser University), Michael Krivelevich (Tel Aviv University), James Lee (University of Washington), Joonkyung Lee (University of Oxford), Fu Li (University of Texas at Austin), Nati Linial (Hebrew University of Jerusalem), Laszlo Miklos Lovasz (MIT), Shachar Lovett (UC San Diego), Zhen Jian Lu (Simon Fraser University), Maryanthe Malliaris (University of Chicago), Freddie Manners (Stanford University), Kaisa Matomäki (University of Turku), Abbas Mehrabian (University of British Columbia), Raghu Meka (UCLA), Jaroslav Nešetřil (Charles University), Ryan O'Donnell (Carnegie Mellon University), Shayan Oveis Gharan (University of Washington), Toni Pitassi (University of Toronto), Sean Prendiville (University of Manchester), Prasad Raghavendra (UC Berkeley), Sasha Razborov (University of Chicago), Omer Reingold (Stanford University), Luka Rimanic (University of Bristol), Mike Saks (Rutgers University), Tom Sanders (University of Oxford), Lisa Sauermann (Stanford University), Fernando Shao (University of Oxford), Asaf Shapira (Tel Aviv University), Amir Shpilka (Tel Aviv University), Nikhil Srivastava (UC Berkeley), Thomas Steinke (IBM Almaden), Terry Tao (UCLA), Amnon Ta-Shma (Tel Aviv University), Caroline Terry (University of Illinois at Chicago), Luca Trevisan (UC Berkeley), Madhur Tulsiani (Toyota Technological Institute at Chicago), Thomas Vidick (California Institute of Technology), Fan Wei (Stanford University), 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)