{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:03:29Z","timestamp":1775282609531,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>\n            An arithmetic formula is multilinear if the polynomial computed by each of its subformulas is multilinear. We prove that any multilinear arithmetic formula for the permanent or the determinant of an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrix is of size super-polynomial in\n            <jats:italic>n<\/jats:italic>\n            . Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multilinear formulas of constant depth.\n          <\/jats:p>","DOI":"10.1145\/1502793.1502797","type":"journal-article","created":{"date-parts":[[2009,4,15]],"date-time":"2009-04-15T13:37:07Z","timestamp":1239802627000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":67,"title":["Multi-linear formulas for permanent and determinant are of super-polynomial size"],"prefix":"10.1145","volume":"56","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[{"name":"Weizmann Institute, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,4,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007378"},{"key":"e_1_2_1_2_1","unstructured":"Alon N. Spencer J. H. and Erdos P. 1992. The Probabiliatic Method. Wiley New York.  Alon N. Spencer J. H. and Erdos P. 1992. The Probabiliatic Method. Wiley New York."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Burgisser P. Clausen M. and Shokrollahi M. A. 1997. Algebraic Complexity Theory. Springer-Verlag New York.  Burgisser P. Clausen M. and Shokrollahi M. A. 1997. Algebraic Complexity Theory. Springer-Verlag New York.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276872"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002009900021"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214050"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a006"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.22"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90083-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744302"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001609"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90060-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Valiant L. G. 1992. Why is Boolean complexity theory difficult&quest; In Boolean Function Complexity (M. S. Paterson ed.) Lond. Math. Soc. Lecture Note Ser. Vol. 169 Cambridge University Press Cambridge UK 84--94.   Valiant L. G. 1992. Why is Boolean complexity theory difficult&quest; In Boolean Function Complexity (M. S. Paterson ed.) Lond. Math. Soc. Lecture Note Ser. Vol. 169 Cambridge University Press Cambridge UK 84--94.","DOI":"10.1017\/CBO9780511526633.008"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(87)80063-9"},{"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\/1502793.1502797","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1502793.1502797","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:37Z","timestamp":1750253377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502797"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1502793.1502797"],"URL":"https:\/\/doi.org\/10.1145\/1502793.1502797","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2004-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}