Communication Complexity f(a,b) of bits communicated a b Han Meimei Li Lei EQ:{0,1}n×{0,1}n→{0,1 J1 a=b 0a夫b
Communication Complexity Han Meimei Li Lei EQ : {0, 1}n × {0, 1}n → {0, 1} # of bits communicated a b f(a, b) EQ(a, b) = ! 1 a = b 0 a != b
Communication Complexity f(a,b) of bits communicated a b Han Meimei Li Lei EQ:{0,1}m×{0,1}n→{0,1} Theorem (Yao 1979). Every deterministic communication protocol solving EO communicates n bits in the worst-case
Communication Complexity Han Meimei Li Lei EQ : {0, 1}n × {0, 1}n → {0, 1} # of bits communicated a b f(a, b) Theorem (Yao 1979). Every deterministic communication protocol solving EQ communicates n bits in the worst-case
Communication Complexity m-1 m-1 f=∑ax2 r)=8(r)? g=> 2=0 2=0 r,8(r) a∈{0,1}n b∈{0,1}m pick uniform by PIT: 1 random r∈2n] one-sided error≤ -2 of bit communicated: too large!
Communication Complexity a ∈{0, 1} b n ∈{0, 1}n f = n 1 i=0 aixi ∈[2n] r, g(r) f(r)=g(r) ? one-sided error 1 2 by PIT: # of bit communicated: too large! g = n X1 i=0 bixi pick uniform random r
Communication Complexity m-1 m-1 f-∑aa r)=8(r)? 9=b2 2=0 2=0 r,8) a∈{0,1}n b∈{0,1n O(log n)bits pick uniform random r∈p] ·choose a prime p∈[n2,2n2] ·letf8∈Z,x] .by PIT:ne-sided eror p (correct w.h.p.)
Communication Complexity 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) ? g = n X1 i=0 bixi O(log n) bits • choose a prime • let • by PIT: one-sided error is p ∈ [n2 ,2n2 ] f, g ∈ ℤp[x] n p = O ( 1 n) (correct w.h.p.)
Polynomial Identity Testing (PIT) Input:a polynomial f,...,]of degree d. Output:f三0？ F,...,:ring of n-variate polynomials in,...,over field F f∈Fx1,,Xn]: f,,》=∑a…空…哈 i1,…,in≥0 Degree off:maximum i+i2+…+in Withai,i…≠0
Input: a polynomial of degree . Output: ? f ∈ 𝔽[x1, …, xn] d f ≡ 0 Polynomial Identity Testing (PIT) 𝔽[x : ring of -variate polynomials in over field 1,…, xn] n x1,…, xn 𝔽 f ∈ 𝔽[x1,…, xn] : f(x1,…, xn) = ∑ i 1,…,i n≥0 ai1,i2,…,in xi 1 1 xi 2 2 ⋯xi n n Degree of f: maximum i with 1 + i 2 + ⋯ + i n ai1,i2,…,in ≠ 0