Communication complexity and lower bounds on multilective computations

 Access to full text

 Full (PDF)

1. [1] H. Abelson, Lower bounds on information transfer in distributed computations, in Proc. 19th IEEE FOCS, IEEE (1978) 151-158. MR539836
2. [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. [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. [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. [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. Zbl0769.68040MR1186884
6. [6] A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Computational Complexity 3 (1993) 1-18. Zbl0777.68043MR1220075
7. [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. Zbl1078.68633MR1627294
8. [8] P. Ďuriš and Z. Galil, On the power of multiple read in chip. Inform. and Comput. 104 (1993) 277-287. Zbl0783.68061MR1221893
9. [9] P. Ďuriš and Galil Z., Schnitger G., Lower bounds on communication complexity, in Proc. 16th ACM STOC, ACM (1984), 81-91. Zbl0635.68034
10. [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. Zbl0874.68150MR1424992
11. [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. Zbl0925.05067MR1136084
12. [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. Zbl0674.68033MR1147985
13. [13] J. Hromkovič, Nonlinear lower bounds on the number of processors of circuits with sublinear seperators. Inform. and Comput. 95 (1991) 117-128. Zbl0747.94025MR1138114
14. [14] J. Hromkovič, Communication Complexity and Parallel Computing. EATCS Series, Springer (1997). Zbl0873.68098MR1442518
15. [15] M. Krause, Lower bounds for depth-restricted branching programs. Inform. and Comput. 91 (1991) 1-14. Zbl0800.68495MR1097261
16. [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. Zbl0768.68017
17. [17] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048MR1426129
18. [18] R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979) 177-189. Zbl0432.05022MR524495
19. [19] E. A. Okolnishkova, On lower bounds for branching programs. Siberian Advances in Mathematics 3 (1993) 152-166. MR1236757
20. [20] P. Pudlák and S. Žák, Space complexity of computation. Techn. Report, Prague (1983). 
21. [21] M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. STACS'98, Lecture Notes in Computer Science (1373) 105-115. MR1650785
22. [22] J. E. Savage, The performance of multilective VLSI algorithms. J. Comput. System Sci. 29 (1984) 243-273. Zbl0583.68021MR773425
23. [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. Zbl0801.68077MR1255335
24. [24] P. Savický and S. Žák, A large lower bound for 1-branching programs. ECCC Report TR D36-96 (1996). Zbl0947.68056
25. [25] C. D. Thompson, Area-time complexity for VLSI, in Proc. 11th ACM STOC, ACM (1979) 81-88. MR564622
26. [26] Gy. Turán, On restricted Boolean circuits, in Proc. FCT'89, Springer-Verlag, Lecture Notes in Computer Science 380 (1989) 460-469. Zbl0728.94009MR1033574
27. [27] Gy. Turán, Lower bounds for synchronous circuits and planar circuits. Inform. Process. Lett. 30 (1989) 37-40. Zbl0662.94021MR984017
28. [28] Gy. Turán, On the complexity of planar Boolean circuits. Comput. Complexity 5 (1995) 24-42. Zbl0816.68069MR1319491
29. [29] J. D. Ullman, Computational Aspects of VLSI. Comput. Science Press, Rockwille MD (1984). Zbl0539.68021
30. [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). Zbl0623.94018MR905473
31. [31] I. Wegener, On the complexity of branching programs and decision trees for clique funcion. J. Assoc. Comput. Mach. 35 (1988) 461-471. Zbl0652.68063MR935261
32. [32] A. C. Yao, Some complexity questions related to distributive computing, in Proc. 11th ACM STOC, ACM (1979) 209-213. 
33. [33] A. C. Yao, The entropic limitations on VLSI computations, in Proc. 11th ACM STOC, ACM (1979) 209-213. 
34. [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. Zbl0558.68044MR783488
35. [35] S. Žák, An exponential lower bound for real-time branching programs. Inform. and Control 71 (1986) 87-94. Zbl0627.68044MR864746