Polynomial Identity Testing (PIT) Input:a polynomial fFx,...,]of degree d. Output:f三0？ fxx)=∑axx… i1,,in≥0 i1+…+n≤d fis given as black-box:given any x F",return f(x) or as product form:e.g.Vandermonde determinant 1 好 1 M= 2 f()det(M)=(x) Ki Xn
Input: a polynomial of degree . Output: ? f ∈ 𝔽[x1, …, xn] d f ≡ 0 Polynomial Identity Testing (PIT) f(x1,…, xn) = i 1,… ∑ , in ≥ 0 i 1 + ⋯ + in ≤ d ai1,i2,…,in xi 1 1 xi 2 2 ⋯xi n n or as product form: e.g. Vandermonde determinant f is given as black-box: given any x ⃗∈ 𝔽 , return n f( x ⃗) M = 1 x1 x2 1 … xn−1 1 1 x2 x2 2 … xn−1 2 ⋮ ⋮ ⋮ ⋱ ⋮ 1 xn x2 n … xn−1 n f( x ⃗) = det(M) = ∏ j<i (xi − xj )
Polynomial Identity Testing (PIT) Input:a polynomial fFx,...,]of degree d. Output:f三0？ fis given as product form if 3 a poly-time deterministic algorithm for PIT: either::NEXP≠P/poly Or:#P≠FP
Input: a polynomial of degree . Output: ? f ∈ 𝔽[x1, …, xn] d f ≡ 0 Polynomial Identity Testing (PIT) f is given as product form if ∃ a poly-time deterministic algorithm for PIT: either: NEXP ≠ P/poly or: #P ≠ FP