×

Multiparty communication complexity and very hard functions. (English) Zbl 1087.68036

Summary: A Boolean function \(f(x_1,\dots,x_n)\) with \(x_i\in\{0,1\}^m\) for each \(i\) is hard if its nondeterministic multiparty communication complexity, \(C(f)\), is at least \(nm\). Note that \(C(f)\leq nm\) for each \(f(x_1,\dots,x_n)\) with \(x_i\in \{0,1\}^m\) for each \(i\). A Boolean function is very hard if it is hard and its complementary function is also hard. In this paper, we show that randomly chosen Boolean function \(f(x_1,\dots,x_n)\) with \(x_i\in\{0,1\}^m\) for each \(i\) is very hard with very high probability (for \(n\geq 3\) and \(m\) large enough). P. Ďuriš and J. P. D. Rolim [J. Comput. Syst. Sci. 56, 90–95 (1998; Zbl 0917.94024)] have shown that if \(f(x_1,\dots,x_k,\dots,x_n)= f_1(x_1, \dots,x_k)\cdot f_2(x_{k+1},\dots,x_n)\), where \(C(f_1)>0\) and \(C(f_2)>0\), then \(C(f)=C(f_1)+C(f_2)\). We prove here an analogous result: If \(f(x_1,\dots,x_k, \dots,x_n)=f_1(x_1,\dots,x_k) \oplus f_2(x_{k+1},\dots,x_n)\) then \(\text{DC}(f)=\text{DC}(f_1)+ \text{DC}(f_2)\), where \(\text{DC}(g)\) denotes the deterministic multiparty communication complexity of the function \(g\) and “\(\oplus\)” denotes the parity function.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 0917.94024
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.V. Aho, J.D. Ullman, M.Y. Yanakakis, On notion of information transfer in VLSI, in: Proceedings of the 15th ACM STOC, 1983, pp. 133-139; A.V. Aho, J.D. Ullman, M.Y. Yanakakis, On notion of information transfer in VLSI, in: Proceedings of the 15th ACM STOC, 1983, pp. 133-139
[2] L. Babai, N. Nisan, M. Szegedy, Multiparty protocols and log-space hard pseudorandom sequences, in: Proceedings of the 21st ACM STOC, 1989, pp. 1-11; L. Babai, N. Nisan, M. Szegedy, Multiparty protocols and log-space hard pseudorandom sequences, in: Proceedings of the 21st ACM STOC, 1989, pp. 1-11
[3] A.K. Chandra, M.L. Furst, R.J. Lipton, Multi-party protocols, in: Proceedings of the 15th ACM STOC, 1983, pp. 94-99; A.K. Chandra, M.L. Furst, R.J. Lipton, Multi-party protocols, in: Proceedings of the 15th ACM STOC, 1983, pp. 94-99
[4] D. Dolev, T. Feder, Multiparty communication complexity, in: Proceedings of the 30th IEEE FOCS, 1989, pp. 428-433; D. Dolev, T. Feder, Multiparty communication complexity, in: Proceedings of the 30th IEEE FOCS, 1989, pp. 428-433
[5] Ďuriš, P.; Galil, Z.; Schnitger, G., Lower bounds on communication complexity, Information and Computation, 73, 1-22 (1987) · Zbl 0635.68034
[6] P. Ďuriš, J.D.P. Rolim, Optimal lower bounds on the multiparty communication complexity, in: Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science, LNCS 900, 1995, pp. 350-360; P. Ďuriš, J.D.P. Rolim, Optimal lower bounds on the multiparty communication complexity, in: Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science, LNCS 900, 1995, pp. 350-360 · Zbl 1379.68129
[7] M. Fürer, The power of randomness in communication complexity, in: Proceedings of the 19th ACM STOC, 1987, pp. 178-181; M. Fürer, The power of randomness in communication complexity, in: Proceedings of the 19th ACM STOC, 1987, pp. 178-181
[8] Kushilevitz, E.; Nisan, N., Communication Complexity (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0869.68048
[9] Maňuch, J., Construction of very hard functions for multiparty communication complexity, Theoretical Informatics and Applications, 34, 61-76 (2000) · Zbl 0971.68065
[10] K. Melhorn, E.M. Schmidt, Las Vegas is better in VLSI and distributed computing, in: Proceedings of the 14th ACM STOC, 1982, pp. 330-337; K. Melhorn, E.M. Schmidt, Las Vegas is better in VLSI and distributed computing, in: Proceedings of the 14th ACM STOC, 1982, pp. 330-337
[11] C.H. Papadimitriou, M. Sipser, Communication complexity. in: Proceedings of the 14th ACM STOC, 1982, pp. 196-200; C.H. Papadimitriou, M. Sipser, Communication complexity. in: Proceedings of the 14th ACM STOC, 1982, pp. 196-200
[12] A. Yao, Some complexity questions related to distributive computing, in: Proceedings of the 11th ACM STOC, 1979, pp. 209-213; A. Yao, Some complexity questions related to distributive computing, in: Proceedings of the 11th ACM STOC, 1979, pp. 209-213
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.