עמוס ביימל

We consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are k fixed Boolean functions f₁,...,f_k and each of Alice and Bob has k inputs, x₁,...,x_k and y₁,...,y_k, respectively. In the eliminate problem, Alice and Bob should output a vector σ₁,...,σ_k such that f_i(x_i, y_i) ≠ σ_i for at least one i (i.e., their goal is to eliminate one of the 2^k output vectors); in the choose problem, Alice and Bob should return (i, f_i(x_i, y_i)), for some i (i.e., they choose one instance to solve), and in the agree problem they should return f_i(x_i, y_i), for some i (i.e., if all the k Boolean values agree then this must be the output). The question, in each of the three cases, is whether one can do better than solving one (say, the first) instance. We study these three problems and prove various positive and negative results. In particular, we prove that the randomized communication complexity of eliminate, of k instances of the same function f, is characterized by the randomized communication complexity of solving one instance of f.