Motivation 2: Communication complexity X f(x,y) Two parties,Alice and Bob,jointly compute a function f(x,y). -x known only to Alice and y only to Bob. Communication complexity*1:how many bits are needed to be exchanged?---D() *1.Ya0.ST0C,1979.Motivation 2: Communication complexity • Two parties, Alice and Bob, jointly compute a function 𝑓(𝑥, 𝑦). – 𝑥 known only to Alice and 𝑦 only to Bob. • Communication complexity* 1 : how many bits are needed to be exchanged? --- 𝐷(𝑓) 𝑓(𝑥, 𝑦) 𝑥 𝑦 *1. Yao. STOC, 1979