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?