This course covers the learning outcomes and goals of understanding nearly optimal pseudorandomness from hardness. It teaches the skills of derandomization, pseudorandom generators, pseudoentropy, and extracting from pseudoentropy. The teaching method includes lectures on topics such as randomized vs. deterministic time, codes with a large alphabet, and locally list recoverable codes. The intended audience for this course is individuals interested in theoretical computer science, cryptography, and complexity theory.
Overview
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
