• Calendar

April 22, Monday
10:00 – 12:00

Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. In the first part of the talk we will focus on the advice complexity of this kind of questions, in a probabilistic Turing machine model, and discuss how many bits of "help" we need to accept such languages. In the second part we will consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are $k$ fixed Boolean functions $f_1,dots,f_k$ and Alice and Bob have $k$ inputs $x_1,dots,x_k$ and $y_1,dots,y_k$, respectively. We consider In the {em eliminate} problem, Alice and Bob should output a vector $sigma_1,dots,sigma_k$ such that $f_i(x_i)neq sigma_i$ for at least one $i$ (i.e., their goal is to eliminate one of the $2^k$ output vectors); in {em choose}, Alice and Bob should return $(i,f_i(x_i,y_i))$ and in {em 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 instance.