The Communication Complexity of Enumeration, Elimination, and Selection

Let k, n∈N and f:{0, 1}ⁿ×{0, 1}ⁿ→{0, 1}. Assume Alice has x₁, ..., x_k∈ {0, 1}ⁿ, Bob has y₁, ..., y_k∈{0, 1}ⁿ, and they want to compute f^k(x₁x₂···x_k, y₁y₂···y_k)=(f(x ₁, y₁), ..., f(x_k, y_k)) (henceforth f(x₁, y₁)···f(x_k, y_k)) communicating as few bits as possible. The direct sum conjecture (henceforth DSC) of Karchmer, Raz, and Wigderson states that the obvious way to compute it (computing f(x₁, y₁), then f(x₂, y₂), etc.) is, roughly speaking, the best. This conjecture arose in the study of circuits since a variant of it implies NC¹≠NC². We consider two related problems. Enumeration:Alice and Bob output e≤2^k-1 elements of {0, 1}^k, one of which is f(x₁, y₁)···f(x_k, y_k). Elimination :Alice and Bob output b such that b≠f(x₁, y₁)···f(x_k, y_k). Selection :(k=2) Alice and Bob output i∈{1, 2} such that if f(x₁, y₁) =1∨f(x₂, y₂)=1 then f(x_i, y_i)=1. (a)We devise the enumeration conjecture (henceforth ENC) and the elimination 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 elimination problem for f^k requires Ω(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 Ω(V) bits. To accomplish this we establish some very general theorems about the communication complexity of graph properties which are of independent interest. (d)For several natural functions f, any randomized protocol for the elimination problem for f^k requires Ω(n(loglog(n))(log(n))) bits. This establishes a weak randomized version of ELC for these functions. (e)Under a reasonable (but unproven) assumption, the elimination problem for f²requiresΩ(D(f)) bits, where D(f) is the deterministic complexity of f. This links a weak version of ELC to other assumptions.