×

zbMATH — the first resource for mathematics

Branching programs provide lower bounds on the area of VLSI circuits. (English) Zbl 0746.68039
Summary: Branching programs that were studied as nonuniform computing model providing lower bounds on the space of deterministic sequential computations are considered. We show that they can be used for providing lower bound on the parallel VLSI computations.
MSC:
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: Link EuDML
References:
[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. · Zbl 0652.68062 · doi:10.1016/0022-0000(87)90010-9
[2] D. A. Barrington: Bounded width polynomial-size branching programs recognize exactly those languages in \(NC^{1}\). Proc. 18th ACM STOC, ACM 1986, pp. 1-5. · Zbl 0667.68059 · doi:10.1016/0022-0000(89)90037-8
[3] A. Borodin D. Dolev F. E. Fich, W. Paul: Bounds for width two branching programs. Proc. 15th ACM STOC, ACM 1983, pp. 87-93. · Zbl 0589.68034 · doi:10.1137/0215040
[4] A. K. Chandra M. L. Furst, R. J. Lipton: Multiparty protocols. Proc. 15th ACM STOC, ACM 1983, pp. 94-99.
[5] M. Ftáčnik, J. Hromkovič: Nonlinear lower bounds for real-time branching programs. Comput. Artificial Intelligence 4 (1985), 3, 353-359. · Zbl 0579.68031
[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. · Zbl 0644.94027
[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, · Zbl 0649.94022
[8] J. Hromkovič: Some complexity aspects of VLSI computations. Part 5. Nondeterministic and probabilistic VLSI circuits. Comput. Artificial Intelligence 8 (1989), 2, 169-188. · Zbl 0673.68030
[9] S. P. Jukna: Lower bounds on the complexity of local circuits. Mathematical Foundation of Computer Science - Proc. 12th Symposium, Bratislava, Czechoslovakia, August 25-29, 1986 (J. Gruska, B. Rovan, J. Wiedermann. (Lecture Notes in Computer Science 233.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1986, pp. 440-448. · Zbl 0609.94018
[10] W. Masek: A Fast Algorithm for String Editing Problem and Decision Graph Complexity. M. Sc. Thesis, MIT, May 1976.
[11] E. I. Nečiporuk: On a Boolean function. Dokl. Akad. Nauk SSSR 169 (1966), 4, 765-766.
[12] P. Pudlák, S. Žák: Space complexity of computations. Unpublished manuscript, 1982.
[13] P. Pudlák: A lower bound on complexity of branching programs. Mathematical Foudations of Computer Science - Proc. 11th Symposium, Prague, Czechoslovakia, September 3-7, 1984 (M. P. Chytil, V. Koubek. (Lecture Notes in Computer Science 176.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984, pp. 480-489. · Zbl 0572.68033
[14] P. Pudlák: The hierarchy of Boolean circuits. Comput. Artificial Intelligence 6 (1987), 5, 449-468. · Zbl 0641.94028
[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.
[16] J. D. Ullman: Computational Aspects of VLSI. Computer Science Press, New York 1984. · Zbl 0539.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.
[18] I. Wegener: Time-space trade-offs for branching programs. J. Comput. System. Sci. 32 (1986), 1,91-96. · Zbl 0593.68038 · doi:10.1016/0022-0000(86)90004-8
[19] I. Wegener: Optimal decision trees and one-time only branching programs for symmetric Boolean functions. Inform. Control 62 (1984), 129-143. · Zbl 0592.94025 · doi:10.1016/S0019-9958(84)80031-5
[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. · Zbl 0623.94018
[21] S. Žák: An exponential lower bound for one-time-only branching programs. Mathematical Foundations of Computer Science - Proc. 11th Symposium, Prague, Czechoslovakia, September 3 - 7, 1984 (M. P. Chytil, V. Koubek. (Lecture Notes in Computer Science 176.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984, pp. 562-566.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.