CS 591 B1: Communication Complexity, Fall 2019 Problem Set 1
Due: 5:00PM, Friday, September 27, 2019.
Homework Policies:
• Submit your completed assignment by email to mbun[at]bu[dot]edu. Please include the string “CS591PS1” 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.
The problem set looks longer than it actually is. This is because some of the problems introduce additional background and concepts that were not covered in the lecture, but which will enhance your understanding of the material and which I hope you will find interesting. Please do not hesitate to ask questions about any of the new material on Piazza or during office hours.
1
Problem 1 (Partial Functions). A partial function is one which is defined only on a subset of its domain. More formally, a partial function is a mapping f : {0, 1}n × {0, 1}n → {0, 1, ⋆}. Inputs x for which f(x) = ⋆ should be interpreted as inputs where f is not defined. A (deterministic) protocol Π computes a partial function f if Π(x, y) = f (x, y) for every (x, y) with f(x,y) ̸= ⋆. This problem investigates which of the results we’ve seen also apply to partial functions.
(a) For b ∈ {0,1}, call a combinatorial rectangle R b-monochromatic with respect to a partial function f if f(x) ∈ {b,⋆} for every x ∈ R. Consider the partial function PrEQn : {0, 1}2n × {0, 1}2n → {0, 1, ⋆} defined by
1 if (x1,…,xn) = (y1,…,yn) and (xn+1,…,x2n) ̸= (yn+1,…,y2n),
PrEQn(x,y) = 0 if (x1,…,xn) ̸= (y1,…,yn) and (xn+1,…,x2n) = (yn+1,…,y2n), ⋆ otherwise.
Show that 2n 0-monochromatic rectangles suffice to cover PrEQ−1(0) and 2n 1-monochromatic
rectangles suffice to cover PrEQ−1(1). n
(b) Show that Pcc(PrEQn) ≥ Ω(n). (Hint: Reduce to the fact that Pcc(EQ2n) = 2n + 1.)
Combined with part (b), this shows that Pcc(f) can be much larger than NPcc(f) · coNPcc(f) for partial functions. Recall that Pcc(f) ≤ O(NPcc(f) · coNPcc(f)) for all total f. No need to hand an explanation in, but where in that proof do we use the fact that f is total?
(c) Let f be a partial function. Show that if every 1-monochromatic rectangle with respect to f has size at most s, then it has nondeterministic communication complexity NPcc(f) ≥ log(f−1(1)/s).
(d) Define the Unambiguous-Disjointness function UDISJn : {0, 1}n × {0, 1}n → {0, 1, ⋆} by 1 if|x∧y|=0,
UDISJn(x,y)= 0 if|x∧y|=1, ⋆ otherwise.
(Here, x∧y denotes the bitwise AND between x and y.) This is a variant of Disjointness which only asks to distinguish the case where the sets represented by x and y are disjoint from the case where they intersect in only one element.
Prove that NPcc(UDISJn) ≥ Ω(n).
2
n
Problem 2 (Diverse Functions). Let f : X ×Y → {0, 1} be a function whose communication matrix Mf has at least k distinct rows. Prove that Pcc(f) ≥ log log k.
Problem 3 (Reductions and Completeness). Let fn, gn : {0, 1}n × {0, 1}n → {0, 1} be families of functions. We say that {fn }n∈N reduces to {gn }n∈N , written {fn } ≤cc {gn }, if there exists a function m(n) = 2polylog(n) for which the following holds. For every n there exist functions RA,RB : {0,1}n → {0,1}m(n) such that f(x,y) = g(RA(x),RB(y)) for every x, y ∈ {0, 1}n. The functions RA and RB allow Alice and Bob to reduce the evaluation of f to the evaluation of g through independent preprocessing of their inputs; the upper bound on m(n) is a criterion for what it means for this preprocessing to be “efficient.”
By analogy to Karp reductions for Turing machine classes, these reductions allow us to define completeness with respect to communication classes. For a communication complexity measure Ccc, recall that we define the class Ccc to be the set of function families {fn} with Ccc(fn) = polylog(n). We say that a family {gn} is complete for Ccc if 1) {gn} ∈ Ccc and 2) {fn} ≤cc {gn} for every {fn} ∈ Ccc.
(a) Prove that the disjointness function DISJn is complete for coNPcc.
(b) Using the fact that the NPcc cost of any protocol is characterized up to constants by its 1-covering number, we can alternatively define the class NPcc as the class of functions which have 1-covers of quasipolynomial size. That is, NPcc is exactly the class of function families {fn} which can be expressed as
2polylog(n) fn(x,y)= Rni(x,y)
i=1
where each function Rni is the indicator of a rectangle.
This perspective gives us a natural way of defining a polynomial hierarchy in commu-
nication complexity without the need to reason about “alternating” protocols, and of
defining an analog of PSPACE without even needing to define space! For instance, we
may define Σcc as the sequences of functions {f } which can be expressed as 2n
2polylog(n) 2polylog(n)
f (x,y)= R ̄i,j(x,y),
nn i=1 j=1
where each function R ̄i,j is the indicator for the complement of a rectangle. n
Identify a complete problem for Σcc and prove its completeness. 2
3
Problem 4 (Corruption and Disjointness). In class, we’ll see that the Disjointness function has large discrepancy, at least Ω(1/n), and hence the discrepancy method cannot be used to prove strong lower bounds. Intuitively, this is because the hardness of Disjointness is “one-sided”: It has large 0-rectangles which are easy to certify membership in, but no large 1-rectangles. The one-sided discrepancy (or corruption) bound uses the fact that large rectangles must have many 0s, and is actually enough to prove a tight Ω(n) lower bound on the randomized communication of DISJn. This problem will walk you through an elegant combinatorial proof of an Ω(√n) lower bound due to Babai, Frankl, and Simon.
(a) (Corruption Bound) Let f : X×Y → {0,1} and let μ be a distribution over X×Y such that
μ(R ∩ f−1(0)) ≥ εμ(R)
for every rectangle with μ(R) ≥ 2−2c. Suppose 1/3 < μ(f−1(1)) < 2/3. Prove that (for ε sufficiently small and c sufficiently large) no deterministic protocol computes f to error ε/4 under inputs sampled from the distribution μ with communication cost ≤ c.
(b) Suppose without loss of generality that n is a perfect square which is divisible by 12. Let μ
be the distribution over DISJn which is uniform over all pairs (x, y) with |x| = |y| = √n,
i.e., Alice and Bob’s inputs indicate random sets of size exactly √n. Let R = A × B
be a rectangle with |A| > 2−δ√n · √n for some constant δ > 0 sufficiently small (but n
independent of n).
Prove by induction that for k = √n/3, there exist rows x1, . . . , xk ∈ A that are “well-
separated” in the sense that for every i = 1, . . . , k, we have |xi \(x1 ∪· · ·∪xi−1)| ≥ √n/2. (c) Suppose μ(R∩DISJ−1(0)) < εμ(R) for ε > 0 sufficiently small. By deleting at most half
n
of the rows of A, we may assume that every x ∈ A intersects at most 2ε|B| of the rows of B. Similarly, by deleting most half of the rows of B, we may assume that every y ∈ B intersects with at most 4εk of the rows in the well-separated set {x1 , . . . , xk } constructed in part (b).
Prove that under these assumptions,
k n−(1−4ε)k√n/2 −δ√n n
|B|≤ 4εk · √n ≤2 · √n for some constant δ > 0.
(d) Conclude that for any rectangle R with μ(R ∩ DISJ−1(0)) < εμ(R), we must have √n
μ(R) < 2−δ n.
(e) Use part (a) to conclude that BPPcc(DISJn) ≥ Ω(√n).
4