{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:07:05Z","timestamp":1750694825554,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":85,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"UKRI","award":["EP\\\/X024431\\\/1"],"award-info":[{"award-number":["EP\\\/X024431\\\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649635","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1935-1943","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Semidefinite Programming and Linear Equations vs. Homomorphism Problems"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9491-2016","authenticated-orcid":false,"given":"Lorenzo","family":"Ciardo","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"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.1017\/S0963548399004071"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.48"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_3_2_1_6_1","unstructured":"Eiichi Bannai and Tatsuro Ito. 1984. Algebraic Combinatorics I. Association Schemes. Benjamin\/Cummings Publishing."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130915479"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.21"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/7228"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.14"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.28"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M128212X"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.46298\/theoretics.23.2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585180"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1312745"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00030"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"A.E. Brouwer A.M. Cohen and A. Neumaier. 1989. Distance-Regular Graphs. Springer Heidelberg.","DOI":"10.1007\/978-3-642-74341-2"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_3_2_1_25_1","volume-title":"Proc. 56th Annual ACM Symposium on Theory of Computing (STOC\u201924)","author":"Chan Siu On","year":"2024","unstructured":"Siu On Chan, Hiu Tsun Ng, and Sijin Peng. 2024. How Random CSPs Fool Hierarchies. In Proc. 56th Annual ACM Symposium on Theory of Computing (STOC\u201924). ACM."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch86"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585112"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1476435"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch25"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Lorenzo Ciardo and Stanislav \u017divn\u00fd. 2023. Semidefinite programming and linear equations vs. homomorphism problems. arXiv:2311.00882.","DOI":"10.1145\/3618260.3649635"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.75"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.03.003"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Victor Dalmau and Jakub Opr\u0161al. 2023. Local consistency as a reduction between constraint satisfaction problems. arXiv:2301.05084.","DOI":"10.1145\/3661814.3662068"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10107-006-0039-7"},{"key":"e_1_3_2_1_35_1","first-page":"1","article-title":"An algebraic approach to the association schemes of coding theory","volume":"10","author":"Delsarte Philippe","year":"1973","unstructured":"Philippe Delsarte. 1973. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10 (1973), 1\u201397. https:\/\/users.wpi.edu\/~martin\/RESEARCH\/philips.pdf","journal-title":"Philips Res. Rep. Suppl."},{"volume-title":"Computational Invariant Theory","author":"Derksen Harm","key":"e_1_3_2_1_36_1","unstructured":"Harm Derksen and Gregor Kemper. 2015. Computational Invariant Theory. Springer."},{"key":"e_1_3_2_1_37_1","volume-title":"Proc. 28th Conference on Learning Theory (COLT\u201915) (JMLR Workshop and Conference Proceedings","volume":"562","author":"Deshpande Yash","year":"2015","unstructured":"Yash Deshpande and Andrea Montanari. 2015. Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems. In Proc. 28th Conference on Learning Theory (COLT\u201915) (JMLR Workshop and Conference Proceedings, Vol. 40). JMLR.org, 523\u2013562. http:\/\/proceedings.mlr.press\/v40\/Deshpande15.html"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","unstructured":"G.F. Frobenius. 1912. \u00dcber Matrizen aus nicht negativen Elementen. K\u00f6nigliche Akademie der Wissenschaften Berlin 456\u2013477. https:\/\/doi.org\/10.3931\/e-rara-18865 10.3931\/e-rara-18865","DOI":"10.3931\/e-rara-18865"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2003.12.011"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a010"},{"key":"e_1_3_2_1_44_1","unstructured":"Chris Godsil. 2010. Association Schemes. https:\/\/www.math.uwaterloo.ca\/~cgodsil\/pdfs\/assoc2.pdf"},{"volume-title":"Erd\u0151s-Ko-Rado Theorems: Algebraic Approaches","author":"Godsil Christopher","key":"e_1_3_2_1_45_1","unstructured":"Christopher Godsil and Karen Meagher. 2016. Erd\u0151s-Ko-Rado Theorems: Algebraic Approaches (Cambridge studies in advanced mathematics). Cambridge University Press."},{"key":"e_1_3_2_1_46_1","volume-title":"Royle","author":"Godsil Chris","year":"2001","unstructured":"Chris Godsil and Gordon F. Royle. 2001. Algebraic Graph Theory. 207, Springer Science & Business Media."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050038"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.62"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_3_2_1_54_1","volume-title":"Johnson","author":"Horn Roger A.","year":"1994","unstructured":"Roger A. Horn and Charles R. Johnson. 1994. Topics in Matrix Analysis. Cambridge University Press."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","unstructured":"Sangxia Huang. 2013. Improved Hardness of Approximating Chromatic Number. In Proc. 16th International Workshop on Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques and the 17th International Workshop on Randomization and Computation (APPROX-RANDOM\u201913). Springer 233\u2013243. isbn:978-3-642-40328-6 https:\/\/doi.org\/10.1007\/978-3-642-40328-6_17 arXiv:1301.5216. 10.1007\/978-3-642-40328-6_17","DOI":"10.1007\/978-3-642-40328-6_17"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015366416311"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321481"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3001582"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959936"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00062"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/17m1152966"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1378223"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400380079"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746600"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.59"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01449896"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander","key":"e_1_3_2_1_80_1","unstructured":"Alexander Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley & Sons."},{"volume-title":"Algorithms in Invariant Theory","author":"Sturmfels Bernd","key":"e_1_3_2_1_81_1","unstructured":"Bernd Sturmfels. 2008. Algorithms in Invariant Theory. Springer Science & Business Media."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079245"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3201777"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"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.3649635","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:47Z","timestamp":1750178207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":85,"alternative-id":["10.1145\/3618260.3649635","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649635","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"}}]}}