Communication complexity and lower bounds on multilective computations
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 2, pp. 193-212. 
@article{ITA_1999__33_2_193_0,
     author = {Hromkovi\v{c}, Juraj},
     title = {Communication complexity and lower bounds on multilective computations},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {193--212},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {2},
     year = {1999},
     mrnumber = {1707970},
     zbl = {0946.68052},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1999__33_2_193_0/}
}
TY  - JOUR
AU  - Hromkovič, Juraj
TI  - Communication complexity and lower bounds on multilective computations
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1999
SP  - 193
EP  - 212
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1999__33_2_193_0/
LA  - en
ID  - ITA_1999__33_2_193_0
ER  - 
%0 Journal Article
%A Hromkovič, Juraj
%T Communication complexity and lower bounds on multilective computations
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 193-212
%V 33
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1999__33_2_193_0/
%G en
%F ITA_1999__33_2_193_0
Hromkovič, Juraj. Communication complexity and lower bounds on multilective computations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 2, pp. 193-212. http://www.numdam.org/item/ITA_1999__33_2_193_0/

[1] H. Abelson, Lower bounds on information transfer in distributed computations, in Proc. 19th IEEE FOCS, IEEE (1978) 151-158. | MR

[2] N. Alon and W. Maas, Meanders, Ramsey theory and lower bounds for branching programs, in Proc.27th IEEE FOCS, IEEE (1986) 410-417.

[3] M. Ajtai, L. Babai, P. Hajnal, J. Komlós, P. Pudlák, V. Rödl, E. Szemerédi and G. Turán, Two lower bounds for branching programs, in Proc. 18th ACM STOC, ACM (1986) 30-38.

[4] A.V. Aho, J. D. Ullman and M. Yanakakis, On notions of information transfer in VLSI circuits, in Proc. 15th ACM STOC, ACM (1983) 133-139.

[5] L. Babai, N. Nisan and M. Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput, System Sci. 45 (1992) 204-232. | MR | Zbl

[6] A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Computational Complexity 3 (1993) 1-18. | MR | Zbl

[7] B. Bollig and I. Wegener, A very simple function that requires exponential size read-once branching programs. Inform. Process. Lett. 66 (1998) 53-57. | MR | Zbl

[8] P. Ďuriš and Z. Galil, On the power of multiple read in chip. Inform. and Comput. 104 (1993) 277-287. | MR | Zbl

[9] P. Ďuriš and Galil Z., Schnitger G., Lower bounds on communication complexity, in Proc. 16th ACM STOC, ACM (1984), 81-91.

[10] M. Dietzfelbinger, J. Hromkovič and G. Schnitger, A comparison of two lower bounds methods for communication complexity. Theoret. Comput. Sci. 168 (1996), 39-51. | MR | Zbl

[11] H. D. Grœger, A new partition lemma for planar graphs and its application to circuit complexity, in Proc. FCT'91, Springer-Verlag, Lecture Notes in Computer Science 529 (1991) 220-229. | MR | Zbl

[12] J. Hromkovič, M. Krause, Meinel And Ch., S. Waack, Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits. Inform. and Comput. 95 (1992) 117-128. | MR | Zbl

[13] J. Hromkovič, Nonlinear lower bounds on the number of processors of circuits with sublinear seperators. Inform. and Comput. 95 (1991) 117-128. | MR | Zbl

[14] J. Hromkovič, Communication Complexity and Parallel Computing. EATCS Series, Springer (1997). | MR | Zbl

[15] M. Krause, Lower bounds for depth-restricted branching programs. Inform. and Comput. 91 (1991) 1-14. | MR | Zbl

[16] M. Krause, Ch. Meinel and S. Waack, Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines, in Proc. Structure in Complexity Theory (1989) 240-249.

[17] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). | MR | Zbl

[18] R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979) 177-189. | MR | Zbl

[19] E. A. Okolnishkova, On lower bounds for branching programs. Siberian Advances in Mathematics 3 (1993) 152-166. | MR

[20] P. Pudlák and S. Žák, Space complexity of computation. Techn. Report, Prague (1983).

[21] M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. STACS'98, Lecture Notes in Computer Science (1373) 105-115. | MR

[22] J. E. Savage, The performance of multilective VLSI algorithms. J. Comput. System Sci. 29 (1984) 243-273. | MR | Zbl

[23] J. Simon and M. Szegedy, A new lower bound theorem for read-only-once branching programs and its application, J. Cai, Ed., Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13, AMS (1993) 183-193. | MR | Zbl

[24] P. Savický and S. Žák, A large lower bound for 1-branching programs. ECCC Report TR D36-96 (1996).

[25] C. D. Thompson, Area-time complexity for VLSI, in Proc. 11th ACM STOC, ACM (1979) 81-88. | MR

[26] Gy. Turán, On restricted Boolean circuits, in Proc. FCT'89, Springer-Verlag, Lecture Notes in Computer Science 380 (1989) 460-469. | MR | Zbl

[27] Gy. Turán, Lower bounds for synchronous circuits and planar circuits. Inform. Process. Lett. 30 (1989) 37-40. | MR | Zbl

[28] Gy. Turán, On the complexity of planar Boolean circuits. Comput. Complexity 5 (1995) 24-42. | MR | Zbl

[29] J. D. Ullman, Computational Aspects of VLSI. Comput. Science Press, Rockwille MD (1984). | Zbl

[30] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, John Wiley and Sons Ltd., and Teubner, B.G., Stuttgart (1987). | MR | Zbl

[31] I. Wegener, On the complexity of branching programs and decision trees for clique funcion. J. Assoc. Comput. Mach. 35 (1988) 461-471. | MR | Zbl

[32] A. C. Yao, Some complexity questions related to distributive computing, in Proc. 11th ACM STOC, ACM (1979) 209-213.

[33] A. C. Yao, The entropic limitations on VLSI computations, in Proc. 11th ACM STOC, ACM (1979) 209-213.

[34] S. Žák, An exponential lower bound for one-time-only branching programs, in Proc MFCS'84, Springer, Berlin, Lecture Notes in Computer Science 176 (1984) 562-566. | MR | Zbl

[35] S. Žák, An exponential lower bound for real-time branching programs. Inform. and Control 71 (1986) 87-94. | MR | Zbl