{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:59:12Z","timestamp":1775282352453,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540544586","type":"print"},{"value":"9783540383918","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54458-5_49","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:53:31Z","timestamp":1330210411000},"page":"47-60","source":"Crossref","is-referenced-by-count":48,"title":["Lower bounds for deterministic and nondeterministic branching programs"],"prefix":"10.1007","author":[{"given":"Alexander A.","family":"Razborov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, L. Babai, P. Hajnal, J. Komlos, P. Pudl\u00e1k, V. R\u00f6dl, E. Szemeredi, and Gy. Tur\u00e1n. Two lower bounds for branching programs. In Proceedings of the 18st ACM STOC, pages 30\u201338, 1986.","DOI":"10.1145\/12130.12134"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemeredi. An O(n log n) sorting network. In Proceedings of the 15st ACM STOC, pages 1\u20139, 1983.","DOI":"10.1145\/800061.808726"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"R. Aleluinas, R. M. Karp, R. J. Lipton, R. J. Lov\u00e1sz, and C. Rackoff. Random walks, universal sequences and the complexity of maze problems. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pages 218\u2013223, 1979.","DOI":"10.1109\/SFCS.1979.34"},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0022-0000(88)90002-5","volume":"37","author":"N. Alon","year":"1988","unstructured":"N. Alon and W. Maass. Meanders and their applications in lower bounds arguments. Journal of Computer and System Sciences, 37:118\u2013129, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols and logspace-hard pseudorandom sequences. In Proceedings of the 21st ACM STOC, pages 1\u201311, 1989.","DOI":"10.1145\/73007.73008"},{"key":"6_CR6","unstructured":"L. Babai, P. Pudl\u00e1k, V. R\u00f6dl, and E. Szemeredi. Lower bounds in complexity of symmetric Boolean functions. 1988. To appear in Theoretical Computer Science."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. In Proceedings of the 18st ACM STOC, pages 1\u20135, 1986.","DOI":"10.1145\/12130.12131"},{"key":"6_CR8","unstructured":"D. A. Barrington and H. Straubing. Superlinear lower bounds for bounded-width branching programs. 1990. Preprint."},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"R. B. Boppana and M. Sipser. The complexity of finite functions. In Jan Van Leeuwen, editor, Handbook of Theoretical Computer Science, vol. A (Algorithms and Complexity), chapter 14, pages 757\u2013804, Elsevier Science Publishers B.V. and The MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"issue":"2","key":"6_CR10","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing, 11(2):287\u2013297, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"A. Borodin, D. Dolev, F. Fich, and W. Paul. Bounds for width 2 branching programs. In Proceedings of the 15st ACM STOC, pages 87\u201393, 1983.","DOI":"10.1145\/800061.808736"},{"key":"6_CR12","unstructured":"A. Borodin, A. Razborov, and R. Smolensky. On lower bounds for read-k times branching programs. May 1991. Submitted to Computational Complexity."},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Jin-yi Cai and R. J. Lipton. Subquadratic simulations of circuits by branching programs. In Proceedings of the 30st IEEE FOCS, pages 568\u2013573, 1989.","DOI":"10.1109\/SFCS.1989.63536"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"A. Chandra, M. Furst, and R. Lipton. Multiparty protocols. In Proceedings of the 15th ACM STOC, pages 94\u201399, 1983.","DOI":"10.1145\/800061.808737"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"R. Cleve. Towards optimal simulations of formulas by bounded-width programs. In Proceedings of the 22th ACM STOC, pages 271\u2013277, 1990.","DOI":"10.1145\/100216.100251"},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/BFb0028795","volume-title":"Proceedings of the FCT","author":"P. E. Dunne","year":"1985","unstructured":"P. E. Dunne. Lower bounds on the complexity of one-time-only branching programs. In Proceedings of the FCT, Lecture Notes in Computer Science, 199, pages 90\u201399, Springer-Verlag, New York\/Berlin, 1985."},{"key":"6_CR17","unstructured":"M. A. Gavrilov. The theory of relay and switching circuits. Nauka, 1950. In Russian."},{"key":"6_CR18","volume-title":"On the switching network size of symmetric Boolean functions","author":"M. I. Grinchuk","year":"1989","unstructured":"M. I. Grinchuk. On the switching network size of symmetric Boolean functions (in Russian). Master's thesis, Moscow State University, Moscow, 1989."},{"key":"6_CR19","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Massachussetts, 1979."},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. In Proceedings of the 3rd Structures in Complexity Theory Annual Conference, pages 112\u2013115, 1988.","DOI":"10.1109\/SCT.1988.5270"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/BFb0016269","volume-title":"Proceedings of the MFCT'86","author":"S. Jukna","year":"1986","unstructured":"S. Jukna. Lower bounds on the complexity of local circuits. In Proceedings of the MFCT'86, Lecture Notes in Computer Science, 233, pages 440\u2013448, Springer-Verlag, New York\/Berlin, 1986."},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"R. Kannan. A circuit size lower bound. In Proceedings of the 22th IEEE Symposium on Foundations of Computer Science, pages 304\u2013309, 1981.","DOI":"10.1109\/SFCS.1981.1"},{"key":"6_CR23","unstructured":"M. Krause. Exponential lower bounds on the complexity of local and real-time branching programs. 1986. To appear in J. Inform. Process. Cybern. (EIK)."},{"issue":"1","key":"6_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(91)90072-A","volume":"91","author":"M. Krause","year":"1991","unstructured":"M. Krause. Lower bounds for depth-restricted branching programs. Information and Computation, 91(1):1\u201314, 1991.","journal-title":"Information and Computation"},{"key":"6_CR25","series-title":"Lecture Notes in Computer Science","first-page":"90","volume-title":"Proceedings of the FCT","author":"K. Kriegel","year":"1987","unstructured":"K. Kriegel and S. Waack. Lower bounds on the complexity of real-time branching programs. In Proceedings of the FCT, Lecture Notes in Computer Science, 278, pages 90\u201399, Springer-Verlag, New York\/Berlin, 1987."},{"key":"6_CR26","first-page":"85","volume":"15","author":"O. B. Lupanov","year":"1965","unstructured":"O. B. Lupanov. On computing symmetric functions of the propositional calculus by switching networks (in Russian). In Problems of Cybernetics, vol. 15, pages 85\u2013100, Nauka, 1965.","journal-title":"Problems of Cybernetics"},{"key":"6_CR27","first-page":"117","volume":"8","author":"A. A. Markov","year":"1962","unstructured":"A. A. Markov. On minimal switching-and-rectifier networks for monotone symmetric functions (in Russian). In Problems of Cybernetics, vol. 8, pages 117\u2013121, Nauka, 1962.","journal-title":"Problems of Cybernetics"},{"key":"6_CR28","unstructured":"W. Masek. A fast algorithm for the string edidting problem and decision graph complexity. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1976."},{"issue":"4","key":"6_CR29","first-page":"765","volume":"169","author":"E. I. Ne\u010diporuk","year":"1966","unstructured":"E. I. Ne\u010diporuk. On a Boolean function. Doklady of the Academy of Sciences of the USSR, 169(4):765\u2013766 (in Russian), 1966. English translation in Soviet Mathematics Doklady 7:4, pages 999\u20131000.","journal-title":"Doklady of the Academy of Sciences of the USSR"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Sipser. Communication complexity. In Proceedings of the 14th ACM STOC, pages 196\u2013200, 1982.","DOI":"10.1145\/800070.802192"},{"key":"6_CR31","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/0304-3975(76)90090-6","volume":"2","author":"M. S. Paterson","year":"1976","unstructured":"M. S. Paterson and L. G. Valiant. Circuit size is nonlinear in depth. Theoretical Computer Science, 2:397\u2013400, 1976.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"6_CR32","first-page":"449","volume":"6","author":"P. Pudl\u00e1k","year":"1987","unstructured":"P. Pudl\u00e1k. The hierarchy of Boolean circuits. Computers and Artificial Intelligence, 6(5):449\u2013468, 1987.","journal-title":"Computers and Artificial Intelligence"},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1007\/BFb0030331","volume-title":"Proceedings of the 11th MFCT","author":"P. Pudl\u00e1k","year":"1984","unstructured":"P. Pudl\u00e1k. A lower bound on complexity of branching programs. In Proceedings of the 11th MFCT, Lecture Notes in Computer Science, 176, pages 480\u2013489, Springer-Verlag, New York\/Berlin, 1984."},{"issue":"6","key":"6_CR34","first-page":"79","volume":"48","author":"A. A. Razborov","year":"1990","unstructured":"A. A. Razborov. Lower bounds on the size of switching-and-rectifier networks for symmetric Boolean functions. Mathematical Notes of the Academy of Sciences of the USSR, 48(6):79\u201391, 1990.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"A. A. Razborov. On the method of approximation. In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 167\u2013176, 1989.","DOI":"10.1145\/73007.73023"},{"key":"6_CR36","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1109\/T-AIEE.1938.5057767","volume":"57","author":"C. Shannon","year":"1938","unstructured":"C. Shannon. A symbolic analysis of relay and switching networks. Transactions of American Institute of Electrical Engeneers, 57:713\u2013723, 1938.","journal-title":"Transactions of American Institute of Electrical Engeneers"},{"issue":"1","key":"6_CR37","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C. Shannon","year":"1949","unstructured":"C. Shannon. The synthesis of two-terminal switching circuits. Bell Systems Technical Journal, 28(1):59\u201398, 1949.","journal-title":"Bell Systems Technical Journal"},{"key":"6_CR38","unstructured":"J. Simon and M. Szegedy. Lower bound techniques for read only once branching programs. November 1990. Preprint."},{"key":"6_CR39","first-page":"525","volume-title":"Proceedings of the 4th Hawaii Symposium on System Sciences","author":"P. M. Spira","year":"1971","unstructured":"P. M. Spira. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences, pages 525\u2013527, Western Periodicals Company, North Hollywood, 1971."},{"key":"6_CR40","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"R. Szelepcs\u00e9nyi. The method of forcing for nondeterministic automata. Bulletin of the EATCS, 33:96\u201399, 1987.","journal-title":"Bulletin of the EATCS"},{"key":"6_CR41","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant. Short monotone formulae for the majority function. Journal of Algorithms, 5:363\u2013366, 1984.","journal-title":"Journal of Algorithms"},{"key":"6_CR42","doi-asserted-by":"crossref","unstructured":"I. Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"6_CR43","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/42282.46161","volume":"35","author":"I. Wegener","year":"1988","unstructured":"I. Wegener. On the complexity of branching programs and decision trees for clique functions. Assoc. Comput. Math., 35:461\u2013471, 1988.","journal-title":"Assoc. Comput. Math."},{"key":"6_CR44","doi-asserted-by":"crossref","unstructured":"A. Yao. Lower bounds by probabilistic arguments. In Proceedings of the 24th IEEE FOCS, pages 420\u2013428, 1983.","DOI":"10.1109\/SFCS.1983.30"},{"key":"6_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/BFb0030340","volume-title":"Proceedings of the 11th MFCT","author":"S. \u017d\u00e1k","year":"1984","unstructured":"S. \u017d\u00e1k. An exponential lower bound for one-time-only branching programs. In Proceedings of the 11th MFCT, Lecture Notes in Computer Science, 176, pages 562\u2013566, Springer-Verlag, New York\/Berlin, 1984."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54458-5_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:54:46Z","timestamp":1605646486000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54458-5_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544586","9783540383918"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3-540-54458-5_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}