{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:57Z","timestamp":1750694757358,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T00:00:00Z","timestamp":1581379200000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>We show an exponential separation between two well-studied models of algebraic computation, namely, read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits. In particular, we show the following:<\/jats:p>\n          <jats:p>\n            (1) There exists an explicit\n            <jats:italic>n<\/jats:italic>\n            -variate polynomial computable by linear sized multilinear depth-three circuits (with only two product gates) such that every ROABP computing it requires 2\n            <jats:sup>\n              \u03a9\n              <jats:italic>(n)<\/jats:italic>\n            <\/jats:sup>\n            size.\n          <\/jats:p>\n          <jats:p>\n            (2) Any multilinear depth-three circuit computing IMM\n            <jats:italic>\n              <jats:sub>n,d<\/jats:sub>\n            <\/jats:italic>\n            (the iterated matrix multiplication polynomial formed by multiplying\n            <jats:italic>d<\/jats:italic>\n            ,\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            symbolic matrices) has\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u03a9(\n              <jats:italic>d<\/jats:italic>\n              )\n            <\/jats:sup>\n            size. IMM\n            <jats:italic>\n              <jats:sup>n,d<\/jats:sup>\n            <\/jats:italic>\n            can be easily computed by a poly(\n            <jats:italic>n,d<\/jats:italic>\n            ) sized ROABP.\n          <\/jats:p>\n          <jats:p>\n            (3) Further, the proof of (2) yields an exponential separation between multilinear depth-four and multilinear depth-three circuits: There is an explicit\n            <jats:italic>n<\/jats:italic>\n            -variate, degree\n            <jats:italic>d<\/jats:italic>\n            polynomial computable by a poly(\n            <jats:italic>n<\/jats:italic>\n            ) sized multilinear depth-four circuit such that any multilinear depth-three circuit computing it has size\n            <jats:italic>\n              n\n              <jats:sup>\u03a9(d)<\/jats:sup>\n            <\/jats:italic>\n            . This improves upon the quasi-polynomial separation of Reference [36] between these two models.\n          <\/jats:p>\n          <jats:p>The hard polynomial in (1) is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure [15, 33, 34, 36], while (2) is proved via a new adaptation of the dimension of the partial derivatives measure of Reference [32]. Our lower bounds hold over any field.<\/jats:p>","DOI":"10.1145\/3369928","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T12:28:17Z","timestamp":1582633697000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits"],"prefix":"10.1145","volume":"12","author":[{"given":"Neeraj","family":"Kayal","sequence":"first","affiliation":[{"name":"Microsoft Research, Bengaluru, Karnataka, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vineet","family":"Nair","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bengaluru, Karnataka, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chandan","family":"Saha","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bengaluru, Karnataka, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975103"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488649"},{"key":"e_1_2_1_4_1","volume-title":"Eigenvalues and expanders. Combinatorica","author":"Alon N.","year":"1986","unstructured":"N. Alon . 1986. Eigenvalues and expanders. Combinatorica ( 1986 ). N. Alon. 1986. Eigenvalues and expanders. Combinatorica (1986)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"N. Alon and V. D. Milman. 1985. Isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory Ser. (1985).  N. Alon and V. D. Milman. 1985. Isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory Ser. (1985).","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_6_1","first-page":"213","article-title":"A note on the isopoermitric constant. Annu","volume":"4","author":"Buser P.","year":"1982","unstructured":"P. Buser . 1982 . A note on the isopoermitric constant. Annu . Sci. Ecole Norm. 4 , 15 (1982), 213 -- 230 . P. Buser. 1982. A note on the isopoermitric constant. Annu. Sci. Ecole Norm. 4, 15 (1982), 213--230.","journal-title":"Sci. Ecole Norm."},{"key":"e_1_2_1_7_1","unstructured":"J. Cheeger. 1970. Lower bound for the smallest eigenvalue of the laplacian. Prob. Anal. (1970) 195--199.  J. Cheeger. 1970. Lower bound for the smallest eigenvalue of the laplacian. Prob. Anal. (1970) 195--199."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000043"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0131-1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_2_1_11_1","first-page":"787","article-title":"Difference equations, isoperimetric inequality and transience of certain random walks","volume":"284","author":"Dodziuk J.","year":"1984","unstructured":"J. Dodziuk . 1984 . Difference equations, isoperimetric inequality and transience of certain random walks . SIAM J. Comput. 284 , 2 (1984), 787 -- 794 . J. Dodziuk. 1984. Difference equations, isoperimetric inequality and transience of certain random walks. SIAM J. Comput. 284, 2 (1984), 787--794.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214034"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1957999"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"volume-title":"Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913)","author":"Michael","key":"e_1_2_1_15_1","unstructured":"Michael A. Forbes and Amir Shpilka. 2013. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs . In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913) . 243--252. Michael A. Forbes and Amir Shpilka. 2013. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913). 243--252."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591824"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.68"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833243"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804674"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9574-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"volume-title":"Randomness and Computation","author":"Kaltofen Erich","key":"e_1_2_1_24_1","unstructured":"Erich Kaltofen . 1989. Factorization of polynomials given by straight-line programs . In Randomness and Computation . JAI Press , 375--412. Erich Kaltofen. 1989. Factorization of polynomials given by straight-line programs. In Randomness and Computation. JAI Press, 375--412."},{"key":"e_1_2_1_25_1","unstructured":"Neeraj Kayal Chandan Saha and S\u00e9bastien Tavenas. 2015. Formulas having low individual degree.  Neeraj Kayal Chandan Saha and S\u00e9bastien Tavenas. 2015. Formulas having low individual degree."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal and Ramprasad Saptharishi. 2014. A selection of lower bounds for arithmetic circuits. Perspect. Comput. Complex. (2014).  Neeraj Kayal and Ramprasad Saptharishi. 2014. A selection of lower bounds for arithmetic circuits. Perspect. Comput. Complex. (2014).","DOI":"10.1007\/978-3-319-05446-9_5"},{"volume-title":"Proceedings on 33rd Annual ACM Symposium on Theory of Computing. 216--223","author":"Klivans Adam","key":"e_1_2_1_27_1","unstructured":"Adam Klivans and Daniel A. Spielman . 2001. Randomness efficient identity testing of multivariate polynomials . In Proceedings on 33rd Annual ACM Symposium on Theory of Computing. 216--223 . Adam Klivans and Daniel A. Spielman. 2001. Randomness efficient identity testing of multivariate polynomials. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing. 216--223."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Symposium on Fundamentals of Computation Theory (FCT\u201979)","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1979 . On determinants, matchings, and random algorithms . In Proceedings of the Symposium on Fundamentals of Computation Theory (FCT\u201979) . 565--574. L\u00e1szl\u00f3 Lov\u00e1sz. 1979. On determinants, matchings, and random algorithms. In Proceedings of the Symposium on Fundamentals of Computation Theory (FCT\u201979). 565--574."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/866057"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. 410--418","author":"Nisan Noam","year":"1991","unstructured":"Noam Nisan . 1991 . Lower bounds for non-commutative computation (extended abstract) . In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. 410--418 . Noam Nisan. 1991. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. 410--418."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a006"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0254-0"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_2_1_37_1","volume-title":"Recent progress on arithmetic circuit lower bounds. Bull. EATCS 114","author":"Saptharishi Ramprasad","year":"2014","unstructured":"Ramprasad Saptharishi . 2014. Recent progress on arithmetic circuit lower bounds. Bull. EATCS 114 ( 2014 ). Ramprasad Saptharishi. 2014. Recent progress on arithmetic circuit lower bounds. Bull. EATCS 114 (2014)."},{"key":"e_1_2_1_38_1","first-page":"49","article-title":"Progress on polynomial identity testing","volume":"99","author":"Saxena Nitin","year":"2009","unstructured":"Nitin Saxena . 2009 . Progress on polynomial identity testing . Bull. EATCS 99 (2009), 49 -- 79 . Nitin Saxena. 2009. Progress on polynomial identity testing. Bull. EATCS 99 (2009), 49--79.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_39_1","volume-title":"Electr. Colloq. Comput. Complex. 20","author":"Saxena Nitin","year":"2013","unstructured":"Nitin Saxena . 2013 . Progress on polynomial identity testing II . Electr. Colloq. Comput. Complex. 20 (2013), 186. Nitin Saxena. 2013. Progress on polynomial identity testing II. Electr. Colloq. Comput. Complex. 20 (2013), 186."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_41_1","first-page":"3","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka Amir","year":"2010","unstructured":"Amir Shpilka and Amir Yehudayoff . 2010 . Arithmetic circuits: A survey of recent results and open questions . Found. Trends Theor. Comput. Sci. 5 , 3 \u2013 4 (Mar. 2010), 207--388. DOI:https:\/\/doi.org\/10.1561\/0400000039 10.1561\/0400000039 Amir Shpilka and Amir Yehudayoff. 2010. Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5, 3\u20134 (Mar. 2010), 207--388. DOI:https:\/\/doi.org\/10.1561\/0400000039","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_42_1","first-page":"3","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka Amir","year":"2010","unstructured":"Amir Shpilka and Amir Yehudayoff . 2010 . Arithmetic circuits: A survey of recent results and open questions . Found. Trends Theor. Comput. Sci. 5 , 3 \u2013 4 (2010), 207--388. Amir Shpilka and Amir Yehudayoff. 2010. Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5, 3\u20134 (2010), 207--388.","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369928","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:27Z","timestamp":1750203867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,11]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3369928"],"URL":"https:\/\/doi.org\/10.1145\/3369928","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,2,11]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}