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

Applied Cryptography
University of Virginia via Udacity
Cryptography II
Stanford University via Coursera
Coding the Matrix: Linear Algebra through Computer Science Applications
Brown University via Coursera
Cryptography I
Stanford University via Coursera
Unpredictable? Randomness, Chance and Free Will
National University of Singapore via Coursera