Construction of Very Hard Functions for Multiparty Communication Complexity
Department of Mathematics and
Turku Centre for Computer Science,
University of Turku,
Accepted: 20 March 2000
We consider the multiparty communication model defined in  using the formalism from . First, we correct an inaccuracy in the proof of the fundamental result of  providing a lower bound on the nondeterministic communication complexity of a function. Then we construct several very hard functions, i.e., functions such that those as well as their complements have the worst possible nondeterministic communication complexity. The problem to find a particular very hard function was proposed in , where it has been shown that almost all functions are very hard. We also prove that combining two very hard functions by the Boolean operation xor gives a very hard function.
Mathematics Subject Classification: 68Q15 / 68Q85
© EDP Sciences, 2000