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!