{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:53Z","timestamp":1725663653065},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_56","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:16:25Z","timestamp":1330254985000},"page":"566-575","source":"Crossref","is-referenced-by-count":1,"title":["A non-probabilistic switching lemma for the Sipser function"],"prefix":"10.1007","author":[{"given":"Sorin","family":"Istrail","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dejan","family":"Zivkovic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender, \u201cA note on the power of threshold circuits\u201d, Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pp. 580\u2013584, 1989.","DOI":"10.1109\/SFCS.1989.63538"},{"key":"56_CR2","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, \u201cBounded-width polynomial-size branching programs recognize exactly those languages in NC1\u201d, Journal of Computer and System Sciences, Vol. 38, pp. 150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"56_CR3","unstructured":"R. Beigel and J. Tarui, \u201cOn ACC\u201d, Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pp. 783\u2013792, 1991."},{"key":"56_CR4","first-page":"757","volume-title":"Handbook of Theoretical Computer Science, Vol. A","author":"R. B. Boppana","year":"1990","unstructured":"R. B. Boppana and M. Sipser, \u201cThe Complexity of Finite Functions\u201d, Handbook of Theoretical Computer Science, Vol. A (J. van Leeuwen, ed., North-Holland, Amsterdam), pp. 757\u2013804, 1990."},{"key":"56_CR5","doi-asserted-by":"crossref","unstructured":"J. Hastad, \u201cAlmost optimal lower bounds for small-depth circuits\u201d, Proceedings of the 18th ACM Symposium on Theory of Computing, pp. 6\u201320, 1986.","DOI":"10.1145\/12130.12132"},{"key":"56_CR6","doi-asserted-by":"crossref","unstructured":"S. Istrail and D. Zivkovic, \u201cA non-probabilistic switching lemma for the Sipser function\u201d, Wesleyan University, CS\/TR-92-1, 1992.","DOI":"10.1007\/3-540-56503-5_56"},{"key":"56_CR7","doi-asserted-by":"crossref","unstructured":"M. Karchmer and A. Wigderson, \u201cMonotone circuits for connectivity require super-logarithmic depth\u201d, Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 539\u2013550, 1988.","DOI":"10.1145\/62212.62265"},{"key":"56_CR8","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0304-3975(89)90150-3","volume":"66","author":"D. Mundici","year":"1989","unstructured":"D. Mundici, \u201cFunctions computed by monotone Boolean formulas with no repeated variables\u201d, Theoretical Computer Science, Vol. 66, pp. 113\u2013114, 1989.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"56_CR9","first-page":"798","volume":"281","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov, \u201cLower bounds on the monotone complexity of some Boolean functions\u201d, Doklady Akademii Nauk SSSR, Vol. 281(4), pp. 798\u2013801, 1985 (in Russian). English translation in Soviet Mathematics Doklady, Vol. 31, pp. 354\u2013357, 1985.","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"4","key":"56_CR10","first-page":"598","volume":"41","author":"A. A. Razborov","year":"1987","unstructured":"A. A. Razborov, \u201cLower bounds on the size of bounded depth networks over a complete basis with logical addition\u201d, Matematicheskie Zametki, Vol. 41(4), pp. 598\u2013607, 1987 (in Russian). English translation in Mathematical Notes of the Academy of Sciences of the USSR, Vol. 41(4), pp. 333\u2013338, 1987.","journal-title":"Matematicheskie Zametki"},{"key":"56_CR11","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/3149.3158","volume":"22","author":"S. Skyum","year":"1985","unstructured":"S. Skyum and L. G. Valiant, \u201cA complexity theory based on Boolean algebra\u201d, Journal of the ACM, Vol. 22, pp. 484\u2013504, 1985.","journal-title":"Journal of the ACM"},{"key":"56_CR12","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, \u201cExponential lower bounds for restricted monotone circuits\u201d, Proceedings of the 15th ACM Symposium on Theory of Computing, pp. 110\u2013117, 1983.","DOI":"10.1145\/800061.808739"},{"key":"56_CR13","doi-asserted-by":"crossref","unstructured":"I. Wegener, The Complexity of Boolean Functions, Wiley-Teubner, 1987.","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T04:49:48Z","timestamp":1640926188000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}