南京大学：《随机算法 Randomized Algorithms》课程教学资源（课件讲稿）Universal Hashing

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 ￾⌅ i￾I (Xi = xi) ⇥ = ⇤ i￾I Pr[Xi = xi]. Definition: Events E1, E2,..., En are mutually independent if for any subset I ￾ {1, 2,...,n}, Pr ￾⌅ i￾I Ei ⇥ = ⇤ i￾I 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 in￾dependent if for any subset I ⇢ [n] and any val￾ues 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,...,S2m￾1 ✓ {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,...,S2m￾1 ✓ {1, 2,...,m} uniform & independent bits: Yj = M i2Sj Xi Y1, Y2,...,Y2m￾1 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}

Random Cut for each vertex v∈V uniform independent Ye0,1} Y,=1 v∈S Y,=0> v∈T for each edge uv∈E Yu卡Yw IC(S,T)=>Yu )Yu=Yo uU∈D OPT EIC(S,T)川=>PY≠Y] 2 2 uw∈E

for each vertex v 2 V uniform & independent v 2 S v 2 T Yv 2 {0, 1} Yv = 1 Yv = 0 Yuv = ( 1 Yu 6= Yv 0 Yu = Yv for each edge uv 2 E |C(S, T)| = X uv2E Yuv E[|C(S, T)|] = X uv2E Pr[Yu 6= Yv] = |E| 2 ￾ OPT 2 Random Cut

Random Cut for each vertex v∈V uniform 2-wise independent YE 10,1} Yo=1> v∈S Y=0> v∈T for each edge uv∈E Yu卡Yw IC(S,T)=>Yu )Yu=Yo uU∈D E OPT EIC(S,T)川=>PY≠Y] 2 2 uw∈E

Random Cut for each vertex v 2 V uniform & 2-wise independent v 2 S v 2 T Yv 2 {0, 1} Yv = 1 Yv = 0 Yuv = ( 1 Yu 6= Yv 0 Yu = Yv for each edge uv 2 E |C(S, T)| = X uv2E Yuv E[|C(S, T)|] = X uv2E Pr[Yu 6= Yv] = |E| 2 ￾ OPT 2

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!

2-wise Independent Variables random source:uniform and independent Xo,X1∈[p Goal:uniform and 2-wise independent Yo,i,.,Yp-1∈p prime p fori∈[pl Y=(Xo+i·X1)modp uniformity:i,a∈[p] Pr[Y:a] 2-wise independence: i卡j,a,b∈[p 1 Pr[Y=a∧Y)=b= p2

2-wise Independent Variables Goal: uniform and 2-wise independent 2 [p] prime p random source: uniform and independent X0, X1 2 [p] for i 2 [p] Yi = (X0 + i · X1) mod p Y0, Y1,...,Yp￾1 uniformity: 8i, a 2 [p] Pr[Yi = a] = 1 p 2-wise independence: 8i 6= j, a, b 2 [p] Pr[Yi = a ^ Yj = b] = 1 p2

uniform and independent Xo,XIE[p] fori∈[p] Y=(Xo+i·X1)modp uniformity:Y i,a∈pl PrYi=a =Pr[(Xo+i·X1)modp=a =>Pr[X1=j]Pr [(Xo+ij)modp=a] j∈[p] ∑Pr[Xo=(a-i)(mod p)] j∈[p] 1 p

for i 2 [p] Yi = (X0 + i · X1) mod p uniformity: 8i, a 2 [p] uniform and independent X0, X1 2 [p] Pr[Yi = a] = Pr [(X0 + i · X1) mod p = a] = X j2[p] Pr[X1 = j] · Pr [(X0 + ij) mod p = a] = 1 p X j2[p] Pr [X0 ⌘ (a ￾ ij) (mod p)] = 1 p