{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:48:16Z","timestamp":1742917696798,"version":"3.40.3"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"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-15579-1_36","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"461-472","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP"],"prefix":"10.1007","author":[{"given":"Kazuyuki","family":"Amano","sequence":"first","affiliation":[]},{"given":"Atsushi","family":"Saito","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"36_CR1","unstructured":"Amano, K., Saito, A.: A satisfiability algorithm for some class of dense depth two threshold circuits, IEICE Trans. Inf. Sys., to appear"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R Beigel","year":"1994","unstructured":"Beigel, R., Tarui, J.: On ACC. Computational Complexity 4, 350\u2013366 (1994)","journal-title":"Computational Complexity"},{"issue":"3","key":"36_CR3","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0211037","volume":"11","author":"D Coppersmith","year":"1982","unstructured":"Coppersmith, D.: Rapid multiplication of rectangular matrices. SIAM J. Comput. 11(3), 467\u2013471 (1982)","journal-title":"SIAM J. Comput."},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial time hierarchy. Mathematical Systems Theory 17, 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Hajnal, A., Maass, W., Pudlak, P., Szegedy, M., Turan, G.: Threshold circuits of bounded depth. In: FOCS 1987, pp. 99\u2013110 (1987)","DOI":"10.1109\/SFCS.1987.59"},{"key":"36_CR6","first-page":"143","volume":"5","author":"J H\u00e5stad","year":"1989","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. Advances in Computing Research 5, 143\u2013170 (1989)","journal-title":"Advances in Computing Research"},{"issue":"4","key":"36_CR7","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: exponential time versus probabilistic polynomial time. J. Comput. and Sys. Sci. 65(4), 672\u2013694 (2002)","journal-title":"J. Comput. and Sys. Sci."},{"issue":"3","key":"36_CR8","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1137\/S0097539792282965","volume":"26","author":"R Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Paturi, R., Saks, M.E.: Size-depth tradeoffs for threshold circuits. SIAM J. Comput. 26(3), 693\u2013707 (1997)","journal-title":"SIAM J. Comput."},{"key":"36_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-45687-2_29","volume-title":"Mathematical Foundations of Computer Science 2002","author":"K Iwama","year":"2002","unstructured":"Iwama, K., Morizumi, H.: An explicit lower bound of 5$$n$$-$$o$$($$n$$) for boolean circuits. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 353\u2013364. Springer, Heidelberg (2002)"},{"issue":"4","key":"36_CR10","first-page":"598","volume":"41","author":"A Razborov","year":"1987","unstructured":"Razborov, A.: Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Mathematical Notes of Academy of Sciences USSR 41(4), 598\u2013607 (1987)","journal-title":"Mathematical Notes of Academy of Sciences USSR"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: STOC 1987, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: STOC 2010, pp. 231\u2013240 (2010)","DOI":"10.1145\/1806689.1806723"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates. In: STOC 2014, pp. 194\u2013102 (2014)","DOI":"10.1145\/2591796.2591858"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. Journal of the ACM 61(1), Article 22 (January 2014)","DOI":"10.1145\/2559903"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T22:37:51Z","timestamp":1676932671000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_36","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 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}