 |
 |
22 of 32 |  |
 |
 |
MIT
Proof Idea
l
Use union bound
»
Chernoff: if expected cut size m, probability
of e
deviation at most exp(
-e²m/3)
l
Problem: exponentially many cuts.
»
Large deviation likely for some?
l
Solution: most cuts large
»
large deviation on them “exponentially rare”