{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:42:58Z","timestamp":1725745378037},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403125"},{"type":"electronic","value":"9783642403132"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_39","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T14:36:43Z","timestamp":1376663803000},"page":"433-444","source":"Crossref","is-referenced-by-count":1,"title":["On Fixed-Polynomial Size Circuit Lower Bounds for Uniform Polynomials in the Sense of Valiant"],"prefix":"10.1007","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Perifel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00e9mi","family":"de Verclos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1983","unstructured":"Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comput. Sci.\u00a022, 317\u2013330 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR2","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and reduction in algebraic complexity theory","author":"P. B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics, vol.\u00a07. Springer, Berlin (2000)"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R., Williams, R.: Fixed-polynomial size circuit bounds. In: IEEE Conference on Computational Complexity, pp. 19\u201326 (2009)","DOI":"10.1109\/CCC.2009.21"},{"key":"39_CR4","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04880-1","volume-title":"The complexity theory companion","author":"L.A. Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, L.A., Ogihara, M.: The complexity theory companion. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2002)"},{"issue":"1","key":"39_CR5","doi-asserted-by":"publisher","first-page":"119","DOI":"10.4086\/toc.2011.v007a008","volume":"7","author":"P. Hrubes","year":"2011","unstructured":"Hrubes, P., Yehudayoff, A.: Arithmetic complexity in ring extensions. Theory of Computing\u00a07(1), 119\u2013129 (2011)","journal-title":"Theory of Computing"},{"key":"39_CR6","unstructured":"Jansen, M.J., Santhanam, R.: Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes. In: STACS, pp. 519\u2013530 (2012)"},{"issue":"1-3","key":"39_CR7","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\u00a055(1-3), 40\u201356 (1982)","journal-title":"Information and Control"},{"issue":"4","key":"39_CR8","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1006\/jcom.1996.0019","volume":"12","author":"P. Koiran","year":"1996","unstructured":"Koiran, P.: Hilbert\u2019s Nullstellensatz is in the polynomial hierarchy. J. Complexity\u00a012(4), 273\u2013286 (1996)","journal-title":"J. Complexity"},{"key":"39_CR9","unstructured":"Koiran, P.: Hilbert\u2019s Nullstellensatz is in the polynomial hierarchy. Technical Report 96-27, DIMACS (July 1996)"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Lipton, R.J.: Polynomials with 0-1 coefficients that are hard to evaluate. In: FOCS, pp. 6\u201310 (1975)","DOI":"10.1109\/SFCS.1975.25"},{"key":"39_CR11","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. In: FOCS, pp. 2\u201310 (1990)"},{"issue":"1","key":"39_CR12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.4086\/toc.2010.v006a007","volume":"6","author":"R. Raz","year":"2010","unstructured":"Raz, R.: Elusive functions and lower bounds for arithmetic circuits. Theory of Computing\u00a06(1), 135\u2013177 (2010)","journal-title":"Theory of Computing"},{"issue":"3","key":"39_CR13","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1137\/070702680","volume":"39","author":"R. Santhanam","year":"2009","unstructured":"Santhanam, R.: Circuit lower bounds for merlin\u2013arthur classes. SIAM J. Comput.\u00a039(3), 1038\u20131061 (2009)","journal-title":"SIAM J. Comput."},{"key":"39_CR14","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0304-3975(78)90016-6","volume":"7","author":"C.-P. Schnorr","year":"1978","unstructured":"Schnorr, C.-P.: Improved lower bounds on the number of multiplications\/divisions which are necessary of evaluate polynomials. Theor. Comput. Sci.\u00a07, 251\u2013261 (1978)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"39_CR15","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0203010","volume":"3","author":"V. Strassen","year":"1974","unstructured":"Strassen, V.: Polynomials with rational coefficients which are hard to compute. SIAM J. Comput.\u00a03(2), 128\u2013149 (1974)","journal-title":"SIAM J. Comput."},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: STOC, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"issue":"1-2","key":"39_CR17","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/j.tcs.2005.07.032","volume":"347","author":"N.V. Vinodchandran","year":"2005","unstructured":"Vinodchandran, N.V.: A note on the circuit complexity of PP. Theor. Comput. Sci.\u00a0347(1-2), 415\u2013418 (2005)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T02:10:59Z","timestamp":1558318259000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}