Playlist: 22 videos

Proving and Using Pseudorandomness

One theme of this workshop will be how to leverage weak pseudorandomness properties, fooling simple classes of tests, in order to derive stronger pseudorandomness properties related to more complex tests. In the setting of additive combinatorics...

0:49:46

Mixing Implies Lower Bounds for Space Bounded Learning

Dana Moshkovitz, University of Texas, Austin
https://simons.berkeley.edu/talks/dana-moshkovitz-2017-03-08
Proving and Using Pseudorandomness
Visit talk page
0:30:54

Algorithmic Regularity Lemmas and Applications

László Miklós Lovász, MIT
https://simons.berkeley.edu/talks/laszlo-miklos-lovasz-2017-03-08
Proving and Using Pseudorandomness
Visit talk page
0:59:55

Linear-Algebraic Pseudorandomness: Subspace Designs and Dimension Expanders

Venkatesan Guruswami, Carnegie Mellon University
https://simons.berkeley.edu/talks/venkatesan-guruswami-2017-03-08
Proving and Using Pseudorandomness
Visit talk page
0:59:44

Derandomizing "Algebraic RL"

Michael Forbes, Princeton University
https://simons.berkeley.edu/talks/michael-forbes-2017-03-09
Proving and Using Pseudorandomness
Visit talk page
0:32:57

Deterministic Isolation for Bipartite Matching and Matroid Intersection

Rohit Gurjar, Tel Aviv University
https://simons.berkeley.edu/talks/rohit-gurjar-2017-03-09
Proving and Using Pseudorandomness
Visit talk page
0:33:34

PRGs for Small Space via Fourier Analysis

Thomas Steinke, IBM Almaden
https://simons.berkeley.edu/talks/thomas-steinke-2017-03-09
Proving and Using Pseudorandomness
Visit talk page
0:34:35

Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas

Rocco Servedio, Columbia University
https://simons.berkeley.edu/talks/rocco-servedio-2017-03-09
Proving and Using Pseudorandomness
Visit talk page
0:28:40

Query-to-Communication Lifting for BPP

Mika Göös, University of Toronto
https://simons.berkeley.edu/talks/mika-goos-2017-03-09
Proving and Using Pseudorandomness
Visit talk page
0:49:14

Fast Permutation Property Testing and Metrics of Permutations

Fan Wei, Stanford University
https://simons.berkeley.edu/talks/fan-wei-2017-03-10
Proving and Using Pseudorandomness
Visit talk page
1:3:53

Randomness Intuition

Jacob Fox, Stanford University
https://simons.berkeley.edu/talks/jacob-fox-2017-03-10
Proving and Using Pseudorandomness
Visit talk page