Construction of very hard functions for multiparty communication complexity
Maňuch, Ján
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 61-75 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_1_61_0,
     author = {Ma\v nuch, J\'an},
     title = {Construction of very hard functions for multiparty communication complexity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {61-75},
     mrnumber = {1771130},
     zbl = {0971.68065},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_1_61_0}
}

Maňuch, Ján. Construction of very hard functions for multiparty communication complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 61-75. http://gdmltest.u-ga.fr/item/ITA_2000__34_1_61_0/

[1] L. Babai, N. Nisan and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings, 21st ACM STOC (1989).

[2] N. Blum, A Boolean function requiring 3n network size. Theoret. Comput. Sci. 28 (1984) 337-345. | MR 742295 | 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. | MR 1181405 | 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. | MR 1371406

[7] P. Ďuriš, Multiparty communication complexity and very hard functions (to appear). | MR 2063621 | Zbl 1087.68036

[8] J. Hromkovič, Communication complexity and parallel Computing, An EATCS Series. Springer (1997). | MR 1442518 | Zbl 0873.68098

[9] E. Kushilevitz and N. Nisan, Communication complexity. Cambridge Univ. Press, xiii (1997). | MR 1426129 | 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. | MR 29860

[13] A. C. Yao, The entropic limitations on VLSI computations, Proceedings, 13th ACM STOC (1981) 308-311.