Opening Hardness Amplification
Hardness Amplification
- Length
- 1 h 19 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 8: Before the lecture
Proves Impagliazzo's hard-core set theorem with von Neumann's minimax theorem, then derives Yao's XOR lemma from it.
Hardness amplification turns a mildly hard function into one that small circuits can barely beat a coin flip on. O'Donnell, in session 26 of CMU 15-855, states Yao's XOR lemma, which takes the parity of over several independent inputs. The hard-core intuition says mild hardness means hopelessness on a small fraction of inputs; Impagliazzo's hard-core set theorem makes this precise and yields the lemma by contraposition. The theorem's proof recasts hardness with smooth -distributions as a zero-sum game, applies the minimax theorem, and polls sampled circuits by majority, as in boosting. The material assumes circuit complexity, Chernoff bounds and basic game theory.
Hardness amplification turns a mildly hard function into one that small circuits can barely beat a coin flip on. O'Donnell, in session 26 of CMU 15-855, states Yao's XOR lemma, which takes the parity of over several independent inputs. The hard-core intuition says mild hardness means hopelessness on a small fraction of inputs; Impagliazzo's hard-core set theorem makes this precise and yields the lemma by contraposition. The theorem's proof recasts hardness with smooth -distributions as a zero-sum game, applies the minimax theorem, and polls sampled circuits by majority, as in boosting. The material assumes circuit complexity, Chernoff bounds and basic game theory.
Pallo's paper
This lecture
Lecture 26 of 27 of Graduate Computational Complexity Theory.
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.
Your comment is kept while you sign up.Sign in