南京大学：《概率与计算 Probability and Computing》课程教学资源（课件讲稿）random1

Probability Computing

Probability & Computing

Textbooks Probability and Computing andomired Alorithms and Probabilisic Analyis Michael Mitzenmacher and Eli Upfal. Michael Mitzenmacher Eli Upfal Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press,2005. WILEY THE PROBABILISTIC METHOD Third Edisiom Nogs Alon Alon and Spencer Joul H.speneer The Probabilistic Method

Textbooks Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Alon and Spencer The Probabilistic Method

n pennies are dropped at random on a carpet. ofr the probability that no two of them overlap? Gian-Carlo Rota 1-dimension:easy to solve (1932-1999) 2-dimension:nothing is known (1979)

Gian-Carlo Rota (1932-1999) n pennies are dropped at random on a carpet. the probability that no two of them overlap? 1-dimension: easy to solve 2-dimension: nothing is known (1979)

Polynomial Identity Testing (PIT) Input:two polynomials f,g EF[]of degree d Output:f=g? Input:a polynomial fF[z]of degree d Output: f三0？ fis given as black-box

Polynomial Identity Testing (PIT) Input: two polynomials f,g ￾ F[x] of degree d Output: f ￾ g? Input: a polynomial of degree d Output: f ￾ F[x] f ￾ 0? f is given as black-box

Input:a polynomial f eF]of degree d Output:f≡O? simple deterministic algorithm: check whether fx)=0 for all x{1,2,...,d+1) Fundamental Theorem of Algebra: A degree d polynomial has at most d roots. Randomized Algorithm pick a uniform random rES; S∈F check whether fr)=0;

simple deterministic algorithm: check whether f(x)=0 for all x ￾ {1, 2,...,d + 1} A degree d polynomial has at most d roots. Fundamental Theorem of Algebra: Randomized Algorithm pick a uniform random r ; check whether f(r) = 0 ; ∈S S ￾ F Input: a polynomial of degree d Output: f ￾ F[x] f ￾ 0?

Randomized Algorithm pick a uniform random rES; SCF check whether fr)=0; S1=2d f∫丰0 d Prf)=o】≤ 1 三 -2 Fundamental Theorem of Algebra: A degree d polynomial has at most d roots

A degree d polynomial has at most d roots. Fundamental Theorem of Algebra: Randomized Algorithm pick a uniform random r ; check whether f(r) = 0 ; ∈S S ￾ F if f ￾￾ 0 Pr[f(r) = 0] ￾ |S| d |S| = 2d = 1 2

Checking ldentity 北京 database 1 Are they identical? 上海 database 2

Checking Identity database 1 database 2 Are they identical? 北京 上海

Communication Complexity (Yao1979) f(a,b) #of bits communicated a b Han Meimei Li Lei EQ:{0,1}m×{0,1}m→{0,1} aa={ 1 a=b a夫b

Communication Complexity (Yao 1979) Han Meimei Li Lei EQ : {0, 1}n × {0, 1}n → {0, 1} # of bits communicated a b f(a, b) EQ(a, b) = ! 1 a = b 0 a ̸= b

Communication Complexity (Yao 1979) f(a,b) #of bits communicated a b Han Meimei Li Lei EQ:{0,1}m×{0,1}m→{0,1} Theorem(Yao,1979) There is no deterministic communication protocol solving EQ with less than n bits in the worst-case

Communication Complexity (Yao 1979) Han Meimei Li Lei EQ : {0, 1}n × {0, 1}n → {0, 1} # of bits communicated a b f(a, b) EQ(a, b) = ! 1 a = b There is no deterministic communication protocol 0 a ̸= b solving EQ with less than n bits in the worst-case. Theorem (Yao, 1979)

Communication Complexity m-1 m-1 f=】 r)=8(r)? 2=0 2=0 r,8(r) a∈{0,1}m b∈{0,1}n Han Meimei Li Lei by PIT: pick uniform 1 random r∈2n one-sided error≤ -2 of bit communicated: too large!

Communication Complexity Han Meimei Li Lei a ∈{0, 1} b n ∈{0, 1}n f = n ￾￾1 i=0 aixi pick uniform random r ∈[2n] r, g(r) f(r)=g(r) ? one-sided error ￾ 1 2 by PIT: # of bit communicated: too large! g = n X￾1 i=0 bixi