Communication Complexity m-1 m-1 f=】 r)=8(r)? 2=0 2=0 r,8(r) a∈{0,1}m b∈{0,1}n Han Meimei Li Lei by PIT: pick uniform 1 random r∈2n one-sided error≤ -2 of bit communicated: too large!Communication Complexity Han Meimei Li Lei a ∈{0, 1} b n ∈{0, 1}n f = n ￾￾1 i=0 aixi pick uniform random r ∈[2n] r, g(r) f(r)=g(r) ? one-sided error ￾ 1 2 by PIT: # of bit communicated: too large! g = n X￾1 i=0 bixi