Definition: Events E1,E2,...,En are mutually independent if for any subset I C {1,2,...,n}, Pr[∧ere=ier Pr[E. Definition: Random variables X1,X2,...,Xn are mutually independent if for any subset I cn and any values xi,where i∈I, Pr[八er(X&=c)】=IΠ∈rPr[X=xl:
Definition: Random variables X1, X2,...,Xn are mutually independent if for any subset I [n] and any values xi, where i ⇥ I, Pr ⌅ iI (Xi = xi) ⇥ = ⇤ iI Pr[Xi = xi]. Definition: Events E1, E2,..., En are mutually independent if for any subset I {1, 2,...,n}, Pr ⌅ iI Ei ⇥ = ⇤ iI Pr[Ei]
k-wise Independence Definition: Events E1,E2,...,En are k-wise independent if for any subset IC {1,2,...,n},with I<k Pr[ΛMEI E=ΠiEI Pr[E: Definition: Random variables X1,X2,...,Xn are k-wise in- dependent if for any subset I cn and any val- ues zi,where i∈I,with I|≤k Pr AieI(Xi=i)=Iier Pr[Xi =i]. pairwise:2-wise
Definition: Definition: k-wise Independence with |I| k with |I| k pairwise: 2-wise Random variables X1, X2,...,Xn are k-wise independent if for any subset I ⇢ [n] and any values xi, where i 2 I, Pr ⇥V i2I (Xi = xi) ⇤ = Q i2I Pr[Xi = xi]. Events E1, E2,..., En are k-wise independent if for any subset I ✓ {1, 2,...,n}, Pr ⇥V i2I Ei ⇤ = Q i2I Pr[Ei]
2-wise Independent Bits uniform independent bits: (random source) X1,X2,.,Xm∈{0,1} Goal:2-wise independent uniform bits: Yi,Y2,.,Yn∈{0,1} n> m C b ⊕b a nonempty subsets: 0 0 0≠S1,S2,,S2m-1C{1,2,.,m} 0 1 1 1 0 1 y=⊕X 1 1 0 iESj
2-wise Independent Bits uniform & independent bits: X1, X2,...,Xm 2 {0, 1} (random source) Goal: 2-wise independent uniform bits: Y1, Y2,...,Yn 2 {0, 1} n m 0 0 0 0 1 1 1 0 1 1 1 0 a b a b S1, S2,...,S2m1 ✓ {1, 2,...,m} nonempty subsets: ; 6= Yj = M i2Sj Xi
uniform independent bits:X1,X2,...,XmE 10,1} nonempty subsets:S1,$2,...,S2m-1 {1,2,...,m} Y=①X iESj 2-wise independent uniform bits: Y1,Y2,.,Y2m-1∈{0,1 log2 n total random bits n-1 pairwise independent bits
X1, X2,...,Xm 2 {0, 1} nonempty subsets: S1, S2,...,S2m1 ✓ {1, 2,...,m} uniform & independent bits: Yj = M i2Sj Xi Y1, Y2,...,Y2m1 2 {0, 1} 2-wise independent uniform bits: log2 n total random bits n-1 pairwise independent bits
Max-Cut partition Vinto two parts: S and T ● maximize the cut IC(S,T)I ●NP-hard 0.878~-approximation in poly-time by SDP easy 0.5-approximation C(S,T)={uw∈E|u∈S and v∈T}
T S Max-Cut • partition V into two parts: S and T • maximize the cut |C(S,T)| • NP-hard • 0.878~-approximation in poly-time by SDP • easy 0.5-approximation C(S, T) = {uv E | u S v T}