I&C Journal 2004 Journal Article
Multiparty communication complexity and very hard functions
- Pavol Ďuriš
A boolean function f(x 1, …, x n ) with x i ∈{0, 1} m for each i is hard if its nondeterministic multiparty communication complexity (introduced in [Proceedings of the 30th IEEE FOCS, 1989. p. 428]), C(f), is at least nm. Note that C(f)⩽nm for each f(x 1, …, x n ) with x i ∈{0, 1} m for each i. A boolean function is very hard if it is hard and its complementary function is also hard. In this paper, we show that randomly chosen boolean function f(x 1, …, x n ) with x i ∈{0, 1} m for each i is very hard with very high probability (for n⩾3 and m large enough). In [Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science, LNCS 900, 1995, p. 350], it has been shown that if f(x 1, …, x k, …, x n )=f 1(x 1, …, x k )·f 2(x k+1, …, x n ), where C(f 1)>0 and C(f 2)>0, then C(f)=C(f 1)+C(f 2). We prove here an analogical result: If f(x 1, …, x k, …, x n )=f 1(x 1, …, x k )⊕f 2(x k+1, …, x n ) then DC(f)=DC(f 1)+DC(f 2), where DC(g) denotes the deterministic multiparty communication complexity of the function g and “⊕” denotes the parity function.