Branching programs provide lower bounds on the area of VLSI circuits

 Access to full text

 Full (PDF)

1. L. Babai P. Hajnal E. Szemeredi, G. Turán, A lower bound for read-once only branching programs, J. Computer System Sci. 35 (1987), 153-162. (1987) MR0910210
2. D. A. Barrington, Bounded width polynomial-size branching programs recognize exactly those languages in $N{C}^1$, In: Proc. 18th ACM STOC, ACM 1986, pp. 1-5. (1986) 
3. A. Borodin D. Dolev F. E. Fich, W. Paul, Bounds for width two branching programs, In: Proc. 15th ACM STOC, ACM 1983, pp. 87-93. (1983) 
4. A. K. Chandra M. L. Furst, R. J. Lipton, Multiparty protocols, In: Proc. 15th ACM STOC, ACM 1983, pp. 94-99. (1983) 
5. M. Ftáčnik, J. Hromkovič, Nonlinear lower bounds for real-time branching programs, Comput. Artificial Intelligence 4 (1985), 3, 353-359. (1985) 
6. J. Hromkovič, Some complexity aspects of VLSI computations, Part 1. A framework for the study of information transfer in VLSI circuits. Comput. Artificial Intelligence 7 (1988), 3, 229-252. (1988) MR0980773
7. J. Hromkovič, Some complexity aspects of VLSI computations, Part 2. Topology of circuits and information transfer. Comput. Artificial Intelligence 7 (1988), 4, 289-302, (1988) MR0961318
8. J. Hromkovič, Some complexity aspects of VLSI computations, Part 5. Nondeterministic and probabilistic VLSI circuits. Comput. Artificial Intelligence 8 (1989), 2, 169-188. (1989) MR0994291
9. S. P. Jukna, Lower bounds on the complexity of local circuits, In: Mathematical Foundation of Computer Science - Proc. 12th Symposium, Bratislava, Czechoslovakia, August 25-29, 1986 (J. Gruska, B. Rovan, J. Wiedermann, eds.). (Lecture Notes in Computer Science 233.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1986, pp. 440-448. (1986) Zbl0609.94018
10. W. Masek, A Fast Algorithm for String Editing Problem and Decision Graph Complexity, M. Sc. Thesis, MIT, May 1976. (1976) 
11. E. I. Nečiporuk, On a Boolean function, Dokl. Akad. Nauk SSSR 169 (1966), 4, 765-766. English translation: Soviet Math. Dokl. 7 (1966), 999-1000. (1966) MR0218148
12. P. Pudlák, S. Žák, Space complexity of computations, Unpublished manuscript, 1982. (1982) 
13. P. Pudlák, A lower bound on complexity of branching programs, In: Mathematical Foudations of Computer Science - Proc. 11th Symposium, Prague, Czechoslovakia, September 3-7, 1984 (M. P. Chytil, V. Koubek, eds.). (Lecture Notes in Computer Science 176.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984, pp. 480-489. (1984) MR0783479
14. P. Pudlák, The hierarchy of Boolean circuits, Comput. Artificial Intelligence 6 (1987), 5, 449-468. (1987) MR0974649
15. C D. Thompson, A Complexity Theory for VLSI, Doctoral Dissertation, CMU-CS-88-140, Computer Science Dept., Carnegie-Mellon University, Pittsburg, August 1980, 131 p. (1980) 
16. J. D. Ullman, Computational Aspects of VLSI, Computer Science Press, New York 1984. (1984) Zbl0539.68021
17. I. Wegener, On the Complexity of Branching Programs and Decision Trees for Qlique Functions, Universitat Frankfurt, Fachbereich Informatik, Int. Rept. 5/84, 1984. (1984) MR0787469
18. I. Wegener, Time-space trade-offs for branching programs, J. Comput. System. Sci. 32 (1986), 1,91-96. (1986) Zbl0593.68038MR0844204
19. I. Wegener, Optimal decision trees and one-time only branching programs for symmetric Boolean functions, Inform. Control 62 (1984), 129-143. (1984) Zbl0592.94025MR0789891
20. I. Wegener, The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science, B. G. Teubner, Stuttgart, John Wiley and Sons, New York 1987. (1987) Zbl0623.94018MR0905473
21. S. Žák, An exponential lower bound for one-time-only branching programs, In: Mathematical Foundations of Computer Science - Proc. 11th Symposium, Prague, Czechoslovakia, September 3 - 7, 1984 (M. P. Chytil, V. Koubek, eds.). (Lecture Notes in Computer Science 176.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984, pp. 562-566. (1984) MR0783488