PRGs for Small Space via Fourier Analysis

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=B9Q6cPgZ6nA


Duration: 33:34
275 views
3

Thomas Steinke, IBM Almaden
https://simons.berkeley.edu/talks/thomas-steinke-2017-03-09
Proving and Using Pseudorandomness



Other Videos By Simons Institute for the Theory of Computing


2017-03-27Representations for Language: From Word Embeddings to Sentence Meanings
2017-03-27A Non-generative Framework and Convex Relaxations for Unsupervised Learning
2017-03-27Geometry, Optimization and Generalization in Multilayer Networks
2017-03-24Understanding Silicon Valley
2017-03-16The Contextual Bandits Problem
2017-03-10A Reduction from Efficient Non-Malleable Extractors to Low-Error Two-Source Extractors
2017-03-10Randomness Intuition
2017-03-10Fast Permutation Property Testing and Metrics of Permutations
2017-03-09Query-to-Communication Lifting for BPP
2017-03-09Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas
2017-03-09PRGs for Small Space via Fourier Analysis
2017-03-09Deterministic Isolation for Bipartite Matching and Matroid Intersection
2017-03-09Derandomizing "Algebraic RL"
2017-03-08Linear-Algebraic Pseudorandomness: Subspace Designs and Dimension Expanders
2017-03-08Algorithmic Regularity Lemmas and Applications
2017-03-08Mixing Implies Lower Bounds for Space Bounded Learning
2017-03-08Preserving Randomness for Adaptive Adversaries
2017-03-07Explicit, Almost Optimal, Epsilon-Balanced Codes
2017-03-07Forcing Quasirandomness with Triangles
2017-03-07Removal Lemmas with Polynomial Bounds
2017-03-06The Number of B_h-sets of a Given Cardinality


Tags:
Proving and Using Pseudorandomness
Thomas Steinke
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley