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