Proving and Using Pseudorandomness

Program

Pseudorandomness

Location

Calvin Lab Auditorium

Date

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

Back to calendar

Click on the titles of individual talks for abstract, slides and archived video (if applicable).

9 – 9:20 a.m.

Coffee and Check-In

9:20 – 9:30 a.m.

Opening Remarks

9:30 – 10 a.m.

The Uncanny Usefulness of Constructive Proofs of Pseudorandomness

Valentine Kabanets, Simon Fraser University

10 – 10:30 a.m.

Approximately Counting Solutions to Systems of Quadratic Equations

Ryan Williams, MIT

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Pseudorandomness in Data Structures

Omer Reingold, Stanford University

12 – 2 p.m.

Lunch

2 – 3 p.m.

Packing Degenerate Graphs Using Pseudorandomness

Julia Böttcher, London School of Economics

3:10 – 3:40 p.m.

Regularity Inheritance in Pseudorandom Graphs

Maya Stein, University of Chile

3:40 – 4:10 p.m.

Break

4:10 – 4:40 p.m.

The Number of B_h-sets of a Given Cardinality

Yoshiharu Kohayakawa, University of,
S,
ã,
o,
Paulo

4:40 – 6 p.m.

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Removal Lemmas with Polynomial Bounds

Asaf Shapira, Tel-Aviv University

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Forcing Quasirandomness with Triangles

Mathias Schacht, University of Hamburg

12 – 2 p.m.

Lunch

2 – 3 p.m.

Explicit, Almost Optimal, Epsilon-Balanced Codes

Amnon Ta-Shma, Tel Aviv University

3:10 – 3:40 p.m.

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

Piotr Indyk, MIT

3:40 – 4:10 p.m.

Break

4:10 – 4:40 p.m.

Open Problem Session

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Preserving Randomness for Adaptive Adversaries

Adam Klivans, University of Texas, Austin

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Mixing Implies Lower Bounds for Space Bounded Learning

Dana Moshkovitz, University of Texas, Austin

12 – 2 p.m.

Lunch

2 – 3:30 p.m.

Free Afternoon

3:30 – 4 p.m.

Algorithmic Regularity Lemmas and Applications

László Miklós Lovász, MIT

4:10 – 5:10 p.m.

Linear-Algebraic Pseudorandomness: Subspace Designs and Dimension Expanders

Venkatesan Guruswami, Carnegie Mellon University

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Derandomizing "Algebraic RL"

Michael Forbes, Princeton University

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Deterministic Isolation for Bipartite Matching and Matroid Intersection

Rohit Gurjar, Tel Aviv University

11:40 a.m. – 12:10 p.m.

PRGs for Small Space via Fourier Analysis

Thomas Steinke, IBM Almaden

12:10 – 2 p.m.

Lunch

2 – 3 p.m.

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time

Li-Yang Tan, TTI Chicago

3:10 – 3:40 p.m.

Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas

Rocco Servedio, Columbia University

3:40 – 4:10 p.m.

Break

4:10 – 4:40 p.m.

Query-to-Communication Lifting for BPP

Mika Göös, University of Toronto

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Fast Permutation Property Testing and Metrics of Permutations

Fan Wei, Stanford University

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Randomness Intuition

Jacob Fox, Stanford University

12 – 2 p.m.

Lunch

2 – 3 p.m.

A Reduction from Efficient Non-Malleable Extractors to Low-Error Two-Source Extractors

Dean Doron, Tel Aviv University