Opening k-wise Independent Generators
k-wise Independent Generators
- Length
- 26 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Definitions and properties of k-wise independence
A k-wise independent pseudorandom generator stretches an -bit seed into an -bit string whose every output positions are exactly uniform. O'Donnell states the definition, flags the misleading names attached to it, and notes that a seed of order bits suffices. A random partition cuts half the edges of any graph in expectation, and pairwise independence is enough for that argument, which derandomizes the Max-Cut algorithm. Variance of a sum is unchanged under pairwise independence, so Chebyshev bounds carry over. The construction comes from linear codes, where generator-matrix columns are k-wise linearly independent when the dual code has large minimum distance.
Your comment is kept while you sign up.Sign in
Derandomizes the half-the-edges Max-Cut algorithm with pairwise independent bits, built from dual codes.
A k-wise independent pseudorandom generator stretches an -bit seed into an -bit string whose every output positions are exactly uniform. O'Donnell states the definition, flags the misleading names attached to it, and notes that a seed of order bits suffices. A random partition cuts half the edges of any graph in expectation, and pairwise independence is enough for that argument, which derandomizes the Max-Cut algorithm. Variance of a sum is unchanged under pairwise independence, so Chebyshev bounds carry over. The construction comes from linear codes, where generator-matrix columns are k-wise linearly independent when the dual code has large minimum distance.
This lecture
Lecture 37 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.