Opening Epsilon-Biased Generators
Epsilon-Biased Generators
- Length
- 23 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Definition of epsilon biased generators
Epsilon-biased generators stretch a short random seed into a long bitstring whose parity under every non-zero linear function over is within of fair. O'Donnell defines the notion, then applies it to Freivalds' algorithm, which checks a claimed matrix product in quadratic time using a random vector. Generator output replaces that vector and cuts the random bits needed. Stacking the outputs as matrix columns turns small bias into large minimum distance of a linear code. Constructions then combine standard coding-theory techniques, including Hadamard codes, with the seed length of Alon, Goldreich, Håstad and Peralta. Part of CMU 15-750, the session assumes linear algebra over and basic coding theory.

Your comment is kept while you sign up.Sign in
Shows that an epsilon-biased generator and a binary linear code with large minimum distance are the same object.
Epsilon-biased generators stretch a short random seed into a long bitstring whose parity under every non-zero linear function over is within of fair. O'Donnell defines the notion, then applies it to Freivalds' algorithm, which checks a claimed matrix product in quadratic time using a random vector. Generator output replaces that vector and cuts the random bits needed. Stacking the outputs as matrix columns turns small bias into large minimum distance of a linear code. Constructions then combine standard coding-theory techniques, including Hadamard codes, with the seed length of Alon, Goldreich, Håstad and Peralta. Part of CMU 15-750, the session assumes linear algebra over and basic coding theory.
Naor and Naor
Alon, Goldreich, Håstad, and Peralta
Ta-Shma
This lecture
Lecture 38 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.