Overview
Syllabus
Intro
Overall Picture: Continuing From Part-2
Learning Parity with Noise BFKL 93, IPS 09 for some constant 8 € (0,1), and a prime modulus p.
PRGs in NC
What Structure? Computable using Bilinear Maps- Bilinear Maps Friendly.
Implausibility of Degree-2 PRGS BBKK 18, LV 18, BHJKS 19
Turning Point: "Degree-2.5" Integer PRGS A.JS 18, JLMS 19, AILMS 19 Input: An Integer vector
NEW! SPRG Overview Also degree 2.5, but boolean output!
SPRG: Simple Proof
Structured Seed PRG
How to Construct SPRG?
Key Intuition: Sparsity Helps SPRG Components
Correct T Errors (Failed First Attempt)
Problem: Can't Reveal BAD
Example: Correcting One Error
Correcting T =: Errors
Correcting T = Errors
What about Security?
Taught by
IEEE FOCS: Foundations of Computer Science