Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-24T16:09:47.568Z Has data issue: false hasContentIssue false
  • English
  • Français

Construction of Very Hard Functions for Multiparty Communication Complexity

Published online by Cambridge University Press:  15 April 2002

Ján Maňuch
Ján Maňuch*
Affiliation:
Department of Mathematics and Turku Centre for Computer Science, University of Turku, Turku, Finland; ([email protected])
Get access

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.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 1 , January 2000 , pp. 61 - 75
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

L. Babai, N. Nisan and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings, 21st ACM STOC (1989).
Blum, N., Boolean, A function requiring 3n network size. Theoret. Comput. Sci. 28 (1984) 337-345. CrossRef
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.
Dolev, D. and Determinism, T. Feder vs. nondeterminism in multiparty communication complexity. SIAM J. Comput. 21 (1992) 889-893. CrossRef
Duris, P. and Rolim, J.D.P., A lower bound on the multiparty communication complexity, STACS'95. Springer-Verlag, Lecture Notes in Comput. Sci. 900 (1995) 350-360. CrossRef
P. Duris, Multiparty communication complexity and very hard functions (to appear).
J. Hromkovic, Communication complexity and parallel computing, An EATCS Series. Springer (1997).
E. Kushilevitz and N. Nisan, Communication complexity. Cambridge Univ. Press. xiii (1997).
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., Radiofizika 1 (1958) 120-140.
Shannon, C., The synthesis of two-terminal switching circuits. Bell Syst. Techn. J. 28 (1949) 59-98. CrossRef
A.C. Yao, The entropic limitations on VLSI computations, Proceedings, 13th ACM STOC (1981) 308-311.