The communication complexity of enumeration, elimination, and selection

Let k, n is an element of N and f: {0, 1}(n) x {0, 1}(n) --> {0, 1}(n). Ass ume Alice has x(1), ...., x(k) is an element of f {0, 1}(n), Bob has y(1), ..., y(k) is an element of {0, 1}(n), and they want to compute f(k)(x(1)x(2 ) (...) x(k), y(1)y(2) (...) y(k)) = (f(x(1), y1), ..., f(x(k), y(k))) (hen ceforth f(x(1), y(1)) (...) f(x(k), y(k)) communicating as few bits as poss ible. The direct sum conjecture (henceforth DSC) of Karchmer, Raz, and Wigd erson states that the obvious way to compute it (computing f(x(1), y(1)), t hen f(x(2), y(2)), etc.) is, roughly speaking, the best. This conjecture ar ose in the study of circuits since a variant of it implies NC1 not equal NC 2. We consider two related problems. Enumeration: Alice and Bob output e less than or equal to 2(k) - 1 elements of {0, 1}(k), one of which is f(x(1), y(1)) (...) f(x(k), y(k)). Elimination: Alice and Bob output b such that b not equal f(x(1), y(1)) (.. .) f(x(k), y(k)). Selection: (k = 2) Alice and Bob output i is an element of {1, 2} such that if f(x(1), y(1)) = 1 boolean OR f(x(2), y(2)) = 1 then f (x(i), y(i)) = 1. (a) We devise the enumeration conjecture (henceforth ENC) and the eliminati on conjecture (henceforth ELC) which roughly state that the obvious ways to compute enumeration and elimination are the best. We use these conjectures to formulate an attack on DSC. (b) For several natural functions f, any deterministic protocol for the eli mination problem for f(k) requires Omega (n) bits. This establishes a weak form of ELC for these functions. (c) For several graph properties f we show that any deterministic protocol for the elimination problem for f(k) requires Omega(\V\) bits. To accomplis h this we establish some very general theorems about the communication comp lexity of graph properties which are of independent interest. (d) For several natural functions f, any randomized protocol for the elimin ation problem for f(k) requires Omega (n/(log log(n))(log(n))) bits. This e stablishes a weak randomized version of ELC for these functions. (e) Under a reasonable (but unproven) assumption, the elimination problem f or f(2) requires Omega (D(f)) bits, where D(f) is the deterministic complex ity of f. This links a weak version of ELC to other assumptions. (C) 2001 A cademic Press.