MIT
45
Proof of Sampling: Idea
lChernoff
bound says probability of large deviation in cut value is
small
lProblem: exponentially many
cuts. Perhaps some
deviate a great deal
lSolution: showed few small
cuts
»only
small cuts likely to deviate much
»but
few, so Chernoff bound applies