Schwartz-Zippel Theorem d ∫丰0 >Pr[f(r1,r2,,rn)=0]≤ S f(ac1,x2,,xn）=axhf(a1,2,…,xn-1）+f(ac1,2,,xn) 了fk丰0 degree of f≤d-k highest power of xn in f< law of total probability: d-k Pr[f(r1,r2,.,rn)=0] I.H.>☐s SI =Pr[f(=0|fk(r1,,rn-1)=0]Pr[f(r1,.,rn-1）=0] +Pr[f(=0|fk(r1,.,rn-1)≠0]Pr[fk(r1,,rn-1)≠0] =Prg1…m-1(n)=0|fk(1,,n-1)≠0]≤ k where91,xn-1(cn）=f(c1,,xn）highest power of xn in ¯f <k fk 6⌘ 0 degree of fk  d ￾ k = xk nfk(x1, x2,...,xn￾1) + ¯f(x1, x2,...,xn) Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 f(x1, x2,...,xn) n law of total probability: Pr[f(r1, r2,...,rn) = 0] = Pr[f(~ r)=0 | fk(r1,...,rn￾1) = 0] · Pr[fk(r1,...,rn￾1) = 0] + Pr[f(~ r)=0 | fk(r1,...,rn￾1) 6= 0] · Pr[fk(r1,...,rn￾1) 6= 0] I.H.  d ￾ k |S|  k |S| gx1,...,xn￾1 where (xn) = f(x1,...,xn) = Pr[gr1,...,rn￾1 (rn)=0 | fk(r1,...,rn￾1) 6= 0]