{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T18:40:21Z","timestamp":1734979221516,"version":"3.32.0"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1991,3,1]],"date-time":"1991-03-01T00:00:00Z","timestamp":667785600000},"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":[[1991,3]]},"DOI":"10.1007\/bf01200059","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T13:41:22Z","timestamp":1109252482000},"page":"91-105","source":"Crossref","is-referenced-by-count":18,"title":["Towards optimal simulations of formulas by bounded-width programs"],"prefix":"10.1007","volume":"1","author":[{"given":"Richard","family":"Cleve","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, L. Babai, P. Hajnal, J. Koml\u00f3s, P. P\u00fadlak, V. R\u00f6dl, E. Szemer\u00e9di, and G. Tur\u00e1n, Two lower bounds for branching programs,Proc. 18th Ann. ACM Symp. Theory of Computing, 1986, 30?38.","DOI":"10.1145\/12130.12134"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"J. Bar-Ilan and D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction,Proc. 8th Ann. ACM Symp. Principles of Distributed Computing, 1989, 201?209.","DOI":"10.1145\/72981.72995"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. Barrington","year":"1989","unstructured":"D. A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages inNC 1,J. Computer System Sci.,38 (1989), 150?164.","journal-title":"J. Computer System Sci."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"M. Ben-Or and R. Cleve, Computing algebraic formulas using a constant number of registers,Proc. 20th Ann. ACM Symp. Theory of Computing, 1988, 254?257.","DOI":"10.1145\/62212.62236"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"A. Borodin, D. Dolev, F. Fich, and W. Paul, Bounds for width two branching programs,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 87?93.","DOI":"10.1145\/800061.808736"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"R. P. Brent, The parallel evaluation of general arithmetic expressions,J. ACM,21 (1974), 201?206.","journal-title":"J. ACM"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"J. Cai and R. J. Lipton, Subquadratic simulations of circuits by branching programs,Proc. 30th Ann. IEEE Symp. Foundations of Computer Sci., 1989, 568?573.","DOI":"10.1109\/SFCS.1989.63536"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"A. Chandra, M. Furst, and R. J. Lipton, Multiparty protocols,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 94?99.","DOI":"10.1145\/800061.808737"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"R. Cleve, Towards optimal simulations of formulas by bounded-width programs,Proc. 22nd Ann. ACM Symp. Theory of Computing, 1990, 271?277.","DOI":"10.1145\/100216.100251"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"J. Kilian, Founding cryptography on oblivious transfer,Proc. 20th Ann. ACM Symp. Theory of Computing, 1988, 20?31.","DOI":"10.1145\/62212.62215"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"P. P\u00fadlak, A lower bound on the complexity of branching programs,Proc. Conf. on Math. Foundations of Computer Sci., 1984, 480?489.","DOI":"10.1007\/BFb0030331"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, Completeness classes in algebra,Proc. 11th Ann. ACM Symp. Theory of Computing, 1979, 249?261.","DOI":"10.1145\/800135.804419"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Lower bounds by probabilistic arguments,Proc. 24th Ann. IEEE Symp. Foundations of Computer Sci., 1983, 420?428.","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200059.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200059\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T18:12:49Z","timestamp":1734977569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["BF01200059"],"URL":"https:\/\/doi.org\/10.1007\/bf01200059","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}