Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Nearly Optimal Pseudorandomness From Hardness

IEEE via YouTube

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

Reviews

Start your review of Nearly Optimal Pseudorandomness From Hardness

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.