乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:45:50Z","timestamp":1740105950795,"version":"3.37.3"},"reference-count":40,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"vor","delay-in-days":1461,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1016\/j.ic.2012.10.013","type":"journal-article","created":{"date-parts":[[2012,10,26]],"date-time":"2012-10-26T16:16:49Z","timestamp":1351268209000},"page":"195-207","source":"Crossref","is-referenced-by-count":3,"special_numbering":"C","title":["Permanent does not have succinct polynomial size arithmetic circuits of constant depth"],"prefix":"10.1016","volume":"222","author":[{"given":"Maurice","family":"Jansen","sequence":"first","affiliation":[]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2012.10.013_br0010","doi-asserted-by":"crossref","unstructured":"M. Agrawal, Proving lower bounds via pseudo-random generators, in: Proc. 25th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2005, pp. 92\u2013105.","DOI":"10.1007\/11590156_6"},{"key":"10.1016\/j.ic.2012.10.013_br0020","first-page":"781","article-title":"Primes is in P","volume":"2","author":"Agrawal","year":"2002","journal-title":"Ann. of Math."},{"key":"10.1016\/j.ic.2012.10.013_br0030","doi-asserted-by":"crossref","unstructured":"M. Agrawal, V. Vinay, Arithmetic circuits: A chasm at depth four, in: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"issue":"7","key":"10.1016\/j.ic.2012.10.013_br0040","doi-asserted-by":"crossref","DOI":"10.4086\/cjtcs.1999.007","article-title":"The permanent requires large uniform threshold circuits","volume":"1999","author":"Allender","year":"1999","journal-title":"Chic. J. Theoret. Comput. Sci."},{"issue":"2","key":"10.1016\/j.ic.2012.10.013_br0050","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0304-3975(92)90353-H","article-title":"Logarithmic advice classes","volume":"99","author":"Balc\u00e1zar","year":"1992","journal-title":"Theor. Comp. Sci."},{"key":"10.1016\/j.ic.2012.10.013_br0060","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","article-title":"On uniformity within NC1","volume":"41","author":"Mix Barrington","year":"1990","journal-title":"J. Comp. Sys. Sci."},{"key":"10.1016\/j.ic.2012.10.013_br0070","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","article-title":"The complexity of partial derivatives","volume":"22","author":"Baur","year":"1982","journal-title":"Theor. Comp. Sci."},{"year":"2000","series-title":"Completeness and Reduction in Algebraic Complexity Theory","author":"B\u00fcrgisser","key":"10.1016\/j.ic.2012.10.013_br0080"},{"key":"10.1016\/j.ic.2012.10.013_br0090","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00037-009-0260-x","article-title":"On defining integers and proving arithmetic circuit lower bounds","volume":"18","author":"B\u00fcrgisser","year":"2009","journal-title":"Comput. Complexity"},{"key":"10.1016\/j.ic.2012.10.013_br0100","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","article-title":"A probabilistic remark on algebraic program testing","volume":"7","author":"DeMillo","year":"1978","journal-title":"Inf. Proc. Lett."},{"key":"10.1016\/j.ic.2012.10.013_br0110","doi-asserted-by":"crossref","unstructured":"D. Grigoriev, M. Karpinski, An exponential lower bound for depth 3 arithmetic circuits, in: Proc. 13th Annual ACM Symposium on the Theory of Computing, 1998, pp. 577\u2013582.","DOI":"10.1145\/276698.276872"},{"key":"10.1016\/j.ic.2012.10.013_br0120","doi-asserted-by":"crossref","unstructured":"J. Heintz, C.P. Schnorr, Testing polynomials which are easy to compute (extended abstract), in: Proc. 12th Annual ACM Symposium on the Theory of Computing, 1980, pp. 262\u2013272.","DOI":"10.1145\/800141.804674"},{"issue":"4","key":"10.1016\/j.ic.2012.10.013_br0130","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","article-title":"Uniform constant-depth threshold circuits for division and iterated multiplication","volume":"64","author":"Hesse","year":"2002","journal-title":"J. Comp. Sys. Sci."},{"key":"10.1016\/j.ic.2012.10.013_br0140","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","article-title":"Probabilistic algorithms for deciding equivalence of straight-line programs","volume":"30","author":"Ibarra","year":"1983","journal-title":"J. Assn. Comp. Mach."},{"key":"10.1016\/j.ic.2012.10.013_br0150","doi-asserted-by":"crossref","unstructured":"M. Jansen, R. Santhanam, Permanent does not have succinct polynomial size arithmetic circuits of constant depth, in: Proc. 38th Annual International Conference on Automata, Languages, and Programming, 2011, pp. 724\u2013735.","DOI":"10.1007\/978-3-642-22006-7_61"},{"key":"10.1016\/j.ic.2012.10.013_br0160","doi-asserted-by":"crossref","unstructured":"M. Jansen, R. Santhanam, Marginal hitting sets imply super-polynomial lower bounds for permanent, in: The 3rd Innovations in Theoretical Computer Science Conference (ITCS 2012), 2012, in press.","DOI":"10.1145\/2090236.2090275"},{"issue":"1\u20132","key":"10.1016\/j.ic.2012.10.013_br0170","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","article-title":"Derandomizing polynomial identity testing means proving circuit lower bounds","volume":"13","author":"Kabanets","year":"2004","journal-title":"Comput. Complexity"},{"key":"10.1016\/j.ic.2012.10.013_br0180","unstructured":"P. Koiran, Shallow circuits with high powered inputs, in: Proc. 2nd Symp. on Innovations in Computer Science, 2011."},{"key":"10.1016\/j.ic.2012.10.013_br0190","doi-asserted-by":"crossref","unstructured":"P. Koiran, S. Perifel, A superpolynomial lower bound on the size of uniform non-constant-depth threshold circuits for the permanent, in: Proc. 24th Annual IEEE Conference on Computational Complexity, 2009.","DOI":"10.1109\/CCC.2009.19"},{"issue":"1","key":"10.1016\/j.ic.2012.10.013_br0200","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-011-0002-8","article-title":"Interpolation in Valiant\u02bcs theory","volume":"20","author":"Koiran","year":"2011","journal-title":"Comput. Complexity"},{"key":"10.1016\/j.ic.2012.10.013_br0210","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","article-title":"BPP and the polynomial hierarchy","volume":"17","author":"Lautemann","year":"1983","journal-title":"Inf. Proc. Lett."},{"key":"10.1016\/j.ic.2012.10.013_br0220","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","article-title":"Algebraic methods for interactive proof systems","volume":"39","author":"Lund","year":"1992","journal-title":"J. Assn. Comp. Mach."},{"key":"10.1016\/j.ic.2012.10.013_br0230","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","article-title":"Relations among complexity measures","volume":"26","author":"Pippenger","year":"1979","journal-title":"J. Assn. Comp. Mach."},{"key":"10.1016\/j.ic.2012.10.013_br0240","doi-asserted-by":"crossref","DOI":"10.4086\/toc.2010.v006a007","article-title":"Elusive functions and lower bounds for arithmetic circuits","volume":"6","author":"Raz","year":"2010","journal-title":"Theory Comput."},{"issue":"2","key":"10.1016\/j.ic.2012.10.013_br0250","doi-asserted-by":"crossref","DOI":"10.1007\/s00037-009-0270-8","article-title":"Lower bounds and separations for constant depth multilinear circuits","volume":"18","author":"Raz","year":"2009","journal-title":"Comput. Complexity"},{"key":"10.1016\/j.ic.2012.10.013_br0260","first-page":"333","article-title":"Lower bounds for the size of circuits of bounded depth with basis {\u2227,\u2295}","volume":"41","author":"Razborov","year":"1987","journal-title":"Math. Notes Acad. Natural Sci. USSR"},{"key":"10.1016\/j.ic.2012.10.013_br0270","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for polynomial identities","volume":"27","author":"Schwartz","year":"1980","journal-title":"J. Assn. Comp. Mach."},{"issue":"1","key":"10.1016\/j.ic.2012.10.013_br0280","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00001609","article-title":"Depth-3 arithmetic formulae over fields of characteristic zero","volume":"10","author":"Shpilka","year":"2001","journal-title":"Comput. Complexity"},{"key":"10.1016\/j.ic.2012.10.013_br0290","doi-asserted-by":"crossref","unstructured":"M. Sipser, A complexity-theoretic approach to randomness, in: Proc. 15th Annual ACM Symposium on the Theory of Computing, 1983, pp. 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"10.1016\/j.ic.2012.10.013_br0300","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proc. 19th Annual ACM Symposium on the Theory of Computing, 1987, pp. 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"10.1016\/j.ic.2012.10.013_br0310","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","article-title":"PP is as hard as the polynomial-time hierarchy","volume":"20","author":"Toda","year":"1991","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.ic.2012.10.013_br0320","first-page":"753","article-title":"Complexity classes defined by counting quantifiers","volume":"38","author":"Tor\u00e1n","year":"1991","journal-title":"J. Assn. Comp. Mach."},{"issue":"4","key":"10.1016\/j.ic.2012.10.013_br0330","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","article-title":"Pseudorandomness and average-case complexity via uniform reductions","volume":"16","author":"Trevisan","year":"2007","journal-title":"Comput. Complexity"},{"key":"10.1016\/j.ic.2012.10.013_br0340","doi-asserted-by":"crossref","unstructured":"L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, 1979, pp. 249\u2013261.","DOI":"10.1145\/800135.804419"},{"key":"10.1016\/j.ic.2012.10.013_br0350","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","volume":"8","author":"Valiant","year":"1979","journal-title":"Theor. Comp. Sci."},{"year":"1999","series-title":"Introduction to Circuit Complexity, A Uniform Approach","author":"Vollmer","key":"10.1016\/j.ic.2012.10.013_br0360"},{"key":"10.1016\/j.ic.2012.10.013_br0370","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","article-title":"The complexity of combinatorial problems with succinct input representation","volume":"23","author":"Wagner","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/j.ic.2012.10.013_br0380","doi-asserted-by":"crossref","unstructured":"R. Williams, Non-uniform ACC circuit lower bounds, in: Proceedings of 26th IEEE Conference on Computational Complexity, 2011, http:\/\/dx.doi.org\/10.1109\/CCC.2011.36.","DOI":"10.1109\/CCC.2011.36"},{"key":"10.1016\/j.ic.2012.10.013_br0390","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1142\/S0129054191000066","article-title":"#P-completeness via many-one reductions","volume":"2","author":"Zank\u00f3","year":"1991","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"10.1016\/j.ic.2012.10.013_br0400","series-title":"Proceedings of the International Symposium on Symbolic and Algebraic Manipulation (EUROSAM \u02bc79)","first-page":"216","article-title":"Probabilistic algorithms for sparse polynomials","volume":"vol. 72","author":"Zippel","year":"1979"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S089054011200154X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S089054011200154X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2018,11,19]],"date-time":"2018-11-19T16:00:23Z","timestamp":1542643223000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S089054011200154X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":40,"alternative-id":["S089054011200154X"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2012.10.013","relation":{},"ISSN":["0890-5401"],"issn-type":[{"type":"print","value":"0890-5401"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}