{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T21:44:36Z","timestamp":1786139076720,"version":"3.56.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1705028"],"award-info":[{"award-number":["CCF-1705028"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            We show that there is an equation of degree at most poly(\n            <jats:italic>n<\/jats:italic>\n            ) for the (Zariski closure of the) set of the non-rigid matrices: That is, we show that for every large enough field \ud835\udd3d, there is a non-zero\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            -variate polynomial\n            <jats:italic>P<\/jats:italic>\n            \u03b5 \ud835\udd3d[\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1, 1<\/jats:sub>\n            , ...,\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n, n<\/jats:italic>\n            <\/jats:sub>\n            ] of degree at most poly(\n            <jats:italic>n<\/jats:italic>\n            ) such that every matrix\n            <jats:italic>M<\/jats:italic>\n            that can be written as a sum of a matrix of rank at most\n            <jats:italic>n<\/jats:italic>\n            \/100 and a matrix of sparsity at most\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/100 satisfies\n            <jats:italic>P(M)<\/jats:italic>\n            = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer, and Landsberg [\n            <jats:xref ref-type=\"bibr\">9<\/jats:xref>\n            ] and improves the best upper bound known for this problem down from exp (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) [\n            <jats:xref ref-type=\"bibr\">9<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">12<\/jats:xref>\n            ] to poly(\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices\n            <jats:italic>M<\/jats:italic>\n            such that the linear transformation represented by\n            <jats:italic>M<\/jats:italic>\n            can be computed by an algebraic circuit with at most\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded.\n          <\/jats:p>\n          <jats:p>\n            Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [\n            <jats:xref ref-type=\"bibr\">21<\/jats:xref>\n            ] to construct low-degree \u201cuniversal\u201d maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low-degree annihilating polynomial completes the proof.\n          <\/jats:p>\n          <jats:p>\n            As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [\n            <jats:xref ref-type=\"bibr\">11<\/jats:xref>\n            ].\n          <\/jats:p>","DOI":"10.1145\/3543685","type":"journal-article","created":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T11:11:39Z","timestamp":1658833899000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7143-7280","authenticated-orcid":false,"given":"Ben Lee","family":"Volk","sequence":"first","affiliation":[{"name":"Efi Arazi School of Computer Science, Reichman University, Herzliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6430-0219","authenticated-orcid":false,"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering, IIT Bombay Mumbai, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,9,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050023"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00067"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00084"},{"key":"e_1_3_3_5_2","unstructured":"Markus Bl\u00e4ser and Christian Ikenmeyer. 2017. Introduction to geometric complexity theory. http:\/\/pcwww.liv.ac.uk\/iken\/teaching_sb\/summer17\/introtogct\/gct.pdf."},{"key":"e_1_3_3_6_2","article-title":"Variety membership testing, algebraic natural proofs, and geometric complexity theory","volume":"1911","author":"Bl\u00e4ser Markus","year":"2019","unstructured":"Markus Bl\u00e4ser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, and Frank-Olaf Schreyer. 2019. Variety membership testing, algebraic natural proofs, and geometric complexity theory. CoRR abs\/1911.02534 (2019).","journal-title":"CoRR"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90766-5"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00085"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a018"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9258-8"},{"key":"e_1_3_3_11_2","article-title":"Towards an algebraic natural proofs barrier via polynomial identity testing","volume":"1701","author":"Grochow Joshua A.","year":"2017","unstructured":"Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. 2017. Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR abs\/1701.01717 (2017).","journal-title":"CoRR"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0061-0"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207004"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000011"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9136-8"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.09.006"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a007"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535928"},{"key":"e_1_3_3_21_2","unstructured":"Ramprasad Saptharishi. 2015. A survey of lower bounds in arithmetic circuit complexity. (2015). Retrieved from https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203010"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543685","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:48Z","timestamp":1750186848000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3543685"],"URL":"https:\/\/doi.org\/10.1145\/3543685","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-05-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}