Communication Complexity m-1 m-1 f=) ax2 r)=8(r)? 2=0 2=0 r,8(r) a∈{0,1}m b∈{0,1}n Han Meimei Li Lei pick uniform random r∈[p] k=1og2(2m)] choose a prime p[2%,+] letf,g∈Zp[x]
Communication Complexity Han Meimei Li Lei a ∈{0, 1} b n ∈{0, 1}n f = n 1 i=0 aixi pick uniform random r ∈[p] r, g(r) f(r)=g(r) ? k = log2(2n) p [2k , 2k+1 choose a prime ] let f,g Zp[x] g = n X1 i=0 bixi
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] :