{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T13:03:44Z","timestamp":1753275824609,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":82,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"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":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649743","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"130-140","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6920-4998","authenticated-orcid":false,"given":"C. S.","family":"Bhargav","sequence":"first","affiliation":[{"name":"IIT Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0572-3721","authenticated-orcid":false,"given":"Prateek","family":"Dwivedi","sequence":"additional","affiliation":[{"name":"IIT Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6931-898X","authenticated-orcid":false,"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[{"name":"IIT Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1901272116"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0114-7"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221006"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"C.S. Bhargav Prateek Dwivedi and Nitin Saxena. 2024. Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring. https:\/\/cse.iitk.ac.in\/users\/nitin\/papers\/PresentableVNP.pdf","DOI":"10.1145\/3618260.3649743"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365667"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575865"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90113-3"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-021-00209-y"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2020.21"},{"key":"e_1_3_2_1_10_1","unstructured":"Markus Bl\u00e4ser and Christian Ikenmeyer. 2018. Introduction to geometric complexity theory. https:\/\/www.dcs.warwick.ac.uk\/~u2270030\/teaching_sb\/summer17\/introtogct\/gct.pdf Lecture Notes"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209663"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-002-0059-5"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-020-09477-6"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20624-5_37"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000043"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.04.006"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.21214"},{"key":"e_1_3_2_1_20_1","unstructured":"Chi-Ning Chou Mrinal Kumar and Noam Solomon. 2019. Closure of VP under taking factors: a short and simple proof. arxiv:1903.02366. arxiv:1903.02366"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a013"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00018"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00026"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510359"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735850"},{"key":"e_1_3_2_1_27_1","unstructured":"Michael Forbes. 2016. Some Concrete Questions on the Border Complexity of Polynomials. https:\/\/www.youtube.com\/watch?v=1HMogQIHT6Q Talk at the Workshop on Algebraic Complexity Theory (WACT) 2016 in Tel Aviv."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852051"},{"volume-title":"Polynomial identity testing of read-once oblivious algebraic branching programs. Ph. D. Dissertation","author":"Forbes Michael A.","key":"e_1_3_2_1_29_1","unstructured":"Michael A. Forbes. 2014. Polynomial identity testing of read-once oblivious algebraic branching programs. Ph. D. Dissertation. Massachusetts Institute of Technology, Cambridge, MA, USA. https:\/\/hdl.handle.net\/1721.1\/89843"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188792"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2021.v017a010"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2015.11.013"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2016.34"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1347395"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_3_2_1_36_1","volume-title":"Innovations in Computer","author":"Jansen Maurice J.","year":"2011","unstructured":"Maurice J. Jansen. 2011. Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods. In Innovations in Computer Science - ICS. Tsinghua University Press, 87\u2013100. http:\/\/conference.iiis.tsinghua.edu.cn\/ICS2011\/content\/papers\/4.html"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214035"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28443"},{"key":"e_1_3_2_1_40_1","first-page":"375","article-title":"Factorization of Polynomials Given by Straight-Line","volume":"5","author":"Kaltofen Erich","year":"1989","unstructured":"Erich Kaltofen. 1989. Factorization of Polynomials Given by Straight-Line Programs. Adv. Comput. Res., 5 (1989), 375\u2013412. https:\/\/users.cs.duke.edu\/~elk27\/bibliography\/89\/Ka89_slpfac.pdf","journal-title":"Programs. Adv. Comput. Res."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390768.1390790"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12163"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0002-8"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0102-y"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371506"},{"key":"e_1_3_2_1_47_1","volume-title":"Hardness-Randomness Tradeoffs for Algebraic Computation. Bull. EATCS, 129","author":"Kumar Mrinal","year":"2019","unstructured":"Mrinal Kumar and Ramprasad Saptharishi. 2019. Hardness-Randomness Tradeoffs for Algebraic Computation. Bull. EATCS, 129 (2019), http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/591\/599"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.40"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108183192"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a011"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1515\/9783110285581.267"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05446-9_4"},{"volume-title":"Polyn\u00f4mes et coefficients. (Polynomials and coefficients). Ph. D. Dissertation","author":"Malod Guillaume","key":"e_1_3_2_1_53_1","unstructured":"Guillaume Malod. 2003. Polyn\u00f4mes et coefficients. (Polynomials and coefficients). Ph. D. Dissertation. Claude Bernard University Lyon , France. https:\/\/tel.archives-ouvertes.fr\/tel-00087399"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCO.2006.09.006"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1201\/b15006"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944346"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184341"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/080718115"},{"volume-title":"Algebraic geometry","author":"Mumford David","key":"e_1_3_2_1_60_1","unstructured":"David Mumford. 1976. Algebraic geometry. I. Springer-Verlag. https:\/\/link.springer.com\/book\/9783540586579 Complex projective varieties"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0130-2"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373207.3404010"},{"volume-title":"Computational complexity","author":"Papadimitriou Christos H.","key":"e_1_3_2_1_63_1","unstructured":"Christos H. Papadimitriou. 1994. Computational complexity. Addison-Wesley Publishing Company, Reading, MA. isbn:0-201-53082-1 https:\/\/dl.acm.org\/doi\/abs\/10.5555\/1074100.1074233"},{"key":"e_1_3_2_1_64_1","unstructured":"Sylvain P\u00e9rifel. 2004. Polyn\u00f4mes donn\u00e9s par des circuits alg\u00e9briques et g\u00e9n\u00e9ralisation du mod\u00e8le de Valiant. \u00c9cole Normal Sup\u00e9rieure de Lyon France. Master\u2019s Thesis"},{"key":"e_1_3_2_1_65_1","first-page":"86","article-title":"Understanding the Mulmuley-Sohoni approach to P vs","volume":"78","author":"Regan Kenneth W.","year":"2002","unstructured":"Kenneth W. Regan. 2002. Understanding the Mulmuley-Sohoni approach to P vs. NP. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 78 (2002), 86\u201399. issn:0252-9742 https:\/\/cse.buffalo.edu\/faculty\/regan\/papers\/pdf\/Reg02MSFD.pdf","journal-title":"NP. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"e_1_3_2_1_66_1","unstructured":"Ramprasad Saptharishi. 2015. A survey of lower bounds in arithmetic circuit complexity. https:\/\/github.com\/dasarpmar\/lowerbounds-survey Github Survey"},{"key":"e_1_3_2_1_67_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. Eur. Assoc. Theor. Comput. Sci. EATCS, 99 (2009), 49\u201379. issn:0252-9742 https:\/\/cse.iitk.ac.in\/users\/nitin\/papers\/pit-survey09.pdf","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"e_1_3_2_1_68_1","volume-title":"Comput. Sci. Appl. Logic","volume":"146","author":"Saxena Nitin","year":"2014","unstructured":"Nitin Saxena. 2014. Progress on polynomial identity testing-II. In Perspectives in computational complexity (Progr. Comput. Sci. Appl. Logic, Vol. 26). Birkh\u00e4user\/Springer, 131\u2013146. isbn:978-3-319-05445-2; 978-3-319-05446-9 https:\/\/cse.iitk.ac.in\/users\/nitin\/papers\/pit-survey13.pdf"},{"volume-title":"Closure of algebraic classes under factoring. https:\/\/www.cse.iitk.ac.in\/users\/nitin\/talks\/Sep2023-paris.pdf Talk at Recent Trends in Computer Algebra (2023) in Institut Henri Poincar\u00e9","author":"Saxena Nitin","key":"e_1_3_2_1_69_1","unstructured":"Nitin Saxena. 2023. Closure of algebraic classes under factoring. https:\/\/www.cse.iitk.ac.in\/users\/nitin\/talks\/Sep2023-paris.pdf Talk at Recent Trends in Computer Algebra (2023) in Institut Henri Poincar\u00e9, Paris."},{"key":"e_1_3_2_1_70_1","unstructured":"Jayalal Sharma and Dinesh K.. 2012. Advanced Complexity Theory. https:\/\/www.cse.iitm.ac.in\/~jayalal\/teaching\/CS6840\/2012\/lecture04.pdf Lecture Notes"},{"volume-title":"A computational introduction to number theory and algebra","author":"Shoup Victor","key":"e_1_3_2_1_71_1","unstructured":"Victor Shoup. 2009. A computational introduction to number theory and algebra (second ed.). Cambridge University Press. isbn:978-0-521-51644-0 https:\/\/shoup.net\/ntb\/"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_35"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-021-00215-0"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203010"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_2_1_77_1","unstructured":"Madhu Sudan. 1998. Algebra and Computation. https:\/\/people.csail.mit.edu\/madhu\/FT98\/ Lecture Notes"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_79_1","volume-title":"Enseign. Math.","volume":"380","author":"Valiant L. G.","year":"1982","unstructured":"L. G. Valiant. 1982. Reducibility by algebraic projections. In Logic and algorithmic (Monogr. Enseign. Math., Vol. 30). Univ. Gen\u00e8ve, Geneva, 365\u2013380."},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.2307\/2007608"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90044-3"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649743","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649743","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649743"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":82,"alternative-id":["10.1145\/3618260.3649743","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649743","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}