Polynomial ldentity Testing (PIT) Input:f,gEF[1,22,...,n]of degree d Output:f=g? F1,2,...,:ring of n-variate polynomials over fieldF f∈F[x1,2,,cn: f(r1,2,,xn)= 21 Qil,i2,...,in 2.…n i1,i2,…,in≥0 degree of f:maximum i1+i2+..+in with a,i2...0
Polynomial Identity Testing (PIT) Input: of degree d Output: f g? f,g 2 F[x1, x2,...,xn] F[x1, x2,...,xn] : ring of n-variate polynomials over field F f(x1, x2,...,xn) = X i1,i2,...,in0 ai1,i2,...,in xi1 1 xi2 2 ··· xin n degree of f : maximum i1 + i2 + ··· + in ai1,i2,...,in with 6= 0 f 2 F[x1, x2,...,xn] :
Input:f,geF[1,22,...,n]of degree d Output:f g? equivalently: Input:fEF[1,22,...,n]of degree d Output:f≡0？ fis given as block-box:given any=(1,x2,...,n) returns f(z) or as product from:e.g.Vandermonde determinant X1 n- 1 -1 T2 2 T T2 M= f(=det(M)=Π(r-x) In 喝 x-1 j<i
Input: of degree d Output: f g? f,g 2 F[x1, x2,...,xn] Input: of degree d Output: f 0? f 2 F[x1, x2,...,xn] equivalently: f is given as block-box: given any ~ x = (x1, x2,...,xn) returns f(~ x) or as product from: Vandermonde determinant M = 2 6 6 6 4 1 x1 x2 1 ... xn1 1 1 x2 x2 2 ... xn1 2 . . . . . . . . . ... . . . 1 xn x2 n ... xn1 n 3 7 7 7 5 f(~ x) = det(M) = Y j<i (xi xj ) e.g
Input:fF[1,22,...,n]of degree d Output:f≡0？ fix an arbitrary S F pick random ri,r2,...,mnES uniformly and independently at random; check whether f(ri,r2,...rn)=0; f=0f(r1,r2,.,rn)=0
Input: 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 f ⌘ 0 f(r1, r2,...,rn)=0
Input:a polynomial fe]of degree d Output:f三0？ fix an arbitrary SF pick a uniform random r ES; check whether fr)=0; f≡0>f(r)=0 Fundamental Theorem of Algebra: A degree d polynomial has at most d roots. f丰0>Prf(r)=0]≤ d Is]
A degree d polynomial has at most d roots. Fundamental Theorem of Algebra: pick a uniform random r ∈S; check whether f(r) = 0 ; Input: a polynomial of degree d Output: f F[x] f 0? fix an arbitrary S ✓ F f ⌘ 0 f(r)=0 f 6⌘ 0 Pr[f(r) = 0] d |S|
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]≤ IS
Input: 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