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

Approximation Algorithms Part I
École normale supérieure via Coursera
Approximation Algorithms Part II
École normale supérieure via Coursera
Automata Theory
Stanford University via edX
Computation in Complex Systems
Santa Fe Institute via Complexity Explorer
Computing: Art, Magic, Science
ETH Zurich via edX