{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T21:10:02Z","timestamp":1748466602538,"version":"3.41.0"},"publisher-location":"Cham","reference-count":9,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_23","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"289-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds for the Size of Nondeterministic Circuits"],"prefix":"10.1007","author":[{"given":"Hiroki","family":"Morizumi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(83)90029-4","volume":"28","author":"N Blum","year":"1984","unstructured":"Blum, N.: A boolean function requiring 3n network size. Theor. Comput. Sci. 28, 337\u2013345 (1984)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-642-22993-0_25","volume-title":"Mathematical Foundations of Computer Science 2011","author":"E Demenkov","year":"2011","unstructured":"Demenkov, E., Kulikov, A.S.: An elementary proof of a 3n $$-$$ o(n) lower bound on the circuit complexity of affine dispersers. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 256\u2013265. Springer, Heidelberg (2011)"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Iwama, K., Morizumi, H.: An explicit lower bound of 5n - o(n) for boolean circuits. In: Proc. of MFCS, pp. 353\u2013364 (2002)","DOI":"10.1007\/3-540-45687-2_29"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Lower bounds for computation with limited nondeterminism. In: Proc. of CCC, pp. 141\u2013152 (1998)","DOI":"10.1109\/CCC.1998.694600"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Lachish, O., Raz, R.: Explicit lower bound of 4.5n - o(n) for boolean circuits. In: Proc. of STOC, pp. 399\u2013408 (2001)","DOI":"10.1145\/380752.380832"},{"issue":"2","key":"23_CR7","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02246615","volume":"13","author":"C Schnorr","year":"1974","unstructured":"Schnorr, C.: Zwei lineare untere schranken f\u00fcr die komplexit\u00e4t boolescher funktionen. Computing 13(2), 155\u2013171 (1974)","journal-title":"Computing"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Slisenko, A.O. (ed.) Studies in Constructive Mathematics and Mathematical Logic, pp. 115\u2013125 (1968)","DOI":"10.1007\/978-1-4899-5327-8_25"},{"issue":"3","key":"23_CR9","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/S0022-0000(76)80041-4","volume":"13","author":"LG Valiant","year":"1976","unstructured":"Valiant, L.G.: Graph-theoretic properties in computational complexity. J. Comput. Syst. Sci. 13(3), 278\u2013285 (1976)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T20:34:03Z","timestamp":1748464443000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}