{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T00:54:34Z","timestamp":1783040074071,"version":"3.54.6"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,17]]},"DOI":"10.1145\/3662158.3662767","type":"proceedings-article","created":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T14:38:06Z","timestamp":1717598286000},"page":"209-219","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Even-Cycle Detection in the Randomized and Quantum CONGEST Model"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4534-4803","authenticated-orcid":false,"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Cit\u00e9, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-1483-4796","authenticated-orcid":false,"given":"Ma\u00ebl","family":"Luce","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Cit\u00e9, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2384-9026","authenticated-orcid":false,"given":"Frederic","family":"Magniez","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Cit\u00e9, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3466-859X","authenticated-orcid":false,"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[{"name":"Universit\u00e9 d'Orl\u00e9ans, Orl\u00e9ans, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Encyclopedia of Algorithms. 335--338.","author":"Alon Noga","unstructured":"Noga Alon, Raphael Yuster, and Uri Zwick. 2016. Color Coding. In Encyclopedia of Algorithms. 335--338."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/992287.992296"},{"key":"e_1_3_2_1_3_1","volume-title":"48th Int. Coll. on Automata, Languages, and Programming (ICALP) (LIPIcs","author":"Censor-Hillel Keren","unstructured":"Keren Censor-Hillel. 2021. Distributed Subgraph Finding: Progress and Challenges. In 48th Int. Coll. on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 3:1--3:14."},{"key":"e_1_3_2_1_4_1","unstructured":"Keren Censor-Hillel. 2022. Distributed Subgraph Finding: Progress and Challenges. arXiv:2203.06597 [cs.DS]"},{"key":"e_1_3_2_1_5_1","volume-title":"Tight Distributed Listing of Cliques. In 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 2878--2891","author":"Censor-Hillel Keren","year":"2021","unstructured":"Keren Censor-Hillel, Yi-Jun Chang, Fran\u00e7ois Le Gall, and Dean Leitersdorf. 2021. Tight Distributed Listing of Cliques. In 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 2878--2891."},{"key":"e_1_3_2_1_6_1","volume-title":"Quantum Distributed Algorithms for Detection of Cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS) (LIPIcs","volume":"25","author":"Censor-Hillel Keren","year":"2022","unstructured":"Keren Censor-Hillel, Orr Fischer, Fran\u00e7ois Le Gall, Dean Leitersdorf, and Rotem Oshman. 2022. Quantum Distributed Algorithms for Detection of Cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS) (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 35:1--35:25."},{"key":"e_1_3_2_1_7_1","volume-title":"Dean Leitersdorf, and Rotem Oshman.","author":"Censor-Hillel Keren","year":"2023","unstructured":"Keren Censor-Hillel, Orr Fischer, Fran\u00e7ois Le Gall, Dean Leitersdorf, and Rotem Oshman. 2023. Private communication."},{"key":"e_1_3_2_1_8_1","volume-title":"Cycles and Small Subgraphs. In 34th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"17","author":"Censor-Hillel Keren","year":"2020","unstructured":"Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, Fran\u00e7ois Le Gall, Dean Leitersdorf, and Rotem Oshman. 2020. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In 34th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 179). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 33:1--33:17."},{"key":"e_1_3_2_1_9_1","volume-title":"Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration. In 38th ACM Symposium on Principles of Distributed Computing (PODC). ACM, 66--73","author":"Chang Yi-Jun","year":"2019","unstructured":"Yi-Jun Chang and Thatchaphol Saranurak. 2019. Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration. In 38th ACM Symposium on Principles of Distributed Computing (PODC). ACM, 66--73."},{"key":"e_1_3_2_1_10_1","volume-title":"Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela.","author":"Coiteux-Roy Xavier","year":"2024","unstructured":"Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, Fran\u00e7ois Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela. 2024. No distributed quantum advantage for approximate graph coloring. arXiv:2307.09444 [cs.DS]"},{"key":"e_1_3_2_1_11_1","volume-title":"Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"15","author":"Czumaj Artur","year":"2018","unstructured":"Artur Czumaj and Christian Konrad. 2018. Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 121). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 16:1--16:15."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_14_1","volume-title":"Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In 33rd International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"16","author":"Eden Talya","year":"2019","unstructured":"Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. 2019. Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In 33rd International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 146). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1--15:16."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-021-00409-3"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611488"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Paul Erd\u00f6s Andr\u00e1s Hajnal and J. W. Moon. 1964. A problem in graph theory. The American Mathematical Monthly 71(10) (1964) 1107--1110.","DOI":"10.2307\/2311408"},{"key":"e_1_3_2_1_18_1","volume-title":"Three Notes on Distributed Property Testing. In 31st Int. Symp. on Distributed Computing (DISC) (LIPIcs","volume":"30","author":"Even Guy","year":"2017","unstructured":"Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. 2017. Three Notes on Distributed Property Testing. In 31st Int. Symp. on Distributed Computing (DISC) (LIPIcs, Vol. 91). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1--15:30."},{"key":"e_1_3_2_1_19_1","volume-title":"Possibilities and Impossibilities for Distributed Subgraph Detection. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 153--162","author":"Fischer Orr","year":"2018","unstructured":"Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. 2018. Possibilities and Impossibilities for Distributed Subgraph Detection. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 153--162."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32733-9_20"},{"key":"e_1_3_2_1_22_1","unstructured":"Pierre Fraigniaud Pedro Montealegre Dennis Olivetti Ivan Rapaport and Ioan Todinca. 2017. Distributed Subgraph Detection. arXiv:1706.03996 [cs.DC]"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322811"},{"key":"e_1_3_2_1_24_1","volume-title":"Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. In 39th ACM Symposium on Principles of Distributed Computing (PODC). 337--346","author":"Gall Fran\u00e7ois Le","year":"2018","unstructured":"Fran\u00e7ois Le Gall and Fr\u00e9d\u00e9ric Magniez. 2018. Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. In 39th ACM Symposium on Principles of Distributed Computing (PODC). 337--346."},{"key":"e_1_3_2_1_25_1","volume-title":"23rd International Symposium (DISC). 243--257","author":"Gavoille Cyril","year":"2009","unstructured":"Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. 2009. What Can Be Observed Locally?. In Distributed Computing, 23rd International Symposium (DISC). 243--257."},{"key":"e_1_3_2_1_26_1","volume-title":"Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model. In 40th ACM Symposium on Principles of Distributed Computing (PODC). 84--93","author":"Izumi Taisuke","year":"2019","unstructured":"Taisuke Izumi and Fran\u00e7ois Le Gall. 2019. Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model. In 40th ACM Symposium on Principles of Distributed Computing (PODC). 84--93."},{"key":"e_1_3_2_1_27_1","first-page":"1","article-title":"Deterministic Subgraph Detection in Broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs, Vol. 95)","volume":"4","author":"Korhonen Janne H.","year":"2017","unstructured":"Janne H. Korhonen and Joel Rybicki. 2017. Deterministic Subgraph Detection in Broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs, Vol. 95). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 4:1--4:16.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_28_1","volume-title":"36 Int. Symp. on Theoretical Aspects of Computer Science (STACS). 49:1--49:14","author":"Gall Fran\u00e7ois Le","year":"2019","unstructured":"Fran\u00e7ois Le Gall, Harumichi Nishimura, and Ansis Rosmanis. 2019. Quantum advantage for the LOCAL model in distributed computing. In 36 Int. Symp. on Theoretical Aspects of Computer Science (STACS). 49:1--49:14."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538413"}],"event":{"name":"PODC '24: 43rd ACM Symposium on Principles of Distributed Computing","location":"Nantes France","acronym":"PODC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"]},"container-title":["Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662158.3662767","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:43:41Z","timestamp":1750290221000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662158.3662767"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":29,"alternative-id":["10.1145\/3662158.3662767","10.1145\/3662158"],"URL":"https:\/\/doi.org\/10.1145\/3662158.3662767","relation":{},"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2024-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}