{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:37:18Z","timestamp":1776803838362,"version":"3.51.2"},"reference-count":15,"publisher":"American Mathematical Society (AMS)","issue":"312","license":[{"start":{"date-parts":[[2018,12,4]],"date-time":"2018-12-04T00:00:00Z","timestamp":1543881600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1405348"],"award-info":[{"award-number":["DMS 1405348"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1312071"],"award-info":[{"award-number":["DMS-1312071"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1400740"],"award-info":[{"award-number":["DMS 1400740"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1405348"],"award-info":[{"award-number":["DMS 1405348"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1312071"],"award-info":[{"award-number":["DMS-1312071"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1400740"],"award-info":[{"award-number":["DMS 1400740"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1405348"],"award-info":[{"award-number":["DMS 1405348"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1312071"],"award-info":[{"award-number":["DMS-1312071"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1400740"],"award-info":[{"award-number":["DMS 1400740"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    The method of shifted partial derivatives introduced A. Gupta et\u00a0al. [\n                    <italic>Approaching the chasm at depth four<\/italic>\n                    , IEEE Comp. Soc., 2013, pp.\u00a065-73] and N. Kayal [\n                    <italic>An exponential lower bound for the sum of powers of bounded degree polynomials<\/italic>\n                    , ECCC 19, 2010, p.\u00a081], was used to prove a super-polynomial lower bound on the size of depth four circuits needed to compute the permanent. We show that this method alone cannot prove that the padded permanent\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l Superscript n minus m Baseline normal p normal e normal r normal m Subscript m\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mi>\n                                \u2113\n                                \n                              <\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>n<\/mml:mi>\n                                <mml:mo>\n                                  \u2212\n                                  \n                                <\/mml:mo>\n                                <mml:mi>m<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:msub>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi mathvariant=\"normal\">p<\/mml:mi>\n                                <mml:mi mathvariant=\"normal\">e<\/mml:mi>\n                                <mml:mi mathvariant=\"normal\">r<\/mml:mi>\n                                <mml:mi mathvariant=\"normal\">m<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>m<\/mml:mi>\n                            <\/mml:msub>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell ^{n-m}\\mathrm {perm}_m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    cannot be realized inside the\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper G upper L Subscript n squared\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                            <mml:msub>\n                              <mml:mi>L<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:msup>\n                                  <mml:mi>n<\/mml:mi>\n                                  <mml:mn>2<\/mml:mn>\n                                <\/mml:msup>\n                              <\/mml:mrow>\n                            <\/mml:msub>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">GL_{n^2}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -orbit closure of the determinant\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal d normal e normal t Subscript n\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"normal\">d<\/mml:mi>\n                              <mml:mi mathvariant=\"normal\">e<\/mml:mi>\n                              <mml:mi mathvariant=\"normal\">t<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathrm {det}_n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    when\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n greater-than 2 m squared plus 2 m\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:msup>\n                              <mml:mi>m<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mi>m<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n&gt;2m^2+2m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Our proof relies on several simple degenerations of the determinant polynomial, Macaulay\u2019s theorem, which gives a lower bound on the growth of an ideal, and a lower bound estimate from [\n                    <italic>Approaching the chasm at depth four<\/italic>\n                    , IEEE Comp. Soc., 2013, pp.\u00a065-73] regarding the shifted partial derivatives of the determinant.\n                  <\/p>","DOI":"10.1090\/mcom\/3284","type":"journal-article","created":{"date-parts":[[2017,6,8]],"date-time":"2017-06-08T09:48:07Z","timestamp":1496915287000},"page":"2037-2045","source":"Crossref","is-referenced-by-count":3,"title":["The method of shifted partial derivatives cannot separate the permanent from the determinant"],"prefix":"10.1090","volume":"87","author":[{"given":"Klim","family":"Efremenko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Landsberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hal","family":"Schenck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jerzy","family":"Weyman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2017,12,4]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"M. Agrawal and V. Vinay, Arithmetic circuits: A chasm at depth four, In Proc. 49th IEEE Symposium on Foundations of Computer Science (2008), 67\u201375.","DOI":"10.1109\/FOCS.2008.32"},{"key":"2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","article-title":"The parallel evaluation of general arithmetic expressions","volume":"21","author":"Brent, Richard P.","year":"1974","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"3","unstructured":"K. Efremenko, J. M. Landsberg, H. Schenck, and J. Weyman, On minimal free resolutions of sub-permanents and other ideals arising in complexity theory, preprint (2016). To appear in J. Algebra."},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01214566","article-title":"Eine Bedingung f\u00fcr die Flachheit und das Hilbertpolynom eines graduierten Ringes","volume":"158","author":"Gotzmann, Gerd","year":"1978","journal-title":"Math. Z.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5874","issn-type":"print"},{"key":"5","isbn-type":"print","first-page":"119","article-title":"Generic initial ideals","author":"Green, Mark L.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/376435951X"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s00037-015-0103-x","article-title":"Unifying known lower bounds via geometric complexity theory","volume":"24","author":"Grochow, Joshua A.","year":"2015","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1109\/CCC.2013.16","article-title":"Approaching the chasm at depth four","author":"Gupta, Ankit","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9780769549972"},{"key":"8","doi-asserted-by":"crossref","unstructured":"A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi, Arithmetic circuits: A chasm at depth three, Electronic Colloquium on Computational Complexity (ECCC) 20 (2013), p. 26.","DOI":"10.1109\/FOCS.2013.68"},{"key":"9","unstructured":"N. Kayal, An exponential lower bound for the sum of powers of bounded degree polynomials, Electronic Colloquium on Computational Complexity (ECCC) 19 (2012), p. 81."},{"key":"10","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","article-title":"Arithmetic circuits: the chasm at depth four gets wider","volume":"448","author":"Koiran, Pascal","year":"2012","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s10231-011-0238-6","article-title":"Equations for secant varieties of Veronese and other varieties","volume":"192","author":"Landsberg, J. M.","year":"2013","journal-title":"Ann. Mat. Pura Appl. (4)","ISSN":"https:\/\/id.crossref.org\/issn\/0373-3114","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01294256","article-title":"Lower bounds on arithmetic circuits via partial derivatives","volume":"6","author":"Nisan, Noam","year":"1996","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"13","unstructured":"J. J. Sylvester, On the principles of the calculus of forms, Cambridge and Dublin Mathematical Journal (1852), 52\u201397."},{"key":"14","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.ic.2014.09.004","article-title":"Improved bounds for reduction to depth 4 and depth 3","volume":"240","author":"Tavenas, S\u00e9bastien","year":"2015","journal-title":"Inform. and Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0890-5401","issn-type":"print"},{"key":"15","isbn-type":"print","first-page":"249","article-title":"Completeness classes in algebra","author":"Valiant, L. G.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0897910036"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03284-1\/mcom3284_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03284-1\/S0025-5718-2017-03284-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03284-1\/S0025-5718-2017-03284-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:41:39Z","timestamp":1776800499000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03284-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,4]]},"references-count":15,"journal-issue":{"issue":"312","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["S0025-5718-2017-03284-1"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3284","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2017,12,4]]}}}