{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:22:30Z","timestamp":1774369350974,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1993,3,1]],"date-time":"1993-03-01T00:00:00Z","timestamp":730944000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1993,3]]},"DOI":"10.1007\/bf01200404","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:08:35Z","timestamp":1108728515000},"page":"1-18","source":"Crossref","is-referenced-by-count":94,"title":["On lower bounds for read-k-times branching programs"],"prefix":"10.1007","volume":"3","author":[{"given":"A.","family":"Borodin","sequence":"first","affiliation":[]},{"given":"A.","family":"Razborov","sequence":"additional","affiliation":[]},{"given":"R.","family":"Smolensky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"K. Abrahamson, Generalized string matching.SIAM Journal on Computing 16 (1987), 1039?1051.","journal-title":"SIAM Journal on Computing"},{"key":"CR2","first-page":"269","volume":"43","author":"K. Abrahamson","year":"1991","unstructured":"K. Abrahamson, Time-space tradeoffs for algebraic problems on general sequential machines.JCSS 43 (1991), 269?289.","journal-title":"JCSS"},{"key":"CR3","first-page":"118","volume":"37","author":"N. Alon","year":"1988","unstructured":"N. Alon andW. Maass, Meanders and their applications in lower bounds arguments.JCSS 37 (1988), 118?129.","journal-title":"JCSS"},{"key":"CR4","first-page":"153","volume":"35","author":"L. Babai","year":"1987","unstructured":"L. Babai, P. Hajnal, E. Szemer\u00e9di, andG. Turan, A lower bound for read-once branching programs.JCSS 35 (1987), 153?162.","journal-title":"JCSS"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"L. Babai, N. Nisan, and M. Szegedy, Multiparty protocols and logspacehard pseudorandom sequences. InProceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, 1?11.","DOI":"10.1145\/73007.73008"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0304-3975(90)90080-2","volume":"74","author":"L. Babai","year":"1990","unstructured":"L. Babai, P. Pudl\u00e1k, V. R\u00f6dl, andE. Szemer\u00e9di, Lower bounds to the complexity of symmetric boolean functions.Theoretical Computer Science 74 (1990), 313?324.","journal-title":"Theoretical Computer Science"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"D. Barrington and H. Straubing, Superlinear lower bounds for bounded-width branching programs. In6th Structure in Complexity Theory, 1991, 305?313. To appear inJCSS.","DOI":"10.1109\/SCT.1991.160274"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1137\/0220017","volume":"20","author":"P. Beame","year":"1991","unstructured":"P. Beame, A general sequential time-space tradeoff for finding unique elements.SIAM Journal on Computing 20 (1991), 270?277.","journal-title":"SIAM Journal on Computing"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"A. Borodin andS. Cook, A time-space tradeoff for sorting on a general sequential model of computation.SIAM Journal on Computing 11 (1982), 287?297.","journal-title":"SIAM Journal on Computing"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"A. Chandra, M. Furst, and R. Lipton, Multiparty protocols. InProceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, 94?99.","DOI":"10.1145\/800061.808737"},{"key":"CR11","first-page":"90","volume-title":"Proceedings of the FCT, Lecture Notes in Computer Science, 199","author":"P.E. Dunne","year":"1985","unstructured":"P.E. Dunne, Lower bounds on the complexity of 1-time only branching programs. InProceedings of the FCT, Lecture Notes in Computer Science, 199, New York, 1985, Springer-Verlag, 90?99."},{"key":"CR12","unstructured":"M.A. Gavrilov,The Theory of Relay and Switching Circuits. Nauka, 1950. In Russian."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman, Nondeterministic space is closed under complementation.SIAM J. Comput. 17 (1988), 935?938.","journal-title":"SIAM J. Comput."},{"key":"CR14","volume-title":"Basic Algebra I","author":"N. Jacobson","year":"1985","unstructured":"N. Jacobson,Basic Algebra I. W.H. Freeman and Company, New York, second edition, 1985.","edition":"second edition"},{"key":"CR15","unstructured":"S. Jukna,A Note on Read-k Times Branching Programs. Technical Report 448, Universit\u00e4t Dortmund, 1992."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"M. Krause, C. Meinel, and S. Waack, Separating complexity classes related to certain input oblivious logarithmic space bounded Turing machines. In4th Structure in Complexity Theory Conference, 1989, 240?259.","DOI":"10.1109\/SCT.1989.41831"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0304-3975(91)90021-S","volume":"86","author":"M. Krause","year":"1991","unstructured":"M. Krause, C. Meinel, andS. Waack, Separating the eraser turing machine classesL e ,N L e ,co-N L e andP e .Theoretical Computer Science 86 (1991), 267?275.","journal-title":"Theoretical Computer Science"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","volume":"38","author":"C. Y. Lee","year":"1959","unstructured":"C. Y. Lee, Representation of switching cirucits by binary-decision programs.Bell System Technical Journal 38 (1959), 985?999.","journal-title":"Bell System Technical Journal"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"Y. Mansour, N. Nisan, and P. Tiwari, The computational complexity of universal hashing. InProceedings of the 22nd Annual ACM Symposium on the Theory of Computing, 1990, 235?243.","DOI":"10.1145\/100216.100246"},{"key":"CR20","volume-title":"A Fast Algorithm for the String Editing Problem and Decision Graph Complexity","author":"W. Masek","year":"1976","unstructured":"W. Masek,A Fast Algorithm for the String Editing Problem and Decision Graph Complexity. M.Sc. Thesis, Massachusetts Institute of Technology, Cambridge, 1976."},{"key":"CR21","first-page":"61","volume":"51","author":"E. A. Okolnishnikova","year":"1991","unstructured":"E. A. Okolnishnikova, Lower bounds for branching programs computing characteristic functions of binary codes.Metody discretnogo analiza 51 (1991), 61?83, In Russian.","journal-title":"Metody discretnogo analiza"},{"key":"CR22","first-page":"260","volume":"28","author":"C. H. Papadimitriou","year":"1984","unstructured":"C. H. Papadimitriou andM. Sipser, Communication complexity.JCSS 28 (1984), 260?269.","journal-title":"JCSS"},{"key":"CR23","unstructured":"P. Pudl\u00e1k, On bounded depth circuits with arbitrary gates. Preprint."},{"key":"CR24","first-page":"47","volume-title":"Proceedings of the 8th FCT, Lecture Notes in Computer Science, 529","author":"A. Razborov","year":"1991","unstructured":"A. Razborov, Lower bounds for deterministic and nondeterministic branching programs. InProceedings of the 8th FCT, Lecture Notes in Computer Science, 529, New York\/Berlin, 1991, Springer-Verlag, 47?60."},{"key":"CR25","first-page":"177","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities.JCSS 4 (1970), 177?192.","journal-title":"JCSS"},{"key":"CR26","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 Engineers 57 (1938), 713?723.","journal-title":"Transactions of American Institute of Electrical Engineers"},{"key":"CR27","unstructured":"J. Simon and M. Szegedy, Lower bound techniques for read only once branching programs. Preprint, 1990."},{"key":"CR28","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"R. Szelepcs\u00e9nyi, The method of forcing for nondeterministic automata.Bull. European Assoc. Theoret. Comput. Sci. 33 (1987), 96?100.","journal-title":"Bull. European Assoc. Theoret. Comput. Sci."},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"I. Wegener,The Complexity of Boolean Functions. Wiley-Teubner Series in Comp. Sci., New York\/Stuttgart, 1987.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"CR30","first-page":"183","volume":"29","author":"Y. Yesha","year":"1984","unstructured":"Y. Yesha, Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer.SIAM Journal on Computing 29 (1984), 183?197.","journal-title":"SIAM Journal on Computing"},{"key":"CR31","series-title":"Lecture Notes in Computer Science","first-page":"562","volume-title":"Proceedings of the 11th MFCT","author":"S. ?\u00e1k","year":"1984","unstructured":"S. ?\u00e1k, An exponential lower bound for one-time-only branching programs. InProceedings of the 11th MFCT, Lecture Notes in Computer Science, 176, New York\/Berlin, 1984, Springer-Verlag, 562?566."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200404.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200404\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:19:00Z","timestamp":1734956340000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["BF01200404"],"URL":"https:\/\/doi.org\/10.1007\/bf01200404","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}