{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:12Z","timestamp":1750220952181,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":21,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"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":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316311","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"425-429","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Separating monotone VP and VNP"],"prefix":"10.1145","author":[{"given":"Amir","family":"Yehudayoff","sequence":"first","affiliation":[{"name":"Technion, Israel"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"volume-title":"Springer Science and Business Media","year":"1997","author":"B\u00fcrgisser P.","key":"e_1_3_2_1_1_1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen. Algebraic complexity theory. Annual Review of Computer Science 3 pages 317\u2013347 1988.   J. von zur Gathen. Algebraic complexity theory. Annual Review of Computer Science 3 pages 317\u2013347 1988.","DOI":"10.1146\/annurev.cs.03.060188.001533"},{"key":"e_1_3_2_1_3_1","unstructured":"P. Hrube\u0161. private communication.  P. Hrube\u0161. private communication."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"P. Hrube\u0161 and A. Yehudayoff. Monotone separations for constant degree polynomials. Information Processing Letters 110 (1) pages 1\u20133 2009.  P. Hrube\u0161 and A. Yehudayoff. Monotone separations for constant degree polynomials. Information Processing Letters 110 (1) pages 1\u20133 2009.","DOI":"10.1016\/j.ipl.2009.09.003"},{"key":"e_1_3_2_1_5_1","first-page":"55","author":"Hrube\u0161 P.","year":"2016","journal-title":"On isoperimetric profiles and computational complexity. LIPIcs-Leibniz International Proceedings in Informatics"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"L. Hyafil. On the parallel evaluation of multivariate polynomials. SICOMP 8(2) pages 120\u2013123 1979.  L. Hyafil. On the parallel evaluation of multivariate polynomials. SICOMP 8(2) pages 120\u2013123 1979.","DOI":"10.1137\/0208010"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322341"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.02.003"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9216-x"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"W. Miller. Computational complexity and numerical stability. SlCOMP 4 pages 97\u2013107 1975.  W. Miller. Computational complexity and numerical stability. SlCOMP 4 pages 97\u2013107 1975.","DOI":"10.1137\/0204009"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321916"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374479"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"C.P. Schnorr. A lower bound on the number of additions in monotone computations. Theoretical Computer Science 2 (3) pages 305\u2013315 1976.  C.P. Schnorr. A lower bound on the number of additions in monotone computations. Theoretical Computer Science 2 (3) pages 305\u2013315 1976.","DOI":"10.1016\/0304-3975(76)90083-9"},{"issue":"1","key":"e_1_3_2_1_16_1","first-page":"301","volume":"13","author":"Shamir E.","year":"1979","journal-title":"Journal Theory of Computing Systems"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science 8 (2) pages 189\u2013201 1979.  L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science 8 (2) pages 189\u2013201 1979.","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90060-2"},{"issue":"4","key":"e_1_3_2_1_20_1","first-page":"641","volume":"12","author":"Valiant L. G.","year":"1983","journal-title":"Fast parallel computation of polynomials using few processors. SIAM J. on Computing"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"e_1_3_2_1_22_1","unstructured":"Abstract 1 Introduction 2 The Separation 3 Proof of Structure Lemma 4 Proof of Weakness Lemma Acknowledgments References  Abstract 1 Introduction 2 The Separation 3 Proof of Structure Lemma 4 Proof of Weakness Lemma Acknowledgments References"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316311","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316311","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\/3313276.3316311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":21,"alternative-id":["10.1145\/3313276.3316311","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316311","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}