The communication complexity of enumeration, elimination, and selection

Let 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(x₁, y₁)···f(x_k, y_k) communicating as few bits as possible. The Direct Sum Conjecture 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 three 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 an element of {0, 1}^k that is not 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 V f(x₂, Y₂)=1 then f(x_i, y_i)=1. We establish lower bounds on ELIM(f^k) for particular f and connect the complexity of ELIM(f^k), ENUM(k, f^k), and SELECT(f ²) to the direct sum conjecture and other conjectures