{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T03:20:00Z","timestamp":1778124000132,"version":"3.51.4"},"reference-count":30,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2002,12,1]],"date-time":"2002-12-01T00:00:00Z","timestamp":1038700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3881,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2002,12]]},"DOI":"10.1016\/s0022-0000(02)00021-1","type":"journal-article","created":{"date-parts":[[2002,12,27]],"date-time":"2002-12-27T18:04:53Z","timestamp":1041012293000},"page":"639-659","source":"Crossref","is-referenced-by-count":16,"title":["Affine projections of symmetric polynomials"],"prefix":"10.1016","volume":"65","author":[{"given":"Amir","family":"Shpilka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(02)00021-1_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"\u03a311-formulae on finite structures","volume":"24","author":"Ajtai","year":"1982","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1","key":"10.1016\/S0022-0000(02)00021-1_BIB2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","article-title":"The monotone circuit complexity of boolean functions","volume":"7","author":"Alon","year":"1987","journal-title":"Combinatorica"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB3","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":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB4","unstructured":"M. Ben-Or, private communication."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB5","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1006\/eujc.1993.1022","article-title":"Apolarity and canonical forms for homogeneous polynomials","volume":"14","author":"Ehrenborg","year":"1993","journal-title":"European J. Combin."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB6","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity, circuits and the polynomial-time hierarchy","volume":"17","author":"Furst","year":"1984","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB7","doi-asserted-by":"crossref","unstructured":"D. Grigoriev, M. Karpinski, An exponential lower bound for depth 3 arithmetic circuits, in: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, Dallas, TX, USA, May 23\u201326, 1998, pp. 577\u2013582.","DOI":"10.1145\/276698.276872"},{"issue":"6","key":"10.1016\/S0022-0000(02)00021-1_BIB8","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/s002009900021","article-title":"Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields","volume":"10","author":"Grigoriev","year":"2000","journal-title":"Appl. Algebra Engng. Comm. Comput."},{"issue":"2","key":"10.1016\/S0022-0000(02)00021-1_BIB9","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","article-title":"Threshold circuits of bounded depth","volume":"46","author":"Hajnal","year":"1993","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB10","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Almost optimal lower bounds for small depth circuits, in: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, May 28\u201330, 1986, pp. 28\u201330.","DOI":"10.1145\/12130.12132"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB11","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1137\/S0097539792282965","article-title":"Size-depth trade-offs for threshold circuits","volume":"26","author":"Impagliazzo","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB12","doi-asserted-by":"crossref","unstructured":"N. Nisan, Lower bounds for non-commutative computation, in: Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing, New Orleans, LS, May 1991, ACM Press, New York, pp. 410\u2013418.","DOI":"10.1145\/103418.103462"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB13","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01294256","article-title":"Lower bound on arithmetic circuits via partial derivatives","volume":"6","author":"Nisan","year":"1996","journal-title":"Comput. Complexity"},{"issue":"2","key":"10.1016\/S0022-0000(02)00021-1_BIB14","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01215351","article-title":"Communication in bounded depth circuits","volume":"14","author":"Pudlak","year":"1994","journal-title":"Combinatorica"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB15","doi-asserted-by":"crossref","unstructured":"J. Radhakrishnan, P. Sen, S. Vishwanathan, Depth-3 arithmetic circuits for Sn2(x) and extensions of the Graham\u2013Pollack theorem, 20th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), New Delhi, India, December 13\u201315, 2000, pp. 176\u2013187.","DOI":"10.1007\/3-540-44450-5_14"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB16","doi-asserted-by":"crossref","unstructured":"R. Raz, A. Shpilka, Lower bounds for matrix product, in bounded depth circuits with arbitrary gates, in: 33rd Annual ACM Symposium on Theory of Computing, Crete, Greece, July 6\u20138, 2001, pp. 409\u2013418.","DOI":"10.1145\/380752.380833"},{"issue":"4","key":"10.1016\/S0022-0000(02)00021-1_BIB17","first-page":"798","article-title":"Lower bounds on the monotone complexity of some boolean functions","volume":"281","author":"Razborov","year":"1985","journal-title":"Dokl. Akad. Nauk. SSSR"},{"issue":"4","key":"10.1016\/S0022-0000(02)00021-1_BIB18","first-page":"333","volume":"41","author":"Razborov","year":"1987","journal-title":"Lower bounds for the size of circuits with bounded depth with basis {\u2227,\u2295}, Mathematical Notes of the Academy of Sciences of the USSR"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB19","series-title":"Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions","author":"Sagan","year":"1991"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB20","unstructured":"M. Saks, private communication."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB21","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(76)90083-9","article-title":"A lower bound on the number of additions in monotone computations","volume":"2","author":"Schnorr","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB22","unstructured":"E. Shamir, M. Snir, Lower bounds on the number of multiplications and the number of additions in monotone computations, Technical Report RC-6757, IBM, 1977."},{"issue":"1","key":"10.1016\/S0022-0000(02)00021-1_BIB23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00001609","article-title":"Depth-3 arithmetic circuits over fields of characteristic zero","volume":"10","author":"Shpilka","year":"2001","journal-title":"Comput. Complexity"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB24","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proceedings of the 19th Annual ACM Symposium of Theory of Computing, New York, 25\u201327 May, 1987, pp. 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB25","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF01436566","article-title":"Die berechnungskomplexi\u00e4t von elementarsymmetrischen funktionen und von interpolationskoeffizienten","volume":"20","author":"Strassen","year":"1973","journal-title":"Numer. Math."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB26","doi-asserted-by":"crossref","unstructured":"L.G. Valiant, Completeness classes in algebra, in: Conference Record of the 11th Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, 30 April\u20132 May, 1979, pp. 249\u2013261.","DOI":"10.1145\/800135.804419"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB27","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":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB28","first-page":"365","article-title":"Reducibility by algebraic projections","volume":"30","author":"Valiant","year":"1982","journal-title":"Logic and Algorithms. L\u2019 \u00c8nsignment Math."},{"key":"10.1016\/S0022-0000(02)00021-1_BIB29","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Separating the polynomial-time hierarchy by oracles, in: 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, 21\u201323 October, 1985, pp. 1\u201310.","DOI":"10.1109\/SFCS.1985.49"},{"key":"10.1016\/S0022-0000(02)00021-1_BIB30","doi-asserted-by":"crossref","unstructured":"A.C. Yao, On ACC and threshold circuits, in: 31st Annual Symposium on Foundations of Computer Science, Vol. II, St. Louis, Missouri, 22\u201324 October, 1990, pp. 619\u2013627.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000211?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000211?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T23:20:38Z","timestamp":1583968838000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000002000211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["S0022000002000211"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(02)00021-1","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}