@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},
volume = {33},
year = {1999},
pages = {193-212},
mrnumber = {1707970},
zbl = {0946.68052},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 193-212. http://gdmltest.u-ga.fr/item/ITA_1999__33_2_193_0/
[1] , Lower bounds on information transfer in distributed computations, in Proc. 19th IEEE FOCS, IEEE (1978) 151-158. | MR 539836
[2] and , Meanders, Ramsey theory and lower bounds for branching programs, in Proc.27th IEEE FOCS, IEEE (1986) 410-417.
[3] , , , , , , and , Two lower bounds for branching programs, in Proc. 18th ACM STOC, ACM (1986) 30-38.
[4] , and , On notions of information transfer in VLSI circuits, in Proc. 15th ACM STOC, ACM (1983) 133-139.
[5] , and , 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] , and , On lower bounds for read-k-times branching programs. Computational Complexity 3 (1993) 1-18. | MR 1220075 | Zbl 0777.68043
[7] and , 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] and , On the power of multiple read in chip. Inform. and Comput. 104 (1993) 277-287. | MR 1221893 | Zbl 0783.68061
[9] and , , Lower bounds on communication complexity, in Proc. 16th ACM STOC, ACM (1984), 81-91.
[10] , and , A comparison of two lower bounds methods for communication complexity. Theoret. Comput. Sci. 168 (1996), 39-51. | MR 1424992 | Zbl 0874.68150
[11] , 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] , , , , 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] , 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] , Communication Complexity and Parallel Computing. EATCS Series, Springer (1997). | MR 1442518 | Zbl 0873.68098
[15] , Lower bounds for depth-restricted branching programs. Inform. and Comput. 91 (1991) 1-14. | MR 1097261 | Zbl 0800.68495
[16] , and , Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines, in Proc. Structure in Complexity Theory (1989) 240-249.
[17] and , Communication Complexity. Cambridge University Press (1997). | MR 1426129 | Zbl 0869.68048
[18] and , A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979) 177-189. | MR 524495 | Zbl 0432.05022
[19] , On lower bounds for branching programs. Siberian Advances in Mathematics 3 (1993) 152-166. | MR 1236757
[20] and , Space complexity of computation. Techn. Report, Prague (1983).
[21] , Lower bounds for randomized read-k-times branching programs, in Proc. STACS'98, Lecture Notes in Computer Science (1373) 105-115. | MR 1650785
[22] , The performance of multilective VLSI algorithms. J. Comput. System Sci. 29 (1984) 243-273. | MR 773425 | Zbl 0583.68021
[23] and , 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] and , A large lower bound for 1-branching programs. ECCC Report TR D36-96 (1996).
[25] , Area-time complexity for VLSI, in Proc. 11th ACM STOC, ACM (1979) 81-88. | MR 564622
[26] , 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] , Lower bounds for synchronous circuits and planar circuits. Inform. Process. Lett. 30 (1989) 37-40. | MR 984017 | Zbl 0662.94021
[28] , On the complexity of planar Boolean circuits. Comput. Complexity 5 (1995) 24-42. | MR 1319491 | Zbl 0816.68069
[29] , Computational Aspects of VLSI. Comput. Science Press, Rockwille MD (1984). | Zbl 0539.68021
[30] , 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] , 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] , Some complexity questions related to distributive computing, in Proc. 11th ACM STOC, ACM (1979) 209-213.
[33] , The entropic limitations on VLSI computations, in Proc. 11th ACM STOC, ACM (1979) 209-213.
[34] , 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] , An exponential lower bound for real-time branching programs. Inform. and Control 71 (1986) 87-94. | MR 864746 | Zbl 0627.68044