Conference Proceedings

Informational complexity and the direct sum problem for simultaneous message complexity

A Chakrabarti, YY Shi, A Wirth, A Yao

42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | IEEE COMPUTER SOC | Published : 2001

Abstract

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. 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 Θ(√n). We prove that solving m copies of the problem has complexity Ω(m√n); the best lower bound provable using previously known techniques is Ω(√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 broad..

View full abstract