Communication complexity F(x,y) Two parties,Alice and Bob,jointly compute a function F on input (x,y). -x known only to Alice and y only to Bob. Communication complexity*1:how many bits are needed to be exchanged? *1.A.Ya0.STOC,1979.Communication complexity • Two parties, Alice and Bob, jointly compute a function 𝐹 on input (𝑥, 𝑦). – 𝑥 known only to Alice and 𝑦 only to Bob. • Communication complexity* 1 : how many bits are needed to be exchanged? 𝐹(𝑥, 𝑦) 𝑥 𝑦 *1. A. Yao. STOC, 1979