Derandomization for each vertex v∈V uniform&2-wise independent Yo∈{0，ly Y=1 v∈S Y=0> v∈T for each edge uv∈E EIC(S,T)川=>Pr[Yu≠Y= E OPT 2 2 uU∈E V={1,2,,vn} Y,Yv2,...,Yvm constructed from log2(n+1)]bits try all 2()=O(n2)possibilities!Derandomization for each vertex v 2 V uniform & 2-wise independent v 2 S v 2 T Yv 2 {0, 1} Yv = 1 Yv = 0 for each edge uv 2 E E[|C(S, T)|] = X uv2E Pr[Yu 6= Yv] = |E| 2 ￾ OPT 2 V = {v1, v2,...,vn} Yv1 , Yv2 ,...,Yvn constructed from dlog bits 2(n + 1)e try all 2dlog2(n+1)e = O(n2) possibilities!