{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T15:06:29Z","timestamp":1778166389154,"version":"3.51.4"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001658","name":"Minerva Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001658","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,11]]},"abstract":"\n We show that any explicit example for a tensor\n A<\/jats:italic>\n : [\n n<\/jats:italic>\n ]\n r<\/jats:sup>\n \u2192\n F<\/jats:italic>\n with tensor-rank \u2265\n n<\/jats:italic>\n r\u010b(1\u2212o(1))<\/jats:sup>\n , where\n r<\/jats:italic>\n =\n r<\/jats:italic>\n (\n n<\/jats:italic>\n ) \u2264 log\n n<\/jats:italic>\n \/log log\n n<\/jats:italic>\n is super-constant, implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over F. This shows that strong enough lower bounds for the size of arithmetic formulas of depth 3 imply super-polynomial lower bounds for the size of general arithmetic formulas.\n <\/jats:p>\n One component of our proof is a new approach for homogenization and multilinearization of arithmetic formulas, that gives the following results:<\/jats:p>\n \n We show that for any\n n<\/jats:italic>\n -variate homogeneous polynomial\n f<\/jats:italic>\n of degree\n r<\/jats:italic>\n , if there exists a (fanin-2) formula of size\n s<\/jats:italic>\n and depth\n d<\/jats:italic>\n for\n f<\/jats:italic>\n then there exists a homogeneous formula of size\n O<\/jats:italic>\n ((\n d<\/jats:italic>\n +\n r<\/jats:italic>\n +1 r) \u010b\n s<\/jats:italic>\n ) for\n f<\/jats:italic>\n . In particular, for any\n r<\/jats:italic>\n \u2264\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ), if there exists a polynomial size formula for\n f<\/jats:italic>\n then there exists a polynomial size homogeneous formula for\n f<\/jats:italic>\n . This refutes a conjecture of Nisan and Wigderson [1996] and shows that super-polynomial lower bounds for homogeneous formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.\n <\/jats:p>\n \n We show that for any\n n<\/jats:italic>\n -variate set-multilinear polynomial\n f<\/jats:italic>\n of degree\n r<\/jats:italic>\n , if there exists a (fanin-2) formula of size\n s<\/jats:italic>\n and depth\n d<\/jats:italic>\n for\n f<\/jats:italic>\n , then there exists a set-multilinear formula of size\n O<\/jats:italic>\n ((\n d<\/jats:italic>\n + 2)\n r<\/jats:sup>\n \u010b\n s<\/jats:italic>\n ) for\n f<\/jats:italic>\n . In particular, for any\n r<\/jats:italic>\n \u2264\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n \/log log\n n<\/jats:italic>\n ), if there exists a polynomial size formula for\n f<\/jats:italic>\n then there exists a polynomial size set-multilinear formula for\n f<\/jats:italic>\n . This shows that super-polynomial lower bounds for set-multilinear formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.\n <\/jats:p>","DOI":"10.1145\/2535928","type":"journal-article","created":{"date-parts":[[2013,12,4]],"date-time":"2013-12-04T14:04:47Z","timestamp":1386165887000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Tensor-Rank and Lower Bounds for Arithmetic Formulas"],"prefix":"10.1145","volume":"60","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[{"name":"Weizmann Institute"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007378"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.28"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276872"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002009900021"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0007-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.013"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707932"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_18_1","first-page":"182","article-title":"Vermeidung von Divisionen","volume":"264","author":"Strassen V.","year":"1973","journal-title":"J. Reine Angew. Math."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/53594.53605"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2535928","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2535928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:06Z","timestamp":1750234206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2535928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2535928"],"URL":"https:\/\/doi.org\/10.1145\/2535928","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2010-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}