CSC3160: Design and Analysis of Algorithms Week 4: Randomized Algorithms Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Randomized Algorithms -We use randomness in our algorithms. You've seen examples in previous courses quick sort:pick a random pivot. We'll see more in this week. 2
Randomized Algorithms ◼ We use randomness in our algorithms. ◼ You’ve seen examples in previous courses ❑ quick sort: pick a random pivot. ◼ We’ll see more in this week. 2
Motivation Why randomness? Faster. Simpler. Price:a nonzero error probability Usually can be controlled to arbitrarily small. Repeating k times drops the error probability to c-k for some constant c>1. Second part of the lecture. 3
Motivation ◼ Why randomness? ❑ Faster. ❑ Simpler. ◼ Price: a nonzero error probability ❑ Usually can be controlled to arbitrarily small. ❑ Repeating 𝑘 times drops the error probability to 𝑐 −𝑘 for some constant 𝑐 > 1. ◼ Second part of the lecture. 3
General references RANDOMIZED Randomized Algorithms, LGORITHMS Rajeev Motwani and Prabhakar Raghavan,Cambridge University Press,1995. Probability and Computing, Probabitity and Computing Eotni pvelas mttobkaene boeh Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005. 4
General references ◼ Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995. ◼ Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005. 4
Part 1:Examples Example 1:Polynomial ldentity Testing 5
Part 1: Examples Example 1: Polynomial Identity Testing 5
Question ■( Given two polynomials pi and p2(by arithmetic circuit),decide whether they are equal. Arithmetic circuit: polynomial computed: (x1x2+X2x3)(x2+x4)-(x3-x5) X1 X2 X3 X4 X5 ■( Question:Given two such circuits,do they compute the same polynomial? 6
Question ◼ Given two polynomials 𝑝1 and 𝑝2 (by arithmetic circuit), decide whether they are equal. ◼ Arithmetic circuit: polynomial computed: (𝑥1𝑥2 + 𝑥2𝑥3 )((𝑥2 + 𝑥4 ) − (𝑥3 − 𝑥5 )) ◼ Question: Given two such circuits, do they compute the same polynomial? + − + − 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 6
Naive algorithm? polynomial computed: (x1x2+x2X3)(x2+x4)-(x3-X5) X1 X2 X3 X4 X5 We can expand the two polynomials and compare their coefficients But it takes too much time. Size of the expansion can be exponential in the number of gates. Can you give such an example?
Naïve algorithm? polynomial computed: (𝑥1𝑥2 + 𝑥2𝑥3)((𝑥2 + 𝑥4) − (𝑥3 − 𝑥5)) ◼ We can expand the two polynomials and compare their coefficients ◼ But it takes too much time. ❑ Size of the expansion can be exponential in the number of gates. ❑ Can you give such an example? + − + − 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 7
Key idea Schwartz-Zippel Lemma.If p(x1,...,xn)is a polynomial of total degree d over a field F, then VS≤F, Prai-RSIp(a1,…,an)=0]≤ d 0 total degree of a monomialxxx:2+3+7 12 total degree ofa polynomial:the max total degree of its monomials. aiR S:pick each ai from S uniformly at random. (Different ai's are picked independently.) 8
Key idea ◼ Schwartz-Zippel Lemma. If 𝑝(𝑥1,…, 𝑥𝑛) is a polynomial of total degree 𝑑 over a field 𝔽, then ∀𝑆 ⊆ 𝔽, Pr𝑎𝑖←𝑅𝑆 𝑝 𝑎1,… , 𝑎𝑛 = 0 ≤ 𝑑 𝑆 . ❑ total degree of a monomial 𝑥1 2𝑥2 3𝑥5 7 :2 + 3 + 7 = 12 ❑ total degree of a polynomial: the max total degree of its monomials. ❑ 𝑎𝑖 ←𝑅 𝑆: pick each 𝑎𝑖 from 𝑆 uniformly at random. (Different 𝑎𝑖 ’s are picked independently.) 8
Few other observations A polynomial is easy to evaluate on any point by following the circuit. 2 3 6 The (formal)degree of an polynomial is easy to obtain
Few other observations ◼ A polynomial is easy to evaluate on any point by following the circuit. ◼ The (formal) degree of an polynomial is easy to obtain. + − + − 2 3 4 1 6 9
Randomized Algorithm On input polynomials pi and p2: d=max{deg(p),deg(p2)} a1,,an←R{1,2,…,100d Evaluate p1(ai,…,an)andp2(a1,…,an)by running the circuits on (a,...an). ■ifp1(a1,…,an)=p2(a1,,an), output“p1=p2". else output“p1≠p2”. 10
Randomized Algorithm On input polynomials 𝑝1 and 𝑝2: ◼ 𝑑 = max{deg(𝑝1),deg(𝑝2)} ◼ 𝑎1, …, 𝑎𝑛 ←𝑅 {1,2, … , 100𝑑} ◼ Evaluate 𝑝1(𝑎1,…, 𝑎𝑛) and 𝑝2(𝑎1,…, 𝑎𝑛) by running the circuits on (𝑎1,… , 𝑎𝑛). ◼ if 𝑝1 𝑎1,…, 𝑎𝑛 = 𝑝2(𝑎1,… , 𝑎𝑛), output “ 𝑝1 = 𝑝2”. else output “ 𝑝1 ≠ 𝑝2”. 10