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 disjunction 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.