{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:41:49Z","timestamp":1781077309691,"version":"3.54.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001843","name":"SERB","doi-asserted-by":"crossref","award":["MTR\/2017\/000958"],"award-info":[{"award-number":["MTR\/2017\/000958"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            We show that there is a sequence of explicit multilinear polynomials\n            <jats:italic>\n              P\n              <jats:sub>n<\/jats:sub>\n            <\/jats:italic>\n            (x\n            <jats:sub>1<\/jats:sub>\n            , \u2026 ,x\n            <jats:sub>n<\/jats:sub>\n            ) \u03f5 R [x\n            <jats:sub>1<\/jats:sub>\n            , \u2026 ,x\n            <jats:sub>n<\/jats:sub>\n            ] with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for\n            <jats:italic>\n              P\n              <jats:sub>n<\/jats:sub>\n            <\/jats:italic>\n            must have size exp (\u03a9 (\n            <jats:italic>n<\/jats:italic>\n            )) This builds on (and strengthens) a result of Yehudayoff (STOC 2019) who showed a lower bound of exp (\u03a9(\u221an)).\n          <\/jats:p>","DOI":"10.1145\/3417758","type":"journal-article","created":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T04:07:32Z","timestamp":1601525252000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Strongly Exponential Separation between Monotone VP and Monotone VNP"],"prefix":"10.1145","volume":"12","author":[{"given":"Srikanth","family":"Srinivasan","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Bombay, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200404"},{"key":"e_1_2_1_3_1","volume-title":"Expander CNFs have exponential DNNF size. CoRR abs\/1411.1995","author":"Bova Simone","year":"2014"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.05.002"},{"key":"e_1_2_1_5_1","volume-title":"Ser. I 1987","author":"Gashkov S. B.","year":"1987"},{"key":"e_1_2_1_6_1","volume-title":"Sergeev","author":"Gashkov Sergey B.","year":"2012"},{"key":"e_1_2_1_7_1","first-page":"15","article-title":"Separating the k-party communication complexity hierarchy: An application of the Zarankiewicz problem","volume":"13","author":"Hayes Thomas P.","year":"2011","journal-title":"Discr. Math. Theor. Comput. Sci."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322341"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9574-4"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the All-union Seminar on Discrete Mathematics and Its Applications. Moskov. Gos","author":"Kasim-Zade O. M.","year":"1986"},{"key":"e_1_2_1_12_1","volume-title":"Communication Complexity: and Applications","author":"Rao Anup"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.013"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"e_1_2_1_15_1","volume-title":"A survey of lower bounds in arithmetic circuit complexity. Github Survey","author":"Saptharishi Ramprasad","year":"2015"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90083-9"},{"key":"e_1_2_1_17_1","unstructured":"Eli Shamir and Marc Snir. 1977. Lower Bounds on the Number of Multiplications and the Number of Additions in Monotone Computations. IBM Thomas J. Watson Research Division.  Eli Shamir and Marc Snir. 1977. Lower Bounds on the Number of Multiplications and the Number of Additions in Monotone Computations. IBM Thomas J. Watson Research Division."},{"key":"e_1_2_1_18_1","first-page":"3","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka Amir","year":"2010","journal-title":"Found. Trends Theoret. Comput. Sci."},{"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.1016\/0304-3975(80)90060-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316311"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417758","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:14Z","timestamp":1750197674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3417758"],"URL":"https:\/\/doi.org\/10.1145\/3417758","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,30]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}