MIT
114
Algorithm
lRCA can enumerate all a-minimum
cuts with high probability in O(n2a) time.
lGiven a-minimum
cuts, can e-estimate
probability one fails via Monte Carlo simulation
for DNF-counting (formula size O(n2a))
lCorollary: when FAIL(p)< n-(2+d), can
e-approximate it in O (cn2+4/d) time
e-approximate it in O (cn2+4/d) time