{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:22:42Z","timestamp":1772083362039,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":71,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"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":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585112","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"623-631","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Approximate Graph Colouring and the Hollow Shadow"],"prefix":"10.1145","author":[{"given":"Lorenzo","family":"Ciardo","sequence":"first","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1982-029-3"},{"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.4230\/LIPIcs.MFCS.2021.11"},{"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","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exu070"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2021.10"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.50"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.21"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451003"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520028"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.14"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.28"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M128212X"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.37"},{"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.1145\/3470867"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746550"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00030"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.27"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(03)00429-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4543-4_6"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2021.27"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2016.08.020"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90015-M"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Lorenzo Ciardo and Stanislav \u017divn\u00fd. 2022. Approximate Graph Colouring and the Hollow Shadow. arXiv:2211.03168. \t\t\t\t  Lorenzo Ciardo and Stanislav \u017divn\u00fd. 2022. Approximate Graph Colouring and the Hollow Shadow. arXiv:2211.03168.","DOI":"10.1145\/3564246.3585112"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch86"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1476435"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch25"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.75"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2008.05.019"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188806"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188804"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.831"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"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","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.62"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90057-3"},{"key":"e_1_3_2_1_47_1","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and homomorphisms (Oxford Lecture Series in Mathematics and its Applications Vol. 28). OUP Oxford. \t\t\t\t  Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and homomorphisms (Oxford Lecture Series in Mathematics and its Applications Vol. 28). OUP Oxford."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_17"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00071-9"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3001582"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959936"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055432"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00062"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055438"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3559736.3559740"},{"key":"e_1_3_2_1_59_1","series-title":"SIAM J. Comput., arXiv:2003.11351","volume-title":"Topology and adjunction in promise constraint satisfaction","author":"Krokhin Andrei A.","unstructured":"Andrei A. Krokhin , Jakub Opr\u0161al , Marcin Wrochna , and Stanislav \u017divn\u00fd . 2022. Topology and adjunction in promise constraint satisfaction . SIAM J. Comput., arXiv:2003.11351 . Andrei A. Krokhin, Jakub Opr\u0161al, Marcin Wrochna, and Stanislav \u017divn\u00fd. 2022. Topology and adjunction in promise constraint satisfaction. SIAM J. Comput., arXiv:2003.11351."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400380079"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.128"},{"key":"e_1_3_2_1_64_1","volume-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization","author":"Parrilo Pablo A","unstructured":"Pablo A Parrilo . 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization . California Institute of Technology . http:\/\/www.cds.caltech.edu\/~doyle\/hot\/thesis.pdf Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology. http:\/\/www.cds.caltech.edu\/~doyle\/hot\/thesis.pdf"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_66_1","volume-title":"Theory of linear and integer programming","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 1986. Theory of linear and integer programming . John Wiley & Sons, Ltd., Chichester. isbn:0-471-90854-1 A Wiley-Interscience Publication Alexander Schrijver. 1986. Theory of linear and integer programming. John Wiley & Sons, Ltd., Chichester. isbn:0-471-90854-1 A Wiley-Interscience Publication"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070233"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.2158"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585112","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":71,"alternative-id":["10.1145\/3564246.3585112","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585112","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}