# Construction of Very Hard Functions for Multiparty Communication Complexity

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 1, page 61-75
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMaňuch, Ján. "Construction of Very Hard Functions for Multiparty Communication Complexity." RAIRO - Theoretical Informatics and Applications 34.1 (2010): 61-75. <http://eudml.org/doc/222016>.

@article{Maňuch2010,

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.
},

author = {Maňuch, Ján},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {multiparty communication model},

language = {eng},

month = {3},

number = {1},

pages = {61-75},

publisher = {EDP Sciences},

title = {Construction of Very Hard Functions for Multiparty Communication Complexity},

url = {http://eudml.org/doc/222016},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Maňuch, Ján

TI - Construction of Very Hard Functions for Multiparty Communication Complexity

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 1

SP - 61

EP - 75

AB -
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.

LA - eng

KW - multiparty communication model

UR - http://eudml.org/doc/222016

ER -

## References

top- L. Babai, N. Nisan and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings, 21st ACM STOC (1989). Zbl0769.68040
- N. Blum, A Boolean function requiring 3n network size. Theoret. Comput. Sci.28 (1984) 337-345. Zbl0539.94036
- A.K. Chandra, M.L. Furst and R.J. Lipton, Multi-party protocols, Proceedings, 15th ACM STOC (1983) 94-99.
- D. Dolev and T. Feder, Multiparty communication complexity, Proceedings, 30th IEEE FOCS (1989) 428-433.
- D. Dolev and T. Feder, Determinismvs. nondeterminism in multiparty communication complexity. SIAM J. Comput.21 (1992) 889-893. Zbl0765.68033
- P. Duris and J.D.P. Rolim, A lower bound on the multiparty communication complexity, STACS'95. Springer-Verlag, Lecture Notes in Comput. Sci.900 (1995) 350-360.
- P. Duris, Multiparty communication complexity and very hard functions (to appear). Zbl1087.68036
- J. Hromkovic, Communication complexity and parallel computing, An EATCS Series. Springer (1997). Zbl0873.68098
- E. Kushilevitz and N. Nisan, Communication complexity. Cambridge Univ. Press. xiii (1997). Zbl0869.68048
- R.J. Lipton and R. Sedgewick, Lower bounds for VLSI, Proceedings, 13th ACM STOC (1981) 300-307.
- O.B. Lupanov, Ob odnom metode sinteza skhem (Russian). Izv. Vyssh. Uchebn. Zaved., Radiofizika1 (1958) 120-140.
- C. Shannon, The synthesis of two-terminal switching circuits. Bell Syst. Techn. J.28 (1949) 59-98.
- A.C. Yao, The entropic limitations on VLSI computations, Proceedings, 13th ACM STOC (1981) 308-311.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.