MIT
43
Sampling Theorem
lGiven graph G,
build a sample G(p) by
including each edge with probability p
lCut of value v in
G has
expected value pv
in G(p)
lDefinition: “constant” r = 8 (ln n) / e2
lTheorem: With high probability,
all exponentially many
cuts in G(r / c) have (1 ± e) times their
expected values.