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 X￾1 i=0 bixi