MIT
111
Focus on Small Cuts
lFact: FAIL(p) > pc
lTheorem: if pc=1/n(2+d) thenPr[>a-mincut fails]< n-ad
lCorollary: FAIL(p) » Pr[£ a-mincut
fails],
where a=1+2/d
lRecall: O(n2a) a-mincuts
lEnumerate with
RCA, run DNF counting