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.