Informational complexity and the direct sum problem for simultaneous message complexity
Informational complexity and the direct sum problem for simultaneous message complexity
复制标题
DOI：
10.1109/sfcs.2001.959901
复制
发表时间：
2001-10
期刊：
影响因子：
--
通讯作者：
Amit Chakrabarti;Yaoyun Shi;Anthony Wirth;A. Yao
中科院分区：
文献类型：
--
作者：
Amit Chakrabarti;Yaoyun Shi;Anthony Wirth;A. Yao
给定同一个问题的m个副本，解决这m个问题是否需要m倍的资源？这就是直和问题，一个在许多计算模型中已经研究过的基本问题。我们在A.C. Yao（1979）.众所周知，n位字符串的等式问题具有SM复杂度/spl Theta/（/spl radic/n）。我们证明，解决m个副本的问题的复杂性/spl欧米茄/（m/spl radic/n），最好的下界证明使用以前已知的技术是/spl欧米茄/（/spl radic/（mn））。我们还证明了类似的下界上的某些布尔组合的多个副本的平等功能。这些结果可以推广到更广泛的函数类。我们引入了一个新的信息复杂度的概念，它与SM复杂度相关，并且具有很好的直和性质。这个概念被用作证明上述结果的工具;它似乎是相当强大的，可能是独立的利益。
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 A.C. Yao (1979). The equality problem for n-bit strings is well known to have SM complexity /spl Theta/(/spl radic/n). We prove that solving m copies of the problem has complexity /spl Omega/(m/spl radic/n); the best lower bound provable using previously known techniques is /spl Omega/(/spl radic/(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.