Nearly Optimal Pseudorandomness From Hardness
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 26-minute IEEE conference talk on derandomization and pseudorandom generators. Delve into the nearly optimal pseudorandomness derived from hardness, presented by researchers from Stanford University and the University of Texas at Austin. Learn about the general approach to derandomization, the STV011-bit stretch, and a new approach using codes with large alphabets. Understand concepts such as pseudoentropy, locally list recoverable codes, and extracting from pseudoentropy. Conclude with open questions in this fascinating area of computational complexity theory.
Syllabus
Intro
Introduction: Derandomization
Randomized vs. Deterministic Time Example
General Approach to Derandomization: Pseudorandom Generators
Parameter Overview
Jumping Off Point: STV01
1-Bit Stretch
New Approach: Codes with Large Alphabet
A Notion of Pseudoentropy
Definition of Locally List Recoverable Codes
Pseudoentropy from LLRC
Extracting from Pseudoentropy
Conclusion
Open Questions
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
Randomized Methods in ComplexityIndian Institute of Technology Kanpur via Swayam Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
Institute for Advanced Study via YouTube Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit
Ryan O'Donnell via YouTube Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube High-Precision Estimation of Random Walks in Small Space
IEEE via YouTube