Monday, September 10, 2001

11:00 AM

CSB 209

Leen Torenvliet

U. Amsterdam

The Communication Complexity of Enumeration, Elimination and Selection

Imagine two parties, Alice and Bob, trying to make an appointment. They have to find a common empty spot in their agendas. How long does their telephone conversation have to be to achieve this? Of course, Alice can send her entire agenda to Bob, who compares the two and sends back a convenient empty spot if it exists. But can they do better? The COMMUNICATION COMPLEXITY of computing a function f(x,y) is the minimum number of bits needed to be exchanged by A and B, when initially A has x and B has y to compute f(x,y) in the sense that both know f(x,y) at the end of the conversation.

Now imagine Alice and Bob to be secretaries who have to make pairwise appointments between a number of people. Can this situation be more favorable? That is, if their input strings would be x_1,x_2,...,x_k and y_1,y_2,...,y_k respectively, could they compute the set of values f(x_i,y_i), i=1,...,k, using FEWER bits of communication than it would cost to compute these values one by one? The Direct Sum Conjecture (DSC) of Karchmer, Raz and Wigderson says they cannot do better, or at least cannot essentially do better.

Let us, for ease of notation, consider only 0/1 valued functions and let us call the string of k bits that is obtained by concatenating the k outputs f^k. Now suppose that Alice and Bob scale down their requirements and only want to ELIMINATE one or more of the possible values of f^k, or equivalently return a set possible values one of which is f^k. In the case of eliminating a single value, they can of course compute one of the values, say f(x_1,y_1) and output (1-f(x_1,y_1))0...0 at the cost of about the communication complexity of f. Can they do better in this case? The evidence we find in the work we discuss seems to also say no.

1. The Enumeration conjecture (ENC): The communication needed to compute a set of 2^{k-i+1}-1 strings one of which is f^k is at least 2. The Elimination conjecture (ELC): The communication needed to compute one string that is NOT f^k is at least about the communication needed to compute f.

Note that this looks like an inductive setup for DSC, where item 2 is the base case.

- For several natural functions we can show that any deterministic protocol for computing f^k requires Omega(n). - For several graph properties f we can show that any deterministic protocol for the elimination problem for f^k requires Omega(|V|) - For several natural functions f, any randomized protocol for the elimination problem for f^k requires Omega(n/(log log n* log n)) bits. This establishes a weak randomized version of ELC for these - Under a reasonable assumption, the elimination problem for f^2 requires Omega(D(f)) bits, where D(f) is the deterministic complexity of f. This links a weak version of ELC to other assumptions.