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

Course Info 。尹一通 yitong.yin@gmail.com yinyt@nju.edu.cn 。office hour: 804,Thursday 2-4pm course homepage:http://tcs.nju.edu.cn/wiki

Course Info • 尹一通 yitong.yin@gmail.com yinyt@nju.edu.cn • office hour: 804, Thursday 2-4pm • course homepage: http://tcs.nju.edu.cn/wiki

Textbooks ITHMS Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press,1995. Probability and Computing tandomized Algorithms and Probabilistic Analysis Michael Mitzenmacher EhUp国 Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press,2005

Textbooks Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005

References 有件海世A3转：C时N CHAILE1年.BB6n k0NA10。v4n7 CLIFFOND STEIN CLRS Feller INTRODUCTION TO ALGORITHMS An Introduction to Probability Theory and Its Applications 生WLE到 Aldous and Fill Reversible Markov Chains and THE PROBABILISTIC Random Walks on Graphs HETHOD Third Editiee Alon and Spencer The Probabilistic Method

References CLRS Feller An Introduction to Probability Theory and Its Applications Aldous and Fill Reversible Markov Chains and Random Walks on Graphs Alon and Spencer The Probabilistic Method

Randomized Algorithms 'algorithms which use randomness in computation 44 Turing Machine random coin Why? Simpler. ● Faster. ● Can do impossibles. ● Can give us clever deterministic algorithms. ● Random input. ● Deterministic problem with random nature

“algorithms which use randomness in computation” Randomized Algorithms Why? • Simpler. • Faster. • Can do impossibles. • Can give us clever deterministic algorithms. • Random input. • Deterministic problem with random nature. • ... ... Turing Machine random coin

Checking Matrix Multiplication three nxn matrices A,B,C: A X B 是 C best matrix multiplication algorithm:O(n2.373)

Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: best matrix multiplication algorithm: O(n2.373)

Checking Matrix Multiplication three nxn matrices A,B,C: 3.0 na ve 兰 C 2.9 人 O(n) Strassen 2.8 PaⅫ Bini et al. 2.7 gorithm:O(n2.373) 2.6 Schonhage Romani 2.5 Coppersmith,Winograd Strassen 2.4 Coppersmith,Winograd Stothers Williams Year 1950 1960 1970 1980 1990 2000 2010

Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: best matrix multiplication algorithm: O(n￾) O(n2.373)

Checking Matrix Multiplication three nxn matrices A,B,C: A X B 是 C best matrix multiplication algorithm:O(n2.373) Freivald's Algorithm pick a uniform random r E0,1)"; check whether A(Br)=Cr; time:O(n2) if AB =C,always correct

best matrix multiplication algorithm: Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; time: O(n2) if AB = C, always correct O(n2.373)

Freivald's Algorithm pick a uniform random r∈{0，l"; check whether A(Br)=Cr; if AB =C,always correct ifAB≠C, letD=AB-C≠0n×n sayD,卡0 2n1 1 PABr-C1-PD.s 2 二 -2 m (Dr)i=>Dikrk =0 D r k=1 i ∑D >=D k≠j

Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; if AB = C, always correct if AB ≠ C, Pr[ABr = Cr] = Pr[Dr = 0] let D = AB ￾ C ￾= 0n￾n D r i (Dr)i = ￾ n k=1 Dikrk =0 rj = ￾ 1 Dij ￾ n k￾=j Dikrk 2n 2n￾1 = 1 2 say Dij ￾= 0 ￾

Freivald's Algorithm pick a uniform random r∈{0，l"; check whether A(Br)=Cr; if AB =C,always correct Theorem(Freivald,1979) IfAB≠C,for a uniformly random r∈{0,1n, 1 Pr[ABr=Cr]≤ repeat independently for 100 times time:O(n2) ifAB≠C,error probability≤2-1oo

Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; if AB = C, always correct If AB ⇥= C, for a uniformly random r ￾ {0, 1}n , Pr[ABr = Cr] ￾ 1 2 . Theorem (Freivald, 1979) repeat independently for 100 times time: O(n2) if AB ≠ C, error probability ≤ 2￾100

Monte Carlo ys Las Vegas Two types of randomized algorithms: Monte Carlo Las Vegas LAS VEGAS N E VA DA running time is fixed always correct correctness is random running time is random

Monte Carlo vs Las Vegas Monte Carlo Las Vegas running time is fixed correctness is random always correct running time is random Two types of randomized algorithms: