Opening Expander Graph Application 2: Derandomization
Expander Graph Application 2: Derandomization
- Length
- 23 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Derandomization with expander graphs reduces the error of a randomized algorithm without spending more random bits. O'Donnell starts from a decision algorithm with one-sided error that uses random bits. Here independent repetitions cut the error exponentially but cost times as many bits. Replacing the independent strings with the neighbours of a strongly explicit bipartite expander keeps the cost at bits and bounds the failure probability by . The proof rests on vertex expansion and on computing neighbourhoods in polynomial time. A closing remark sketches how a random walk on a regular expander gives exponential error decay with bits.

Your comment is kept while you sign up.Sign in
Runs a one-sided-error algorithm on a bipartite expander's neighbours, cutting error to on random bits.
Derandomization with expander graphs reduces the error of a randomized algorithm without spending more random bits. O'Donnell starts from a decision algorithm with one-sided error that uses random bits. Here independent repetitions cut the error exponentially but cost times as many bits. Replacing the independent strings with the neighbours of a strongly explicit bipartite expander keeps the cost at bits and bounds the failure probability by . The proof rests on vertex expansion and on computing neighbourhoods in polynomial time. A closing remark sketches how a random walk on a regular expander gives exponential error decay with bits.
This lecture
Lecture 51 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.