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},
zbl = {0946.68052},
mrnumber = {1707970},
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
DA  - 1999///
SP  - 193
EP  - 212
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1999__33_2_193_0/
UR  - https://zbmath.org/?q=an%3A0946.68052
UR  - https://www.ams.org/mathscinet-getitem?mr=1707970
LA  - en
ID  - ITA_1999__33_2_193_0
ER  - 
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 539836

[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 1186884 | Zbl 0769.68040

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

[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 1627294 | Zbl 1078.68633

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

[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 1424992 | Zbl 0874.68150

[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 1136084 | Zbl 0925.05067

[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 1147985 | Zbl 0674.68033

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

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

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

[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 1426129 | Zbl 0869.68048

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

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

[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 1650785

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

[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 1255335 | Zbl 0801.68077

[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 564622

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

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

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

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

[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 905473 | Zbl 0623.94018

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

[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 783488 | Zbl 0558.68044

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