@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] Lower bounds on information transfer in distributed computations, in Proc. 19th IEEE FOCS, IEEE (1978) 151-158. | MR
,[2] Meanders, Ramsey theory and lower bounds for branching programs, in Proc.27th IEEE FOCS, IEEE (1986) 410-417.
and ,[3] Two lower bounds for branching programs, in Proc. 18th ACM STOC, ACM (1986) 30-38.
, , , , , , and ,[4] On notions of information transfer in VLSI circuits, in Proc. 15th ACM STOC, ACM (1983) 133-139.
, and ,[5] Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput, System Sci. 45 (1992) 204-232. | MR | Zbl
, and ,[6] On lower bounds for read-k-times branching programs. Computational Complexity 3 (1993) 1-18. | MR | Zbl
, and ,[7] A very simple function that requires exponential size read-once branching programs. Inform. Process. Lett. 66 (1998) 53-57. | MR | Zbl
and ,[8] On the power of multiple read in chip. Inform. and Comput. 104 (1993) 277-287. | MR | Zbl
and ,[9] Lower bounds on communication complexity, in Proc. 16th ACM STOC, ACM (1984), 81-91.
and , ,[10] A comparison of two lower bounds methods for communication complexity. Theoret. Comput. Sci. 168 (1996), 39-51. | MR | Zbl
, and ,[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 | Zbl
,[12] 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] Nonlinear lower bounds on the number of processors of circuits with sublinear seperators. Inform. and Comput. 95 (1991) 117-128. | MR | Zbl
,[14] Communication Complexity and Parallel Computing. EATCS Series, Springer (1997). | MR | Zbl
,[15] Lower bounds for depth-restricted branching programs. Inform. and Comput. 91 (1991) 1-14. | MR | Zbl
,[16] Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines, in Proc. Structure in Complexity Theory (1989) 240-249.
, and ,[17] Communication Complexity. Cambridge University Press (1997). | MR | Zbl
and ,[18] A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979) 177-189. | MR | Zbl
and ,[19] On lower bounds for branching programs. Siberian Advances in Mathematics 3 (1993) 152-166. | MR
,[20] Space complexity of computation. Techn. Report, Prague (1983).
and ,[21] Lower bounds for randomized read-k-times branching programs, in Proc. STACS'98, Lecture Notes in Computer Science (1373) 105-115. | MR
,[22] The performance of multilective VLSI algorithms. J. Comput. System Sci. 29 (1984) 243-273. | MR | Zbl
,[23] 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
and ,[24] A large lower bound for 1-branching programs. ECCC Report TR D36-96 (1996).
and ,[25] Area-time complexity for VLSI, in Proc. 11th ACM STOC, ACM (1979) 81-88. | MR
,[26] On restricted Boolean circuits, in Proc. FCT'89, Springer-Verlag, Lecture Notes in Computer Science 380 (1989) 460-469. | MR | Zbl
,[27] Lower bounds for synchronous circuits and planar circuits. Inform. Process. Lett. 30 (1989) 37-40. | MR | Zbl
,[28] On the complexity of planar Boolean circuits. Comput. Complexity 5 (1995) 24-42. | MR | Zbl
,[29] Computational Aspects of VLSI. Comput. Science Press, Rockwille MD (1984). | Zbl
,[30] 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] On the complexity of branching programs and decision trees for clique funcion. J. Assoc. Comput. Mach. 35 (1988) 461-471. | MR | Zbl
,[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 | Zbl
,[35] An exponential lower bound for real-time branching programs. Inform. and Control 71 (1986) 87-94. | MR | Zbl
,