Informational complexity and the direct sum problem for simultaneous message complexity

Given m copies of the some problem, does it take m times the amount of resources to solve these m problems? This is the direct slim problem, a fundamental question that has been studied in many computational models. We study this question in the simultaneous message (SM) model of communication introduced by Yao [Y79]. The equality problem for n-bit strings is well known to have SM complexity Theta(rootn). We prove that solving m copies of the problem has complexity Omega (m rootn); the best lower bound provable using previously known techniques is Omega(root mn). We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalized to a broader class of functions. We introduce a new notion of informational complexity which is related to SM complexity and has nice direct sum properties. This notion is used as a tool to prove the above results; it appears to be quite powerful and may be of independent interest.