עמוס ביימל

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 Alice and Bob have 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 ) ≠ σ_i for at least one i (i.e., their goal is to eliminate one of the 2^k output vectors); in choose, Alice and Bob should return (i,f_i (x_i, y_i )) and in agree they should return f_i (x_i, y_i ), for some i. 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.