{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:04Z","timestamp":1750220404079,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"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":[[2021,12,31]]},"abstract":"<jats:p>\n            We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et\u00a0al. (2014) and Mahajan et\u00a0al. (2018). We consider three different variants of graph homomorphisms, namely\n            <jats:italic>injective homomorphisms<\/jats:italic>\n            ,\n            <jats:italic>directed homomorphisms<\/jats:italic>\n            , and\n            <jats:italic>injective directed homomorphisms<\/jats:italic>\n            , and obtain polynomial families complete for VF, VBP, VP, and VNP under each one of these. The polynomial families have the following properties:\n            <jats:list>\n              <jats:list-item>\n                <jats:label>\u2022<\/jats:label>\n                <jats:p>The polynomial families complete for VF, VBP, and VP are model independent, i.e., they do not use a particular instance of a formula, algebraic branching programs, or circuit for characterising VF, VBP, or VP, respectively.<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>\u2022<\/jats:label>\n                <jats:p>\n                  All the polynomial families are hard under\n                  <jats:italic>p<\/jats:italic>\n                  -projections.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>","DOI":"10.1145\/3470858","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T19:28:46Z","timestamp":1630524526000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes"],"prefix":"10.1145","volume":"13","author":[{"given":"Prasad","family":"Chaugule","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Bombay, Mumbai, India"}]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay, Mumbai, India"}]},{"given":"Aditya","family":"Varre","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2021,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9630-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_29"},{"key":"e_1_2_1_6_1","volume-title":"Leibniz International Proceedings in Informatics","volume":"29","author":"Durand Arnaud","year":"2014","unstructured":"Arnaud Durand , Meena Mahajan , Guillaume Malod , Nicolas de Rugy-Altherre , and Nitin Saurabh . 2014 . Homomorphism polynomials complete for VP . In Leibniz International Proceedings in Informatics , Vol. 29 . Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh. 2014. Homomorphism polynomials complete for VP. In Leibniz International Proceedings in Informatics, Vol. 29."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00382"},{"key":"e_1_2_1_8_1","unstructured":"Raymond Greenlaw H. James Hoover and Walter Ruzzo. 1992. A compendium of problems complete for P. Citeseer.  Raymond Greenlaw H. James Hoover and Walter Ruzzo. 1992. A compendium of problems complete for P. Citeseer."},{"key":"e_1_2_1_9_1","volume-title":"Universal search problems. Probl. Inf. Transmiss. 9, 3","author":"Levin Leonid A.","year":"1973","unstructured":"Leonid A. Levin . 1973. Universal search problems. Probl. Inf. Transmiss. 9, 3 ( 1973 ). [in Russian ] Leonid A. Levin. 1973. Universal search problems. Probl. Inf. Transmiss. 9, 3 (1973). [in Russian]"},{"key":"e_1_2_1_10_1","unstructured":"Meena Mahajan. 2013. Algebraic complexity classes. arXiv:cs.CC\/1307.3863. Retrieved from https:\/\/arxiv.org\/abs\/1307.3863.  Meena Mahajan. 2013. Algebraic complexity classes. arXiv:cs.CC\/1307.3863. Retrieved from https:\/\/arxiv.org\/abs\/1307.3863."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9740-y"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11821069_61"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027202"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374479"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470858","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470858"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3470858"],"URL":"https:\/\/doi.org\/10.1145\/3470858","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}