×

Construction of very hard functions for multiparty communication complexity. (English) Zbl 0971.68065

Summary: We consider the multiparty communication model defined in [D. Dolev and T. Feder, Multiparty communication complexity, Proceedings, 30th IEEE FOCS, 428-433 (1989)] using the formalism from [J. Hromkovič, Texts in Theoretical Computer Science (1997; Zbl 0873.68098)]. First, we correct an inaccuracy in the proof of the fundamental result of P. Ďuriš and J. D. P. Rolim [Lect. Notes Comput. Sci. 900, 350-360 (1995)] 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 [P. Ďuriš, Multiparty communication complexity and very hard functions (to appear)], 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.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Citations:

Zbl 0873.68098
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[1] L. Babai, N. Nisan and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings, 21st ACM STOC (1989). · Zbl 0769.68040
[2] N. Blum, A Boolean function requiring 3n network size. Theoret. Comput. Sci. 28 (1984) 337-345. Zbl0539.94036 MR742295 · Zbl 0539.94036
[3] A. K. Chandra, M. L. Furst and R. J. Lipton, Multi-party protocols, Proceedings, 15th ACM STOC (1983) 94-99.
[4] D. Dolev and T. Feder, Multiparty communication complexity, Proceedings, 30th IEEE FOCS (1989) 428-433.
[5] D. Dolev and T. Feder, Determinism vs. nondeterminism in multiparty communication complexity. SIAM J. Comput. 21 (1992) 89-893. Zbl0765.68033 MR1181405 · Zbl 0765.68033
[6] P. Ďuriš 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. MR1371406 · Zbl 1379.68129
[7] P. Ďuriš, Multiparty communication complexity and very hard functions (to appear). Zbl1087.68036 MR2063621 · Zbl 1087.68036
[8] J. Hromkovič, Communication complexity and parallel Computing, An EATCS Series. Springer (1997). Zbl0873.68098 MR1442518 · Zbl 0873.68098
[9] E. Kushilevitz and N. Nisan, Communication complexity. Cambridge Univ. Press, xiii (1997). Zbl0869.68048 MR1426129 · Zbl 0869.68048
[10] R. J. Lipton and R. Sedgewick, Lower bounds for VLSI, Proceedings, 13th ACM STOC (1981) 300-307.
[11] O. B. Lupanov, Ob odnom metode sinteza skhem (Russian). Izv. Vyssh. Uchebn. Zaved., Radiofizika 1 (1958) 120-140.
[12] C. Shannon, The synthesis of two-terminal switching circuits. Bell Syst. Techn. J. 28 (1949) 59-98. MR29860
[13] A. C. Yao, The entropic limitations on VLSI computations, Proceedings, 13th ACM STOC (1981) 308-311.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.