{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:10:37Z","timestamp":1725455437078},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167839"},{"type":"electronic","value":"9783540399094"}],"license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/bfb0016269","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T00:39:17Z","timestamp":1131842357000},"page":"440-448","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Lower bounds on the complexity of local circuits"],"prefix":"10.1007","author":[{"given":"S. P.","family":"Jukna","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"40_CR1","unstructured":"N.Alon and R.B.Boppana: The monotone circuit complexity of Boolean functions, manuscript (1985)\u2014 to appear in Combinatorica."},{"key":"40_CR2","first-page":"1033","volume":"282","author":"A.E. Andreev","year":"1985","unstructured":"A.E. Andreev: On one method of obtaining lower bounds of individual monotone function complexity, Dokl. Akad. Nauk SSSR, 282 (1985), pp. 1033\u20131037.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"40_CR3","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/BFb0028795","volume":"199","author":"P.E. Dunne","year":"1985","unstructured":"P.E. Dunne: Lower bounds on the complexity of 1-time-only branching programs, Lecture Notes in Comput. Sci.,199(1985), pp.90\u201399.","journal-title":"Lecture Notes in Comput. Sci."},{"key":"40_CR4","unstructured":"M.Furst, J.B.Saxe and M.Sipser: Parity, circuits and polynomial-time hierarchy, 22ND Symp. on the Foundations of Computer Science, (1981), pp. 260\u2013270."},{"key":"40_CR5","first-page":"75","volume":"2","author":"S.V. Jablonskij","year":"1959","unstructured":"S.V. Jablonskij: On algorithmic obstacles in synthesis of minimal contact schemes, Problemy Kibernetiki, 2 (1959), pp.75\u2013121.","journal-title":"Problemy Kibernetiki"},{"key":"40_CR6","first-page":"301","volume":"224","author":"J.I. Janov","year":"1975","unstructured":"J.I. Janov: On some semantic characteristics of Turing machines, Dokl. Akad. Nauk SSSR, 224 (1975), pp.301\u2013304.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"40_CR7","first-page":"251","volume":"44","author":"S.P. Jukna","year":"1984","unstructured":"S.P. Jukna: Convolutional characterization of computability and complexity of computations, Colloquia Mathematica Societatis J\u00e1nos Bolyai, 44 (1984), pp. 251\u2013270.","journal-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai"},{"key":"40_CR8","first-page":"56","volume":"5","author":"S.E. Kuznetsov","year":"1981","unstructured":"S.E. Kuznetsov: Combinatorial circuits with no null chains over basis {&, V, \u2212}, Izvestija VUZ, Matematika, 5 (1981), pp. 56\u201363.","journal-title":"Matematika"},{"key":"40_CR9","first-page":"765","volume":"169","author":"E.I. Nechiporuk","year":"1966","unstructured":"E.I. Nechiporuk: A Boolean function, Doklady Akad. Nauk SSSR, 169 (1966), pp. 765\u2013766.","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"40_CR10","unstructured":"P.Pudl\u00e1k and S.\u017d\u00e1k: Space complexity of computations, Preprint Univ. Prague (1983), 30p."},{"key":"40_CR11","unstructured":"A.K.Pulatov: Lower bounds on the complexity of implementation of characteristic functions of group codes by \u03a0-networks, Combinatorial-Algebraic Methods in Applied Mathematics, Gorki (1979), pp. 81\u201395."},{"key":"40_CR12","first-page":"798","volume":"281","author":"A.A. Razborov","year":"1985","unstructured":"A.A. Razborov: Lower bounds on the monotone complexity of some Boolean functions, Doklady Akad. Nauk SSSR, 281 (1985), pp. 798\u2013801.","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"40_CR13","unstructured":"G.A.Tkachev: On the complexity of a sequence of Boolean functions by implementing in terms of circuits and \u03a0-circuits under additional restrictions on the circuits structure, Combinatorial-Algebraic Methods in Applied Mathematics, Gorki (1980), pp. 261\u2013207."},{"key":"40_CR14","unstructured":"I.Wegener: On the complexity of branching programs and decision trees for clique functions, Univ. Frankfurt, Interner Bericht, 5 (1984), 32p."},{"key":"40_CR15","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/BFb0030340","volume":"176","author":"S. \u017dak","year":"1984","unstructured":"S. \u017dak: An exponential lower bounds for one-time-only branching programs, Lecture Notes in Computer Science, 176 (1984), pp. 562\u2013566.","journal-title":"Lecture Notes in Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:34:31Z","timestamp":1578526471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016269"}},"subtitle":["Preliminary report"],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167839","9783540399094"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0016269","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]},"assertion":[{"value":"10 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}