{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:13:17Z","timestamp":1784110397841,"version":"3.55.0"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319341705","type":"print"},{"value":"9783319341712","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-34171-2_22","type":"book-chapter","created":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T06:34:18Z","timestamp":1464590058000},"page":"309-323","source":"Crossref","is-referenced-by-count":4,"title":["Depth-4 Identity Testing and Noether\u2019s Normalization Lemma"],"prefix":"10.1007","author":[{"given":"Partha","family":"Mukhopadhyay","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,5,31]]},"reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/11590156_6","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"M Agrawal","year":"2005","unstructured":"Agrawal, M.: Proving lower bounds via pseudo-random generators. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 92\u2013105. Springer, Heidelberg (2005)"},{"issue":"2","key":"22_CR2","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. Math. 160(2), 781\u2013793 (2004)","journal-title":"Ann. Math."},{"issue":"3","key":"22_CR3","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 the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1017\/S0963548398003411","volume":"8","author":"N Alon","year":"1999","unstructured":"Alon, N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8, 7\u201330 (1999)","journal-title":"Comb. Probab. Comput."},{"issue":"4","key":"22_CR5","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/j.ic.2009.06.003","volume":"208","author":"V Arvind","year":"2010","unstructured":"Arvind, V., Mukhopadhyay, P.: The ideal membership problem and polynomial identity testing. Inf. Comput. 208(4), 351\u2013363 (2010)","journal-title":"Inf. Comput."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Saha, C., Saptharishi, R., Saxena, N.: Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, pp. 599\u2013614 (2012)","DOI":"10.1145\/2213977.2214033"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Vinay, V.: Arithmetic circuits: a chasm at depth four. In: Proceedings-Annual Symposium on Foundations of Computer Science, pp. 67\u201375. IEEE (2008)","DOI":"10.1109\/FOCS.2008.32"},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.ic.2012.10.004","volume":"222","author":"M Beecken","year":"2013","unstructured":"Beecken, M., Mittmann, J., Saxena, N.: Algebraic independence and blackbox identity testing. Inf. Comput. 222, 2\u201319 (2013)","journal-title":"Inf. Comput."},{"key":"22_CR9","volume-title":"Using Algebraic Geometry","author":"DA Cox","year":"2005","unstructured":"Cox, D.A., Little, J., O\u2019Shea, D.: Using Algebraic Geometry. Springer, New York (2005)"},{"key":"22_CR10","series-title":"3\/e (Undergraduate Texts in Mathematics)","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-35651-8","volume-title":"Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra","author":"DA Cox","year":"2007","unstructured":"Cox, D.A., Little, J., O\u2019Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. 3\/e (Undergraduate Texts in Mathematics). Springer, New York (2007)"},{"issue":"5","key":"22_CR11","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z Dvir","year":"2007","unstructured":"Dvir, Z., Shpilka, A.: Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput. 36(5), 1404\u20131434 (2007)","journal-title":"SIAM J. Comput."},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/978-3-642-40328-6_37","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"MA Forbes","year":"2013","unstructured":"Forbes, M.A., Shpilka, A.: Explicit Noether normalization for simultaneous conjugation via polynomial identity testing. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 527\u2013542. Springer, Heidelberg (2013)"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Forbes, M.A., Shpilka, A.: Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pp. 243\u2013252 (2013)","DOI":"10.1109\/FOCS.2013.34"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Approaching the chasm at depth four. In: IEEE Conference on Computational Complexity, pp. 65\u201373 (2013)","DOI":"10.1109\/CCC.2013.16"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Arithmetic circuits: a chasm at depth three. In: FOCS, pp. 578\u2013587 (2013)","DOI":"10.1109\/FOCS.2013.68"},{"key":"22_CR16","unstructured":"Gupta, A.: Algebraic geometric techniques for depth-4 PIT & Sylvester-Gallai conjectures for varieties. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 21, p. 130 (2014)"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Heintz, J., Schnorr, C.-P.: Testing polynomials which are easy to compute (extended abstract). In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 262\u2013272 (1980)","DOI":"10.1145\/800141.804674"},{"issue":"1\u20132","key":"22_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13(1\u20132), 1\u201346 (2004)","journal-title":"Comput. Complex."},{"issue":"6","key":"22_CR19","doi-asserted-by":"crossref","first-page":"2114","DOI":"10.1137\/110824516","volume":"42","author":"ZS Karnin","year":"2013","unstructured":"Karnin, Z.S., Mukhopadhyay, P., Shpilka, A., Volkovich, I.: Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM J. Comput. 42(6), 2114\u20132131 (2013)","journal-title":"SIAM J. Comput."},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Klivans, A., Spielman, D.A.: Randomness efficient identity testing of multivariate polynomials. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 6\u20138 July 2001, pp. 216\u2013223 (2001)","DOI":"10.1145\/380752.380801"},{"issue":"2","key":"22_CR21","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00037-007-0226-9","volume":"16","author":"N Kayal","year":"2007","unstructured":"Kayal, N., Saxena, N.: Polynomial identity testing for depth 3 circuits. Comput. Complex. 16(2), 115\u2013138 (2007)","journal-title":"Comput. Complex."},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Kayal, N., Saraf, S.: Blackbox polynomial identity testing for depth 3 circuits. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 198\u2013207 (2009)","DOI":"10.1109\/FOCS.2009.67"},{"issue":"3","key":"22_CR23","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s00493-011-2537-3","volume":"31","author":"ZS Karnin","year":"2011","unstructured":"Karnin, Z.S., Shpilka, A.: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica 31(3), 333\u2013364 (2011)","journal-title":"Combinatorica"},{"key":"22_CR24","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: FCT, pp. 565\u2013574 (1979)"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Mulmuley, K.: Geometric complexity theory V: equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether\u2019s Normalization Lemma. In: CoRR (also, in FOCS 2012) (2012). abs\/1209.5993","DOI":"10.1109\/FOCS.2012.15"},{"key":"22_CR26","volume-title":"Algebraic Geometry I : Complex Projective Varieties","author":"D Mumford","year":"1976","unstructured":"Mumford, D.: Algebraic Geometry I : Complex Projective Varieties. Springer, Heidelberg (1976). Grundlehren der mathematischen Wissenschaften"},{"issue":"1","key":"22_CR27","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"4","key":"22_CR28","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"22_CR29","unstructured":"Shamir, A.: IP=PSPACE. In: 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, 22\u201324 October 1990, vol. 1, pp. 11\u201315 (1990)"},{"issue":"5","key":"22_CR30","doi-asserted-by":"crossref","first-page":"1285","DOI":"10.1137\/10848232","volume":"41","author":"N Saxena","year":"2012","unstructured":"Saxena, N., Seshadhri, C.: Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn\u2019t matter. SIAM J. Comput. 41(5), 1285\u20131298 (2012)","journal-title":"SIAM J. Comput."},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"Saraf, S., Volkovich, I.: Black-box identity testing of depth-4 multilinear circuits. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pp. 421\u2013430 (2011)","DOI":"10.1145\/1993636.1993693"},{"issue":"3\u20134","key":"22_CR32","first-page":"207","volume":"5","author":"A Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theoret. Comput. Sci. 5(3\u20134), 207\u2013388 (2010)","journal-title":"Found. Trends Theoret. Comput. Sci."},{"key":"22_CR33","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Symbolic and Algebraic Computation, EUROSAM 1979, An International Symposiumon Symbolic and Algebraic Computation, pp. 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-34171-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T01:14:08Z","timestamp":1567991648000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-34171-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319341705","9783319341712"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-34171-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}