{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:24:57Z","timestamp":1725600297830},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229923"},{"type":"electronic","value":"9783642229930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_40","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:44:46Z","timestamp":1312893886000},"page":"436-447","source":"Crossref","is-referenced-by-count":0,"title":["Symmetric Functions Capture General Functions"],"prefix":"10.1007","author":[{"given":"Richard J.","family":"Lipton","sequence":"first","affiliation":[]},{"given":"Kenneth W.","family":"Regan","sequence":"additional","affiliation":[]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. J. Assn. Comp. Mach.\u00a045, 501\u2013555 (1998)","journal-title":"J. Assn. Comp. Mach."},{"key":"40_CR2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. Assn. Comp. Mach.\u00a045, 70\u2013122 (1998)","journal-title":"J. Assn. Comp. Mach."},{"issue":"3","key":"40_CR3","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica\u00a023(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"key":"40_CR4","unstructured":"Assumus Jr., E.F., Key, J.D.: Polynomial codes and Finite Geometries in Handbook of Coding Theory. In: Pless Jr., V.S., Huffman, W.C. (eds.), vol.\u00a0II, ch.16. Elsevier, Amsterdam (1998)"},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1982","unstructured":"Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comp. Sci.\u00a022, 317\u2013330 (1982)","journal-title":"Theor. Comp. Sci."},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0304-3975(92)90372-M","volume":"100","author":"P. Beame","year":"1992","unstructured":"Beame, P., Brisson, E., Ladner, R.: The complexity of computing symmetric functions using threshold circuits. Theor. Comp. Sci.\u00a0100, 253\u2013265 (1992)","journal-title":"Theor. Comp. Sci."},{"key":"40_CR7","unstructured":"Beigel, R., Tarui, J.: On ACC. In: Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, pp. 783\u2013792 (1991)"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 15th Annual ACM Symposium on the Theory of Computing, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Dixon, J.D., Panario, D.: The degree of the splitting field of a random polynomial over a finite field. The Electronic Journal of Combinatorics\u00a011(1) (2004), http:\/\/www.combinatorics.org\/Volume_11\/Abstracts\/v11i1r70.html","DOI":"10.37236\/1823"},{"key":"40_CR10","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. Math. Sys. Thy.\u00a017, 13\u201327 (1984)","journal-title":"Math. Sys. Thy."},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M.: An exponential lower bound for depth 3 arithmetic circuits. In: Proc. 30th Annual ACM Symposium on the Theory of Computing, pp. 577\u2013582 (1998)","DOI":"10.1145\/276698.276872"},{"key":"40_CR12","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s002009900021","volume":"10","author":"D. Grigoriev","year":"2000","unstructured":"Grigoriev, D., Razborov, A.: Exponential lower bounds for depth 3 algebraic circuits in algebras of functions over finite fields. Applicable Algebra in Engineering, Communication, and Computing\u00a010, 465\u2013487 (2000) (preliminary version FOCS 1998)","journal-title":"Applicable Algebra in Engineering, Communication, and Computing"},{"key":"40_CR13","first-page":"200","volume":"32","author":"V. Grolmusz","year":"2002","unstructured":"Grolmusz, V.: Computing elementary symmetric polynomials with a sub-polynomial number of multiplications. SIAM Journal on Computing\u00a032, 2002\u201302 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"40_CR14","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1002\/rsa.20262","volume":"35","author":"C.S. Jutla","year":"2009","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. Random Struct. Algorithms\u00a035(2), 163\u2013193 (2009)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"40_CR15","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1137\/S0097539704445615","volume":"36","author":"T. Kaufman","year":"2006","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. SIAM Journal on Computing\u00a036(3), 779\u2013802 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"40_CR16","doi-asserted-by":"publisher","first-page":"571","DOI":"10.2307\/2314898","volume":"74","author":"A. Klinger","year":"1967","unstructured":"Klinger, A.: The Vandermonde matrix. The American Mathematical Monthly\u00a074(5), 571\u2013574 (1967)","journal-title":"The American Mathematical Monthly"},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"Lu, C.J.: An exact characterization of symmetric functions in qAC0[2]. In: Proc. 4th International Combinatorics and Computing Conference, pp. 167\u2013173 (1998)","DOI":"10.1007\/3-540-68535-9_20"},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A. Razborov","year":"1987","unstructured":"Razborov, A.: Lower bounds for the size of circuits of bounded depth with basis {\u2009\u2227\u2009,\u2009\u2295\u2009}. Mathematical Notes (formerly of the Academy of Natural Sciences of the USSR)\u00a041, 333\u2013338 (1987)","journal-title":"Mathematical Notes, (formerly of the Academy of Natural Sciences of the USSR)"},{"key":"40_CR19","doi-asserted-by":"crossref","unstructured":"Razborov, A.: On the method of approximations. In: Proc. 21st Annual ACM Symposium on the Theory of Computing, pp. 167\u2013176 (1989)","DOI":"10.1145\/73007.73023"},{"key":"40_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814549","volume-title":"A computational introduction to number theory and algebra","author":"V. Shoup","year":"2008","unstructured":"Shoup, V.: A computational introduction to number theory and algebra. Cambridge University Press, New York (2008)"},{"key":"40_CR21","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proc. 19th Annual ACM Symposium on the Theory of Computing, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:10:17Z","timestamp":1606187417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}