We introduce (reasonable) generalizations of the one-way uniform two-party protocols introduced in [6,7], which provide a closer relationship between communication complexity and finite automata as regular language recognizers. A superpolynomial separation between k-party and (k-1)-party message complexities of the nondeterministic model is established by exhibiting a sequence of concrete languages to witness it, thus a strong hierarchy result. As a consequence, the new model provides an essentially better lower bound method for estimating ns(L), for some regular languages L. We remark that in the deterministic case hierarchy is not realized.
展开▼
