{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:18Z","timestamp":1750220178895,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["820148"],"award-info":[{"award-number":["820148"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533348","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Choiceless Polynomial Time with Witnessed Symmetric Choice"],"prefix":"10.1145","author":[{"given":"Moritz","family":"Lichter","sequence":"first","affiliation":[{"name":"TU Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"TU Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00005-6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1190150152"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"volume-title":"Lectures on coherent configurations","author":"Chen Gang","key":"e_1_3_2_1_5_1","unstructured":"Gang Chen and Ilia Ponomarenko . 2019. Lectures on coherent configurations . Central China Normal University Press , Wuhan . A draft is available at www.pdmi.ras.ru\/~inp\/ccNOTES.pdf. Gang Chen and Ilia Ponomarenko. 2019. Lectures on coherent configurations. Central China Normal University Press, Wuhan. A draft is available at www.pdmi.ras.ru\/~inp\/ccNOTES.pdf."},{"key":"e_1_3_2_1_6_1","unstructured":"Anuj Dawar Erich Gr\u00e4del and Moritz Lichter. 2021. Limitations of the Invertible-Map Equivalences. CoRR abs\/2109.07218(2021). arXiv:2109.07218https:\/\/arxiv.org\/abs\/2109.07218  Anuj Dawar Erich Gr\u00e4del and Moritz Lichter. 2021. Limitations of the Invertible-Map Equivalences. CoRR abs\/2109.07218(2021). arXiv:2109.07218https:\/\/arxiv.org\/abs\/2109.07218"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45220-1_16"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.4.503"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2007.11.011"},{"key":"e_1_3_2_1_10_1","volume-title":"Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math.","author":"Fagin Ronald","year":"1973","unstructured":"Ronald Fagin . 1974. Generalized first-order spectra and polynomial-time recognizable sets . In Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math. , New York, 1973 ). 43\u201373. SIAM\u2013AMS Proc ., Vol. VII . Ronald Fagin. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1973). 43\u201373. SIAM\u2013AMS Proc., Vol. VII."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2712"},{"volume-title":"Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday(Lecture Notes in Computer Science, Vol.\u00a09300), Lev\u00a0D","author":"Gr\u00e4del Erich","key":"e_1_3_2_1_12_1","unstructured":"Erich Gr\u00e4del and Martin Grohe . 2015. Is Polynomial Time Choiceless? . In Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday(Lecture Notes in Computer Science, Vol.\u00a09300), Lev\u00a0D . Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, and Wolfram Schulte (Eds.). Springer , 193\u2013209. https:\/\/doi.org\/10.1007\/978-3-319-23534-9_11 10.1007\/978-3-319-23534-9_11 Erich Gr\u00e4del and Martin Grohe. 2015. Is Polynomial Time Choiceless?. In Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday(Lecture Notes in Computer Science, Vol.\u00a09300), Lev\u00a0D. Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, and Wolfram Schulte (Eds.). Springer, 193\u2013209. https:\/\/doi.org\/10.1007\/978-3-319-23534-9_11"},{"key":"e_1_3_2_1_13_1","volume-title":"Characterising Choiceless Polynomial Time with First-Order Interpretations. In 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015","author":"Gr\u00e4del Erich","year":"2015","unstructured":"Erich Gr\u00e4del , Wied Pakusa , Svenja Schalth\u00f6fer , and Lukasz Kaiser . 2015 . Characterising Choiceless Polynomial Time with First-Order Interpretations. In 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015 , Kyoto, Japan , July 6-10, 2015. IEEE Computer Society, 677\u2013688. https:\/\/doi.org\/10.1109\/LICS.2015.68 10.1109\/LICS.2015.68 Erich Gr\u00e4del, Wied Pakusa, Svenja Schalth\u00f6fer, and Lukasz Kaiser. 2015. Characterising Choiceless Polynomial Time with First-Order Interpretations. In 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015. IEEE Computer Society, 677\u2013688. https:\/\/doi.org\/10.1109\/LICS.2015.68"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.11"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Martin Grohe. 2017. Descriptive Complexity Canonization and Definable Graph Structure Theory. Cambridge University Press.  Martin Grohe. 2017. Descriptive Complexity Canonization and Definable Graph Structure Theory. Cambridge University Press.","DOI":"10.1017\/9781139028868"},{"key":"e_1_3_2_1_16_1","volume-title":"Canonisation and Definability for Graphs of Bounded Rank Width. In 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2019","author":"Grohe Martin","year":"2019","unstructured":"Martin Grohe and Daniel Neuen . 2019 . Canonisation and Definability for Graphs of Bounded Rank Width. In 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2019 , Vancouver, BC, Canada , June 24-27, 2019. IEEE, 1\u201313. https:\/\/doi.org\/10.1109\/LICS.2019.8785682 10.1109\/LICS.2019.8785682 Martin Grohe and Daniel Neuen. 2019. Canonisation and Definability for Graphs of Bounded Rank Width. In 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019. IEEE, 1\u201313. https:\/\/doi.org\/10.1109\/LICS.2019.8785682"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.154"},{"volume-title":"Current Trends in Theoretical Computer Science","author":"Gurevich Yuri","key":"e_1_3_2_1_18_1","unstructured":"Yuri Gurevich . 1988. Logic and the Challenge of Computer Science . In Current Trends in Theoretical Computer Science , Egon Boerger (Ed.). Computer Science Press , 1\u201357. Yuri Gurevich. 1988. Logic and the Challenge of Computer Science. In Current Trends in Theoretical Computer Science, Egon Boerger (Ed.). Computer Science Press, 1\u201357."},{"key":"e_1_3_2_1_19_1","unstructured":"Yuri Gurevich. 1997. From Invariants to Canonization. Bull. EATCS 63(1997).  Yuri Gurevich. 1997. From Invariants to Canonization. Bull. EATCS 63(1997)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"e_1_3_2_1_21_1","volume-title":"MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I(Lecture Notes in Computer Science, Vol.\u00a09234)","author":"Kiefer Sandra","year":"2015","unstructured":"Sandra Kiefer , Pascal Schweitzer , and Erkal Selman . 2015 . Graphs Identified by Logics with Counting. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium , MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I(Lecture Notes in Computer Science, Vol.\u00a09234) , Giuseppe\u00a0F. Italiano, Giovanni Pighizzini, and Donald Sannella (Eds.). Springer, 319\u2013330. https:\/\/doi.org\/10.1007\/978-3-662-48057-1_25 10.1007\/978-3-662-48057-1_25 Sandra Kiefer, Pascal Schweitzer, and Erkal Selman. 2015. Graphs Identified by Logics with Counting. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I(Lecture Notes in Computer Science, Vol.\u00a09234), Giuseppe\u00a0F. Italiano, Giovanni Pighizzini, and Donald Sannella (Eds.). Springer, 319\u2013330. https:\/\/doi.org\/10.1007\/978-3-662-48057-1_25"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470598"},{"key":"e_1_3_2_1_23_1","volume-title":"29th EACSL Annual Conference on Computer Science Logic, CSL","author":"Lichter Moritz","year":"2021","unstructured":"Moritz Lichter and Pascal Schweitzer . 2021. Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time . In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021 , January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference)(LIPIcs, Vol.\u00a0183), Christel Baier and Jean Goubault-Larrecq (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 31:1\u201331:18. https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2021.31 10.4230\/LIPIcs.CSL.2021.31 Moritz Lichter and Pascal Schweitzer. 2021. Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time. In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference)(LIPIcs, Vol.\u00a0183), Christel Baier and Jean Goubault-Larrecq (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 31:1\u201331:18. https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2021.31"},{"key":"e_1_3_2_1_24_1","unstructured":"Moritz Lichter and Pascal Schweitzer. 2022. Choiceless Polynomial Time with Witnessed Symmetric Choice. CoRR abs\/2205.14003(2022). arXiv:2205.14003https:\/\/arxiv.org\/abs\/2205.14003  Moritz Lichter and Pascal Schweitzer. 2022. Choiceless Polynomial Time with Witnessed Symmetric Choice. CoRR abs\/2205.14003(2022). arXiv:2205.14003https:\/\/arxiv.org\/abs\/2205.14003"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90004-8"},{"key":"e_1_3_2_1_26_1","volume-title":"29th EACSL Annual Conference on Computer Science Logic, CSL","author":"Pago Benedikt","year":"2021","unstructured":"Benedikt Pago . 2021. Choiceless Computation and Symmetry: Limitations of Definability . In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021 , January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference)(LIPIcs, Vol.\u00a0183), Christel Baier and Jean Goubault-Larrecq (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 33:1\u201333:21. https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2021.33 10.4230\/LIPIcs.CSL.2021.33 Benedikt Pago. 2021. Choiceless Computation and Symmetry: Limitations of Definability. In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference)(LIPIcs, Vol.\u00a0183), Christel Baier and Jean Goubault-Larrecq (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 33:1\u201333:21. https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2021.33"},{"key":"e_1_3_2_1_27_1","unstructured":"Wied Pakusa. 2015. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. Ph.\u00a0D. Dissertation. RWTH Aachen.  Wied Pakusa. 2015. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. Ph.\u00a0D. Dissertation. RWTH Aachen."},{"key":"e_1_3_2_1_28_1","volume-title":"Definability of Cai-F\u00fcrer-Immerman Problems in Choiceless Polynomial Time. In 25th EACSL Annual Conference on Computer Science Logic, CSL 2016","author":"Pakusa Wied","year":"2016","unstructured":"Wied Pakusa , Svenja Schalth\u00f6fer , and Erkal Selman . 2016 . Definability of Cai-F\u00fcrer-Immerman Problems in Choiceless Polynomial Time. In 25th EACSL Annual Conference on Computer Science Logic, CSL 2016 , August 29 - September 1, 2016, Marseille, France(LIPIcs, Vol.\u00a062), Jean-Marc Talbot and Laurent Regnier (Eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 19:1\u201319:17. https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2016.19 10.4230\/LIPIcs.CSL.2016.19 Wied Pakusa, Svenja Schalth\u00f6fer, and Erkal Selman. 2016. Definability of Cai-F\u00fcrer-Immerman Problems in Choiceless Polynomial Time. In 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France(LIPIcs, Vol.\u00a062), Jean-Marc Talbot and Laurent Regnier (Eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 19:1\u201319:17. https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2016.19"},{"volume-title":"Fields of Logic and Computation, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday(Lecture Notes in Computer Science, Vol.\u00a06300)","author":"Rossman Benjamin","key":"e_1_3_2_1_29_1","unstructured":"Benjamin Rossman . 2010. Choiceless Computation and Symmetry . In Fields of Logic and Computation, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday(Lecture Notes in Computer Science, Vol.\u00a06300) , Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig (Eds.). Springer , 565\u2013580. https:\/\/doi.org\/10.1007\/978-3-642-15025-8_28 10.1007\/978-3-642-15025-8_28 Benjamin Rossman. 2010. Choiceless Computation and Symmetry. In Fields of Logic and Computation, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday(Lecture Notes in Computer Science, Vol.\u00a06300), Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig (Eds.). Springer, 565\u2013580. https:\/\/doi.org\/10.1007\/978-3-642-15025-8_28"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316338"},{"key":"e_1_3_2_1_31_1","volume-title":"MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I(Lecture Notes in Computer Science, Vol.\u00a08634)","author":"Zaid Faried\u00a0Abu","year":"2014","unstructured":"Faried\u00a0Abu Zaid , Erich Gr\u00e4del , Martin Grohe , and Wied Pakusa . 2014 . Choiceless Polynomial Time on Structures with Small Abelian Colour Classes. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium , MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I(Lecture Notes in Computer Science, Vol.\u00a08634) , Erzs\u00e9bet Csuhaj-Varj\u00fa, Martin Dietzfelbinger, and Zolt\u00e1n \u00c9sik (Eds.). Springer, 50\u201362. https:\/\/doi.org\/10.1007\/978-3-662-44522-8_5 10.1007\/978-3-662-44522-8_5 Faried\u00a0Abu Zaid, Erich Gr\u00e4del, Martin Grohe, and Wied Pakusa. 2014. Choiceless Polynomial Time on Structures with Small Abelian Colour Classes. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I(Lecture Notes in Computer Science, Vol.\u00a08634), Erzs\u00e9bet Csuhaj-Varj\u00fa, Martin Dietzfelbinger, and Zolt\u00e1n \u00c9sik (Eds.). Springer, 50\u201362. https:\/\/doi.org\/10.1007\/978-3-662-44522-8_5"}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"],"location":"Haifa Israel","acronym":"LICS '22"},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533348","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:09Z","timestamp":1750186929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":31,"alternative-id":["10.1145\/3531130.3533348","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533348","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}