{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:27:05Z","timestamp":1747196825702,"version":"3.40.5"},"publisher-location":"Cham","reference-count":8,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319133492"},{"type":"electronic","value":"9783319133508"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"unspecified","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":[[2014]]},"DOI":"10.1007\/978-3-319-13350-8_29","type":"book-chapter","created":{"date-parts":[[2014,12,9]],"date-time":"2014-12-09T07:46:18Z","timestamp":1418111178000},"page":"394-405","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Limit of Some Algorithmic Approach to Circuit Lower Bounds"],"prefix":"10.1007","author":[{"given":"Osamu","family":"Watanabe","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,12,10]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Oracles are subtle but not malicious. In: Proc. IEEE Conference on Computational Complexity (CCC 2006), pp. 340\u2013354. IEEE (2006)","DOI":"10.1109\/CCC.2006.32"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P=?NP question. SIAM J. Comput. 4, 431\u2013442 (1975)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"29_CR3","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"NH Bshouty","year":"1996","unstructured":"Bshouty, N.H., Cleve, R., Gavald\u00e0, R., Kannan, S.: Oracles and queries that are sufficient for exact learning. J. Comput. Sys. Sci. 52(3), 421\u2013433 (1996)","journal-title":"J. Comput. Sys. Sci."},{"key":"29_CR4","unstructured":"Cai, J.Y.: $${S}^{p}_2$$ $$\\subseteq $$ ZPPNP. In: Proc. of the 42nd Annual Sympos. on Foundations of Comp. Sci. pp. 620\u2013629. IEEE (2001)"},{"issue":"4","key":"29_CR5","doi-asserted-by":"publisher","first-page":"984","DOI":"10.1137\/S0097539703422716","volume":"33","author":"J Cai","year":"2004","unstructured":"Cai, J., Watanabe, O.: On proving circuit lower bounds against the polynomial-time hierarchy. SIAM Journal on Computing 33(4), 984\u20131009 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"29_CR6","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R Kannan","year":"1982","unstructured":"Kannan, R.: Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control 55(1), 40\u201356 (1982)","journal-title":"Information and Control"},{"key":"29_CR7","first-page":"191","volume":"28","author":"RM Karp","year":"1982","unstructured":"Karp, R.M., Lipton, R.J.: Turing machines that take advice. Enseign. Math. 28, 191\u2013201 (1982)","journal-title":"Enseign. Math."},{"issue":"1","key":"29_CR8","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1137\/S0097539795296206","volume":"28","author":"J K\u00f6bler","year":"1998","unstructured":"K\u00f6bler, J., Watanabe, O.: New collapse consequences of np having small circuits. SIAM Journal on Computing 28(1), 311\u2013324 (1998)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Computing with New Resources"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13350-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T00:00:57Z","timestamp":1747180857000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13350-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319133492","9783319133508"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13350-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"10 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}