文章基本信息

标题：On Multipartition Communication Complexity
本地全文：下载
作者：Pavol Duris ; Juraj Hromkovic ; Stasys Jukna 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit hierarchy on the degree of non-obliviousness is established by proving that, using k+1 partitions instead of k may decrease the communication complexity from a linear function in the input size to a logarithmic function in k. 2. Certain linear codes are hard for k-partition protocols even when k may be exponentially large (in the input size). On the other hand, one can show that all characteristic functions of linear codes are easy for randomized OBDDs. 3. It is proven that there are subfunctions of the triangle-freeness function and the function Parity-3-Clique which are hard for multipartition protocols. As an application, truly exponential lower bounds on the size of nondeterministic read-once branching programs for these functions are obtained, solving an open problem of Razborov.
关键词：Computational Complexity , lower bounds , multipartition communication complexity , non-obliviousness , read-once branching programs , rectangular complexity