{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T21:28:06Z","timestamp":1673299686804},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T00:00:00Z","timestamp":1535500800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/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":[[2018,10,31]]},"abstract":"\n In 1979, Valiant showed that the complexity class\n VP<\/jats:bold>\n e<\/jats:sub>\n of families with polynomially bounded formula size is contained in the class\n VP<\/jats:bold>\n s<\/jats:sub>\n of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes, we study the topological closure\n VP<\/jats:bold>\n e<\/jats:sub>\n , i.e., the class of polynomials that can be approximated arbitrarily closely by polynomials in\n VP<\/jats:bold>\n e<\/jats:sub>\n . We describe\n VP<\/jats:bold>\n e<\/jats:sub>\n using the well-known continuant polynomial (in characteristic different from 2). Further understanding this polynomial seems to be a promising route to new formula size lower bounds.\n <\/jats:p>\n \n Our methods are rooted in the study of ABPs of small constant width. In 1992, Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of\n VP<\/jats:bold>\n e<\/jats:sub>\n .\n <\/jats:p>\n \n As a natural continuation of this work, we prove that the class\n VPN<\/jats:bold>\n can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.\n <\/jats:p>","DOI":"10.1145\/3209663","type":"journal-article","created":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T13:45:11Z","timestamp":1535636711000},"page":"1-29","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On Algebraic Branching Programs of Small Width"],"prefix":"10.1145","volume":"65","member":"320","published-online":{"date-parts":[[2018,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0114-7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2011.576539"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221006"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575865"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90113-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 32nd Computational Complexity Conference (CCC\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Ryan O\u2019Donnell (Ed.)","volume":"79","author":"Bringmann Karl","year":"2017","unstructured":"Karl Bringmann , Christian Ikenmeyer , and Jeroen Zuiddam . 2017 . On algebraic branching programs of small width . In Proceedings of the 32nd Computational Complexity Conference (CCC\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Ryan O\u2019Donnell (Ed.) , Vol. 79 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 20:1--20:31. Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. 2017. On algebraic branching programs of small width. In Proceedings of the 32nd Computational Complexity Conference (CCC\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Ryan O\u2019Donnell (Ed.), Vol. 79. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 20:1--20:31."},{"key":"e_1_2_1_9_1","volume-title":"Completeness and Reduction in Algebraic Complexity Theory. Algorithms Comput. Math","author":"B\u00fcrgisser Peter","unstructured":"Peter B\u00fcrgisser . 2000. Completeness and Reduction in Algebraic Complexity Theory. Algorithms Comput. Math ., Vol. 7 . Springer-Verlag , Berlin . xii+168 pages. Peter B\u00fcrgisser. 2000. Completeness and Reduction in Algebraic Complexity Theory. Algorithms Comput. Math., Vol. 7. Springer-Verlag, Berlin. xii+168 pages."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115473.3115783"},{"key":"e_1_2_1_11_1","volume-title":"Algebraic Complexity Theory. Grundlehren Math. Wiss","author":"B\u00fcrgisser Peter","unstructured":"Peter B\u00fcrgisser , Michael Clausen , and M. Amin Shokrollahi . 1997. Algebraic Complexity Theory. Grundlehren Math. Wiss ., Vol. 315 . Springer-Verlag , Berlin . xxiv+618 pages. Peter B\u00fcrgisser, Michael Clausen, and M. Amin Shokrollahi. 1997. Algebraic Complexity Theory. Grundlehren Math. Wiss., Vol. 315. Springer-Verlag, Berlin. xxiv+618 pages."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993704"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488627"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/090765328"},{"key":"e_1_2_1_15_1","unstructured":"Charles Conley and Valentin Ovsienko. 2017. Rotundus: triangulations Chebyshev polynomials and Pfaffians. arXiv:1707.09106. Charles Conley and Valentin Ovsienko. 2017. Rotundus: triangulations Chebyshev polynomials and Pfaffians. arXiv:1707.09106."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Workshop on Algebraic Complexity Theory (WACT\u201916)","author":"Forbes Michael","year":"2016","unstructured":"Michael Forbes . 2016 . Some Concrete Questions on the Border Complexity of Polynomials . Proceedings of the Workshop on Algebraic Complexity Theory (WACT\u201916) . Retrieved from https:\/\/www.youtube.com\/watch?v=1HMogQIHT6Q. Michael Forbes. 2016. Some Concrete Questions on the Border Complexity of Polynomials. Proceedings of the Workshop on Algebraic Complexity Theory (WACT\u201916). Retrieved from https:\/\/www.youtube.com\/watch?v=1HMogQIHT6Q."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0103-x"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","volume":"55","author":"Grochow Joshua A.","year":"2016","unstructured":"Joshua A. Grochow , Ketan D. Mulmuley , and Youming Qiao . 2016 . Boundaries of VP and VNP . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) , Vol. 55 . 34:1--34:14. Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. 2016. Boundaries of VP and VNP. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916), Vol. 55. 34:1--34:14."},{"key":"e_1_2_1_19_1","unstructured":"Yonghui Guan. 2015. Brill\u2019s equations as a GL(V)-module. arXiv:1508.02293 Yonghui Guan. 2015. Brill\u2019s equations as a GL(V)-module. arXiv:1508.02293"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.16"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2013.825892"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-05-00506-0"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4171\/CMH\/292"},{"key":"e_1_2_1_24_1","volume-title":"Landsberg and Mateusz Micha\u0142ek","author":"Joseph","year":"2016","unstructured":"Joseph M. Landsberg and Mateusz Micha\u0142ek . 2016 . A 2n^{2<\/sup> − log(n) − 1 lower bound for the border rank of matrix multiplication. arXiv:1608.07486 Joseph M. Landsberg and Mateusz Micha\u0142ek. 2016. A 2n2<\/sup> − log(n) − 1 lower bound for the border rank of matrix multiplication. arXiv:1608.07486"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a011"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90023-1"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 18th Australasian Theory Symposium on Computing. Australian Computer Society, Inc., 59--68","author":"Mahajan Meena","year":"2012","unstructured":"Meena Mahajan , Nitin Saurabh , and Karteek Sreenivasaiah . 2012 . Counting paths in planar width 2 branching programs . In Proceedings of the 18th Australasian Theory Symposium on Computing. Australian Computer Society, Inc., 59--68 . Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=2523693.2523701. Meena Mahajan, Nitin Saurabh, and Karteek Sreenivasaiah. 2012. Counting paths in planar width 2 branching programs. In Proceedings of the 18th Australasian Theory Symposium on Computing. Australian Computer Society, Inc., 59--68. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=2523693.2523701."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.09.006"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/080718115"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"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.1080\/10586458.2015.1037872"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_35_1","volume-title":"Combinatorial Mathematics. Published by The Mathematical Association of America, distributed by John Wiley and Sons","author":"Ryser Herbert John","unstructured":"Herbert John Ryser . 1963. Combinatorial Mathematics. Published by The Mathematical Association of America, distributed by John Wiley and Sons , Inc., New York . xiv+154 pages. Herbert John Ryser. 1963. Combinatorial Mathematics. Published by The Mathematical Association of America, distributed by John Wiley and Sons, Inc., New York. xiv+154 pages."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","volume":"4","author":"Saha Chandan","year":"2009","unstructured":"Chandan Saha , Ramprasad Saptharishi , and Nitin Saxena . 2009 . The power of depth 2 circuits over algebras . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , Vol. 4 . 371--382. arXiv:0904.2058 Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. 2009. The power of depth 2 circuits over algebras. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Vol. 4. 371--382. arXiv:0904.2058"},{"key":"e_1_2_1_37_1","unstructured":"Ramprasad Saptharishi. 2016. A survey of lower bounds in arithmetic circuit complexity 3.0.2. Retrieved from https:\/\/github.com\/dasarpmar\/lowerbounds-survey. Ramprasad Saptharishi. 2016. A survey of lower bounds in arithmetic circuit complexity 3.0.2. Retrieved from https:\/\/github.com\/dasarpmar\/lowerbounds-survey."},{"key":"e_1_2_1_38_1","volume-title":"Rank and optimal computation of generic tensors. Linear Algebra Appl. 52\/53","author":"Strassen Volker","year":"1983","unstructured":"Volker Strassen . 1983. Rank and optimal computation of generic tensors. Linear Algebra Appl. 52\/53 ( 1983 ), 645--685. Volker Strassen. 1983. Rank and optimal computation of generic tensors. Linear Algebra Appl. 52\/53 (1983), 645--685."},{"key":"e_1_2_1_39_1","volume-title":"Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math. 375\/376","author":"Strassen Volker","year":"1987","unstructured":"Volker Strassen . 1987. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math. 375\/376 ( 1987 ), 406--443. Volker Strassen. 1987. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math. 375\/376 (1987), 406--443."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_41_1","volume-title":"Reducibility by Algebraic Projections","author":"Valiant Leslie G.","unstructured":"Leslie G. Valiant . 1980. Reducibility by Algebraic Projections . University of Edinburgh , Department of Computer Science. Internal Report. Leslie G. Valiant. 1980. Reducibility by Algebraic Projections. University of Edinburgh, Department of Computer Science. Internal Report."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.03.015"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T20:52:50Z","timestamp":1672519970000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209663"}},"subtitle":[],"editor":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[]},{"given":"Christian","family":"Ikenmeyer","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0003-0651-6238","authenticated-orcid":false,"given":"Jeroen","family":"Zuiddam","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2018,8,29]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3209663"],"URL":"http:\/\/dx.doi.org\/10.1145\/3209663","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2018,8,29]]},"assertion":[{"value":"2017-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}}