{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:15Z","timestamp":1759638615084,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,2]],"date-time":"2019-04-02T00:00:00Z","timestamp":1554163200000},"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":[[2019,6,30]]},"abstract":"<jats:p>We study limitations of polynomials computed by depth-2 circuits built over read-once formulas (ROFs). In particular:<\/jats:p>\n          <jats:p>\n            \u2022 We prove a 2\n            <jats:sup>\n              \u03a9(\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            lower bound for the sum of ROFs computing the 2\n            <jats:italic>n<\/jats:italic>\n            -variate polynomial in VP defined by Raz and Yehudayoff [21].\n          <\/jats:p>\n          <jats:p>\n            \u2022 We obtain a 2\n            <jats:sup>\n              \u03a9(\u221a\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            lower bound on the size of \u03a3 \u03a0\n            <jats:sup>\n              [\n              <jats:italic>n<\/jats:italic>\n              <jats:sup>1\/15<\/jats:sup>\n              ]\n            <\/jats:sup>\n            arithmetic circuits built over restricted ROFs of unbounded depth computing the permanent of an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrix (superscripts on gates denote bound on the fan-in). The restriction is that the number of variables with + gates as a parent in a proper sub formula of the ROF has to be bounded by \u221a\n            <jats:italic>n<\/jats:italic>\n            . This proves an exponential lower bound for a subclass of possibly non-multilinear formulas of unbounded depth computing the permanent polynomial.\n          <\/jats:p>\n          <jats:p>\u2022 We also show an exponential lower bound for the above model against a polynomial in VP.<\/jats:p>\n          <jats:p>\n            \u2022 Finally, we observe that the techniques developed yield an exponential lower bound on the size of \u03a3\u03a0\n            <jats:sup>\n              [\n              <jats:italic>N<\/jats:italic>\n              <jats:sup>1\/30<\/jats:sup>\n              ]\n            <\/jats:sup>\n            arithmetic circuits built over syntactically multi-linear \u03a3\u03a0\u03a3\n            <jats:sup>\n              [\n              <jats:italic>N<\/jats:italic>\n              <jats:sup>1\/4<\/jats:sup>\n              ]\n            <\/jats:sup>\n            arithmetic circuits computing a product of variable disjoint linear forms on\n            <jats:italic>N<\/jats:italic>\n            variables, where the superscripts on gates denote bound on the fan-in.\n          <\/jats:p>\n          <jats:p>Our proof techniques are built on the measure developed by Kumar et al. [14] and are based on a non-trivial analysis of ROFs under random partitions. Further, our results exhibit strengths and provide more insight into the lower bound techniques introduced by Raz [19].<\/jats:p>","DOI":"10.1145\/3313232","type":"journal-article","created":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T18:38:37Z","timestamp":1554403117000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Lower bounds for Sum and Sum of Products of Read-once Formulas"],"prefix":"10.1145","volume":"11","author":[{"given":"C.","family":"Ramya","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_2_1_3_1","unstructured":"Peter B\u00fcrgisser. 2013. Completeness and Reduction in Algebraic Complexity Theory. Vol. 7. Springer Science 8 Business Media.  Peter B\u00fcrgisser. 2013. Completeness and Reduction in Algebraic Complexity Theory. Vol. 7. Springer Science 8 Business Media."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Devdatt Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms (1st ed.). Cambridge University Press New York NY.   Devdatt Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms (1st ed.). Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Michael Forbes. 2014. Polynomial Identity Testing of Read-once Oblivious Algebraic Branching Programs. PhD Thesis Massachusetts Institute of Technology.  Michael Forbes. 2014. Polynomial Identity Testing of Read-once Oblivious Algebraic Branching Programs. PhD Thesis Massachusetts Institute of Technology.","DOI":"10.1109\/FOCS.2013.34"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.34"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276872"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629541"},{"volume-title":"Electron. Colloq. Comput. Complex. 19","year":"2012","author":"Kayal Neeraj","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591823"},{"volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","year":"2015","author":"Kayal Neeraj","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","year":"2016","author":"Kayal Neeraj","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898437"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.46"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.10.019"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007353"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0254-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001609"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"e_1_2_1_26_1","unstructured":"Iddo Tzameret. 2008. Studies in Algebraic and Propositional Proof Complexity. Ph.D Thesis (2008) 33. Retrieved from http:\/\/www.cs.rhul.ac.uk\/home\/tzameret\/Iddo-PhD-thesis.pdf.  Iddo Tzameret. 2008. Studies in Algebraic and Propositional Proof Complexity. Ph.D Thesis (2008) 33. Retrieved from http:\/\/www.cs.rhul.ac.uk\/home\/tzameret\/Iddo-PhD-thesis.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"J. H. van Lint and R. M. Wilson. 2001. A Course in Combinatorics (2nd ed.). Cambridge University Press.  J. H. van Lint and R. M. Wilson. 2001. A Course in Combinatorics (2nd ed.). Cambridge University Press.","DOI":"10.1017\/CBO9780511987045"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858783"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:00Z","timestamp":1750204440000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,2]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3313232"],"URL":"https:\/\/doi.org\/10.1145\/3313232","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,4,2]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}