{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:26Z","timestamp":1781031446758,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":34,"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":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["948057"],"award-info":[{"award-number":["948057"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2022\/47\/D\/ST6\/03421"],"award-info":[{"award-number":["2022\/47\/D\/ST6\/03421"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800829","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1180-1191","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Reversal of Transductions of Sparse Graph Classes"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2662-5303","authenticated-orcid":false,"given":"Jan","family":"Dreier","sequence":"first","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4761-3432","authenticated-orcid":false,"given":"Jakub","family":"Gajarsk\u00fd","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"},{"name":"Masaryk University, Faculty of Informatics, Brno, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7891-1988","authenticated-orcid":false,"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"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.48550\/ARXIV.2504.08266"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-00965-5"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.EJC.2025.104130"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2506.08926"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(2:14)2023"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00012"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533349"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2601.14906"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585186"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.125"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718259"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.10.004"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SWAT.2022.22"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3383206"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382093"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.128"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2024.137"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533356"},{"key":"e_1_3_2_1_20_1","volume-title":"Makowsky (Eds.) (Contemporary Mathematics","volume":"206","author":"Grohe Martin","year":"2011","unstructured":"Martin Grohe and Stephan Kreutzer. 2011. Methods for Algorithmic Meta Theorems. In Model Theoretic Methods in Finite Combinatorics, M. Grohe and J.A. Makowsky (Eds.) (Contemporary Mathematics, Vol. 558). American Mathematical Society, 181\u2013206."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1168753"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90052-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-16(1:25)2020"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00023-9"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.EJC.2006.07.013"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity \u2014 Graphs Structures and Algorithms (Algorithms and combinatorics Vol. 28). Springer. https:\/\/doi.org\/10.1007\/978-3-642-27875-4 10.1007\/978-3-642-27875-4","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.120"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.EJC.2020.103223"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2501.04166"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209178"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209136"},{"key":"e_1_3_2_1_32_1","volume-title":"\u201cSparsity","author":"Pilipczuk Marcin","unstructured":"Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Sebastian Siebertz. Winter semesters 2017\/18 and 2019\/20. Lecture notes for the course \u201cSparsity\u201d given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw. Available online at https:\/\/www.mimuw.edu.pl\/ mp248287\/sparsity2"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS56636.2023.10175719"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387660"}],"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.3800829","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:03:13Z","timestamp":1781028193000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800829"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":34,"alternative-id":["10.1145\/3798129.3800829","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800829","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"}}]}}