The Problem
l Cut sampling relied on Chernoff bound
l Chernoff bounds required that no one
edge is a large fraction of the
expectation of a cut it crosses
l If sample rate <<1/c, each edge across
a min-cut is too significant
But: if edge only crosses large cuts,
then sample rate <<1/c is OK!