MIT
109
Few Samples Needed
lSuppose k
clauses
lThen
E[sample]
> 1/k
»1
£ satisfied clauses £ k
»1
³
sample value ³ 1/k
lAdding
O(k log n / e2) samples gives “large”
mean
lSo
Chernoff says sample mean is probably
good estimate