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.) 8Key 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