YoVDO

Nearly Optimal Pseudorandomness From Hardness

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Cryptography Courses Theoretical Computer Science Courses Complexity Theory Courses Derandomization Courses

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 Complexity
Indian 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