| Attributs | Valeurs |
|---|
| type
| |
| Is Part Of
| |
| Subject
| |
| Title
| - Construction of Very Hard Functions for Multiparty Communication Complexity
|
| Date
| |
| has manifestation of work
| |
| related by
| |
| Author
| |
| Abstract
| - We consider the multiparty communication model defined in [4] using the formalism from [8]. First, we correct an inaccuracy in the proof of the fundamental result of [6] 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 [7], 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.
|
| article type
| |
| publisher identifier
| |
| Date Copyrighted
| |
| Rights
| |
| Rights Holder
| |
| is part of this journal
| |
| is primary topic
of | |
