{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:20Z","timestamp":1781031440962,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Independent Research Fund Denmark","award":["10.46540\/3103-00116B"],"award-info":[{"award-number":["10.46540\/3103-00116B"]}]},{"name":"VILLUM Foundation Grant","award":["54451"],"award-info":[{"award-number":["54451"]}]},{"name":"UK Research and Innovation (UKRI)","award":["EP\/X028259\/1"],"award-info":[{"award-number":["EP\/X028259\/1"]}]},{"name":"European Union","award":["CountHom, 101077083"],"award-info":[{"award-number":["CountHom, 101077083"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800779","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"631-640","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0572-3721","authenticated-orcid":false,"given":"Prateek","family":"Dwivedi","sequence":"first","affiliation":[{"name":"IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6377-1230","authenticated-orcid":false,"given":"Benedikt","family":"Pago","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6447-0568","authenticated-orcid":false,"given":"Tim","family":"Seppelt","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-016-9692-2"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2025.19"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.24"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90068-U"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2019.3"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26176-4_8"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820609"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751316"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451124"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.74"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.22"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.122"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_2_1_18_1","unstructured":"Anuj Dawar. 2025. Notions of Width: Variables Pebbles and Supports. The Logic in Computer Science Column 147. https:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/865"},{"key":"e_1_3_2_1_19_1","unstructured":"Anuj Dawar Benedikt Pago and Tim Seppelt. 2025. Symmetric Algebraic Circuits and Homomorphism Polynomials. 2502.06740v4."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2026.46"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005108"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.52"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.36"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.40"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Julian D\u00f6rfler Marc Roth Johannes Schmitt and Philip Wellnitz. 2021. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness. doi:10.1007\/s00453-021-00894-9 https:\/\/doi.org\/10.1007\/s00453-021-00894-9 10.1007\/s00453-021-00894-9","DOI":"10.1007\/s00453-021-00894-9"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649644"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2016.003"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20461"},{"key":"e_1_3_2_1_29_1","unstructured":"Prateek Dwivedi Benedikt Pago and Tim Seppelt. 2026. Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials. 2601.09343v1."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2024.27"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3576044"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394739"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Martin Grohe. 2017. Descriptive Complexity Canonisation and Definable Graph Structure Theory. Cambridge University Press. isbn:978-1-139-02886-8 doi:10.1017\/9781139028868 http:\/\/ebooks.cambridge.org\/ref\/id\/CBO9781139028868 10.1017\/9781139028868","DOI":"10.1017\/9781139028868"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470677"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-023-00077-w"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940323"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2025.105"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05446-9_5"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436980.3436982"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-023-01108-0"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840735"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3734215"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Meena Mahajan. 2013. Algebraic Complexity Classes. arXiv. arXiv:1307.3863 [cs] doi:10.48550\/arXiv.1307.3863 arxiv:1307.3863 10.48550\/arXiv.1307.3863","DOI":"10.48550\/arXiv.1307.3863"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9740-y"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00067"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-20(2:9)2024"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2024.53"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0058"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007353"},{"key":"e_1_3_2_1_56_1","unstructured":"David E. Roberson. 2022. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. arXiv. arxiv:2206.10321"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00676-9"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.108"},{"key":"e_1_3_2_1_59_1","unstructured":"Ramprasad Saptharishi. 2021. A Selection of Lower Bounds in Arithmetic Circuit Complexity. Community survey available Github https:\/\/github.com\/dasarpmar\/lowerbounds-survey\/releases\/tag\/v9.0.3"},{"key":"e_1_3_2_1_60_1","volume-title":"Analysis of Algebraic Complexity Classes and Boolean Functions","author":"Saurabh Nitin","year":"2010","unstructured":"Nitin Saurabh. 2016. Analysis of Algebraic Complexity Classes and Boolean Functions. The Institute of Mathematical Sciences. http:\/\/www.hbni.ac.in\/phdthesis\/math\/MATH10201005003.pdf"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.MFCS.2025.89"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","unstructured":"Tim Seppelt. 2024. Homomorphism Indistinguishability. RWTH Aachen University. doi:10.18154\/RWTH-2024-11629 https:\/\/publications.rwth-aachen.de\/record\/998785 10.18154\/RWTH-2024-11629","DOI":"10.18154\/RWTH-2024-11629"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105224"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_66_1","volume-title":"International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=ryGs6iA5Km","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks? In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=ryGs6iA5Km"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:43Z","timestamp":1781028103000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":66,"alternative-id":["10.1145\/3798129.3800779","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800779","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}