CS 591 B1: Communication Complexity, Fall 2019 Problem Set 3
Due: 5:00PM, Friday, November 15, 2019.
Homework Policies:
• Submit your completed assignment by email to mbun[at]bu[dot]edu. Please include the string “CS591PS3” somewhere in your subject line.
• Solutions must be typeset, e.g., using LATEX or Microsoft Word.
• To help your instructor calibrate the length and difficulty of future assignments, please
include with each problem an estimate of how long it took you to solve it.
• You are encouraged to collaborate on the homework problems with each other in small groups (2-3 people). Collaboration may include brainstorming or exploring possible solutions together on a whiteboard, but should not include one person telling the others how to solve a problem. You must also write up the solutions independently (in your own words) and acknowledge your collaborators at the beginning of the first page.
• You may freely use without proof any results proved in class, in Mark’s lecture notes posted on the class webpage, or in the main body of the texts assigned as reading. Note that this excludes results that appear in the texts as problems and exercises. You may, of course, use such results but you have to prove them first.
• You may read papers and other outside sources to help you solve these problems. If you do so, you must acknowledge these sources and write the solutions in your own words.
• Start early! The problems are presented roughly in the order of the course content they correspond to, so you may get started on the first few problems as soon as the assignment is released. Late assignments will receive credit only with prior permission of the instructor.
1
Problem 1 (Unbounded Error Communication).
(a) Give an unbounded error communication protocol for the greater-than function GTn which requires only one bit of communication from Alice to Bob (who can then output the answer).
(b) Let f : X×Y → {−1,1} be any function with rank± Sf = 2. Show that f has a bounded error randomized communication protocol with cost O(log n).
Hint: You may use without proof the fact that BPPcc(GTn) = O(log n).
It turns out that this result cannot be improved: There are functions with sign rank 3 but with discrepancy exp(−Ω(n)), and hence even PPcc communication complexity Ω(n).
Problem 2 (Karchmer-Wigderson Games). Karchmer-Wigderson games translate (often difficult) questions in circuit complexity into simple-to-state problems in communication complexity. This problem illustrate how to prove lower bounds on monotone circuit size using lifting theorems.
Let f : {0, 1}n → {0, 1} be a monotone boolean function. (A boolean function is mono- tone if f(x) ≤ f(y) whenever xi ≤ yi for every i = 1,…,n. In other words, flipping an input bit from 0 to 1 cannot decrease the value of the function from 1 to 0.) The Karchmer- Wigderson game associated to f, denoted KWf, is the following communication problem. Alice receives an input x ∈ f−1(0) and Bob receives an input y ∈ f−1(1). Their goal is to agreeonanyindexiforwhichxi =0andyi =1.
(a) Show that this game is well-defined, i.e., for every monotone function f and x ∈ f−1(0),y ∈ f−1(1) there exists an index i for which xi = 0 and yi = 1.
(b) A monotone boolean circuit is a directed, acyclic graph with one sink (an “output gate”) and n sources (“input gates”). The inputs are labeled by variables x1,…,xn and all other vertices have in-degree 2 and are labeled by either ∧ or ∨. The function computed at any vertex labeled by ∧ is the logical AND of the two functions computed on its incoming wires, and similarly for vertices labeled by ∨ with logical OR. The function computed by the circuit itself is the function computed at its output gate. The depth of such a circuit is the maximum length of any path from an input vertex to the output.
Prove that the minimum depth of a monotone circuit computing a monotone function f is exactly the deterministic communication complexity of KWf .
Hint: Start by showing that one can construct a protocol for KWf by traversing a shallow circuit computing f from the output to the input level.
(c) Consider the following search problem. Given as input a string x1, . . . , xn, find any index i such that at least one of the following holds:
• i=1andxi =1,
2
• i=nandxi =0,or • i≤nandxi ̸=xi+1.
Show that any decision tree (over the variables x1, . . . , xn) solving this search problem requires depth Ω(log n).
(d) In the st-connectivity problem STCONN, a graph on vertex set V is presented to a boolean circuit via its adjacency matrix. Prove that the monotone circuit depth of STCONN is Ω(log2 |V |).
Hint: Lift the lower bound from part (c) using the Indexing gadget and show that a protocol for KWSTCONN can be used to solve the resulting problem.
3