Question 1

The rectangle property of two-party deterministic protocols states that for any protocol tree T computing a function f  : {0, 1}n  × {0, 1}n  → {0, 1}, and for any node v of T: Rv  = Av  × Bv where,

Rv     =    (x,y)|x,y ∈ {0, 1}m , (x,y)⇝(T) v 

Av     =   {x|∃y ∈ {0, 1}m , (x,y) ∈ Rv }

Bv     =   {y|∃x ∈ {0, 1}m , (x,y) ∈ Rv }

Here (x,y) ⇝ v denotes that when protocol T is run on (x,y) it eventually reaches the node v . Prove by induction that the property is true.

(a)  Base case: Prove that the property is true at the root of the protocol

(2 points)

(b) Induction step: Assume the property is true for a node at depth i, and prove it for its children. (3 points)

Question 2

Recall the three-party number on the forehead model of communication. There are three players, Alice, Bob, and Charlie, who want to compute a function f : {0, 1}n  × {0, 1}n  × {0, 1}n  → {0, 1} on their inputs x,y and z .  Note that the players get their input on their forehead in this model. Thus Alice knows what y,z is but does not know x, Bob knows x,z but not y, and Charlie knows x,y but not z . Consider the following generalization of the 2-party version of EQn

f(x,y,z) = (0(1)

if ∀i ∈ [n] : xi = yi+ zi(mod2)

otherwise

(1)

Note that addition modulo 2 of two binary bits is defined as 1 + 1 = 0, 1 + 0 = 1, 0 + 1 = 1, and 0 + 0 = 0. Consider the following number on forehead protocol for f where n = 2 (that is Alice, Bob and Charlie gets 2-bit strings x,y and z respectively on their forehead):

• Alice writes y1 on the board (that everyone can see)

•  Bob writes 1 on the board if x1 = y1 + z1 (mod2), and 0 otherwise.

•  If Bob writes they stop the protocol and announce the answer to be 0.

•  Else, Alice writes y2 on the board

•  Bob writes 0 on the board if x2 = y2 + z2 (mod2), and 0 otherwise.

• The players decide that value of f(x,y,z) is equal to the value written by Bob and stop the protocol.

(a) Draw the protocol tree for the above protocol solving f on 2-bit inputs.  Note that since the players still send binary bits, the tree would be a binary tree. The only difference would be that each internal node can be labeled by Alice, Bob, or Charlie based on who is writing on the board.

(2 points)

(b) Consider the unique path traced from the root to a leaf by the following transcript of the protocol: 1. Alice sends y1  = 0, 2. Bob writes 1 indicating that x1  = y1 + z1 (mod2), 3. Alice sends y2  = 1, Bob writes 0 indicating that x2  y2 + z2 (mod2). For each vertex v on this path compute

Sv     =    (x,y,z) | (x,y,z)⇝(T) v 

That is, Sv  is the set of inputs which reach v, when we run the protocol above. (2 points)

(c)  Rectangle property of 2-party protocols proved in Question 1, was an important tool in under- standing communication complexity of various functions in the 2-party model. A natural general- ization of this property for 3-party number-on-forehead protocols would say that for any v in the protocol tree T, Sv  can be written as Sv  = Av  × Bv  × Cv  where Av  =  x | ∃y,z,(x,y,z)⇝(T) v  , Bv  =  y | ∃x,z,(x,y,z)⇝(T) v   and Cv  =  z | ∃x,y,(x,y,z)⇝(T) v  . Using the answer to Question 2.b argue whether this particular generalization of the rectangle property holds for 3-party number on forehead protocols.

• At the node reached by Alice sending y1 = 0 is the property true? (2 points)

• At the node reached by Bob responding with 1 indicating x1 = y1 +z1 ( mod 2) is the property true? (2 points)

•  If the property is false at some node in the transcript in Question 2.b, why does it break down? (4 points)

Question 3

We saw an overview of how given the partition communication matrix Mf  (of a two party com- munication function f  : {0, 1}n  × {0, 1}n  → {0, 1}) into k monochromatic rectangles, one can turn it into a protocol solving f whose cost is log2 k bits. Prove the same by reducing the problem to the Clique Independent Set intersection problem.

In this problem, Alice and Bob know some n-vertex graph G, Alice is given a clique from the graph, and Bob is given an independent set. The players’ goal is to find whether their clique and indepen- dent set intersects. We saw that this problem can be solved using log2 n bits of communication so that if there is an intersection, at the end of the protocol, the players also learn the label v of the vertex in the intersection.

(a)  Based on the partition of Mf into k monochromatic rectangles (which is known to both Alice and Bob) come up with a graph G with k vertices which is known to both Alice and Bob.

(2 points)

(b)  Transform the input x of Alice into a Clique C in this graph, and transform the input y of Bob into an independent set I in this graph.

1 (2 points)