Input:fF[1,22,...,n]of degree d Output:f≡0？ fix an arbitrary S F pick random ri,r2,...,rES uniformly and independently at random; check whether f(ri,r2,...,r)=0 f三0>f(r,r2,,rn)=0 Schwartz-Zippel Theorem d f丰0>Pr[f(1,r2,,rn)=0]≤ ISInput: of degree d Output: f ￾ 0? f 2 F[x1, x2,...,xn] pick random r1, r2, ... , rn ∈S uniformly and independently at random; check whether f(r1, r2, ... , rn) = 0 ; fix an arbitrary S ✓ F Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 f ⌘ 0 f(r1, r2,...,rn)=0