Workshops

Spring 2017

Proving and Using Pseudorandomness

Mar 6, 2017 to Mar 10, 2017

Return to event »

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

Monday, March 6th, 2017
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Opening Remarks
9:30 am–10:00 am		The Uncanny Usefulness of Constructive Proofs of Pseudorandomness Valentine Kabanets, Simon Fraser University
10:00 am–10:30 am		Approximately Counting Solutions to Systems of Quadratic Equations Ryan Williams, MIT
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Pseudorandomness in Data Structures Omer Reingold, Stanford University
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Packing Degenerate Graphs Using Pseudorandomness Julia Böttcher, London School of Economics
3:10 pm–3:40 pm		Regularity Inheritance in Pseudorandom Graphs Maya Stein, University of Chile
3:40 pm–4:10 pm		Break
4:10 pm–4:40 pm		The Number of B_h-sets of a Given Cardinality Yoshiharu Kohayakawa, University of S ã o Paulo
4:40 pm–6:00 pm		Reception

Tuesday, March 7th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Removal Lemmas with Polynomial Bounds Asaf Shapira, Tel-Aviv University
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Forcing Quasirandomness with Triangles Mathias Schacht, University of Hamburg
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Explicit, Almost Optimal, Epsilon-Balanced Codes Amnon Ta-Shma, Tel Aviv University
3:10 pm–3:40 pm		Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform Piotr Indyk, MIT
3:40 pm–4:10 pm		Break
4:10 pm–4:40 pm		Open Problem Session

Wednesday, March 8th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Preserving Randomness for Adaptive Adversaries Adam Klivans, University of Texas, Austin
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Mixing Implies Lower Bounds for Space Bounded Learning Dana Moshkovitz, University of Texas, Austin
12:00 pm–2:00 pm		Lunch
2:00 pm–3:30 pm		Free Afternoon
3:30 pm–4:00 pm		Algorithmic Regularity Lemmas and Applications László Miklós Lovász, MIT
4:10 pm–5:10 pm		Linear-Algebraic Pseudorandomness: Subspace Designs and Dimension Expanders Venkatesan Guruswami, Carnegie Mellon University

Thursday, March 9th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Derandomizing "Algebraic RL" Michael Forbes, Princeton University
10:30 am–11:00 am		Break
11:00 am–11:30 am		Deterministic Isolation for Bipartite Matching and Matroid Intersection Rohit Gurjar, Tel Aviv University
11:40 am–12:10 pm		PRGs for Small Space via Fourier Analysis Thomas Steinke, IBM Almaden
12:10 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time Li-Yang Tan, TTI Chicago
3:10 pm–3:40 pm		Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas Rocco Servedio, Columbia University
3:40 pm–4:10 pm		Break
4:10 pm–4:40 pm		Query-to-Communication Lifting for BPP Mika Göös, University of Toronto

Friday, March 10th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Fast Permutation Property Testing and Metrics of Permutations Fan Wei, Stanford University
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Randomness Intuition Jacob Fox, Stanford University
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		A Reduction from Efficient Non-Malleable Extractors to Low-Error Two-Source Extractors Dean Doron, Tel Aviv University