Lecture 4.Multiparty Communication Complexity 1.Models In this class we study communication complexity models in which input variables are distributed to k>2 parties.Two most studied ways of distributing input variables are Number in Hand (NiH):The input is(x1,...,xx)where xi E Xi for some set Xi,and xi is given to Player i. Number on the Forehead (NoF):The input is (x1,...,xx)where xi E Xi for some set Xi,and xi=(x1,..,,+1,...,xn)is given to Player i. Typical ways of communication models include: ● Blackboard:There is a common blackboard for players to write on,and it's visible to everyone. The communication complexity is the total number of bits written on the blackboard. ● Message passing:There are channels between every pair ofplayers,and the communication complexity is the total number of transmitted bits during the whole protocol. ● One-way:Player I sends a message to Player 2,who then sends a message to Player 3,and so on. The last player outputs a value. ● SMP:One can further restrict the allowed communication channels:each of the k players sends one message to a Referee who then announces the result. The NiH model draws much attention in recent years because of its connection to data streaming algorithms.NiH with SMP has an intimate connection to the data sketching algorithms.Earlier studies in the multiparty communication complexity focused more on the NoF model with a blackboard because of its connection to circuit complexity.(We will come to the connection later in the class.) Across today's lecture,we assume that there is a blackboard.It is easy to see that some of the results hold for other communication models as well.Lecture 4. Multiparty Communication Complexity 1. Models In this class we study communication complexity models in which input variables are distributed to k>2 parties. Two most studied ways of distributing input variables are ⚫ Number in Hand (NiH): The input is (x1, …, xk) where xi ∈ Xi for some set Xi , and xi is given to Player i. ⚫ Number on the Forehead (NoF): The input is (x1, …, xk) where xi ∈ Xi for some set Xi , and 𝑥−𝑖 = (𝑥1,… ,𝑥𝑖−1,𝑥𝑖+1,…,𝑥𝑛) is given to Player i. Typical ways of communication models include: ⚫ Blackboard: There is a common blackboard for players to write on, and it’s visible to everyone. The communication complexity is the total number of bits written on the blackboard. ⚫ Message passing: There are channels between every pair of players, and the communication complexity is the total number of transmitted bits during the whole protocol. ⚫ One-way: Player 1 sends a message to Player 2, who then sends a message to Player 3, and so on. The last player outputs a value. ⚫ SMP: One can further restrict the allowed communication channels: each of the k players sends one message to a Referee who then announces the result. The NiH model draws much attention in recent years because of its connection to data streaming algorithms. NiH with SMP has an intimate connection to the data sketching algorithms. Earlier studies in the multiparty communication complexity focused more on the NoF model with a blackboard because of its connection to circuit complexity. (We will come to the connection later in the class.) Across today’s lecture, we assume that there is a blackboard. It is easy to see that some of the results hold for other communication models as well