Structure vs. Randomness

Program

Pseudorandomness

Location

Calvin Lab Auditorium

Date

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

Back to calendar

Click on the titles of individual talks for abstract, slides and archived video.

9 – 9:20 a.m.

Coffee and Check-In

9:20 – 9:30 a.m.

Opening Remarks

9:30 – 10 a.m.

Algorithmic Dense Model Theorems and Weak Regularity

Russell Impagliazzo, UC San Diego

10 – 10:30 a.m.

Sum of Squares Lower Bounds for Refuting Any CSP

Ryan O'Donnell, Carnegie Mellon University

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

What Can Infinity Tell Us about the Finite?

Maryanthe Malliaris, University of Chicago

12 – 2 p.m.

Lunch

2 – 3 p.m.

Large Deviations for Arithmetic Progressions

Yufei Zhao, University of Oxford

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

Trading Information Complexity for Error

Hamed Hatami, McGill University

4 – 4:30 p.m.

Sparse Dense Dichotomy and Liquid Graphs

Jarik Nesetril, Charles University

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

The Entropy Decrement Method and the Erdos Discrepancy Problem

Terry Tao, UCLA

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Vinogradov's Three Primes Theorem with Primes from Special Sets

Kaisa Matomäki, University of Turku

12 – 2 p.m.

Lunch

2 – 3 p.m.

Additive Structure of Sets of Fourier Coefficients

Thomas Bloom, University of Bristol

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

On Structural Properties of Low Threshold Rank Graphs

Shayan Oveis-Gharan, University of Washington

4 – 5 p.m.

Open Problem Session

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs

Laszlo Babai, University of Chicago

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs

Laszlo Babai, University of Chicago

12 – 2 p.m.

Lunch

2 – 3 p.m.

Random High-Dimensional Combinatorial Objects

Nati Linial, Hebrew University of Jerusalem

3 – 5 p.m.

Free Afternoon

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Positional Games and Randomness

Michael Krivelevich, Tel Aviv University

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

The Independence Number of the Birkhoff Polytope Graph, and Applications to Coding Theory

Shachar Lovett, UC San Diego

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

Partitioning to Sumsets Vs. Subspaces via Entropy Decrement

Kaave Hosseini, UC San Diego

2:30 – 3 p.m.

Tight Bounds for Arithmetic Progressions with Popular Common Differences in Dense Sets

Huy Pham, Stanford University

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

Outlaw Distributions and Locally Decodable Codes

Sivakanth Gopi, Princeton University

4 – 4:30 p.m.

Twenty (Simple) Questions (and Hitting Maximal Antichains)

Shay Moran, Simons Institute and UC San Diego

4:30 – 6 p.m.

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Unavoidable Patterns in Words

David Conlon, University of Oxford

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

True Complexity of Multilinear Systems

Freddie Manners, Stanford University