{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T21:19:06Z","timestamp":1718918346679},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,11,26]],"date-time":"2021-11-26T00:00:00Z","timestamp":1637884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,26]],"date-time":"2021-11-26T00:00:00Z","timestamp":1637884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00446-021-00409-3","type":"journal-article","created":{"date-parts":[[2021,11,26]],"date-time":"2021-11-26T06:01:22Z","timestamp":1637906482000},"page":"207-234","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Sublinear-time distributed algorithms for detecting small cliques and even cycles"],"prefix":"10.1007","volume":"35","author":[{"given":"Talya","family":"Eden","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nimrod","family":"Fiat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Orr","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,26]]},"reference":[{"key":"409_CR1","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed graph coloring: fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2013)","DOI":"10.2200\/S00520ED1V01Y201307DCT011"},{"issue":"2","key":"409_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"JA Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. J. Combin. Theory Ser. B 16(2), 97\u2013105 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"409_CR3","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00446-011-0132-x","volume":"24","author":"Z Brakerski","year":"2011","unstructured":"Brakerski, Z., Patt-Shamir, B.: Distributed discovery of large near-cliques. Distrib. Comput. 24(2), 79\u201389 (2011)","journal-title":"Distrib. Comput."},{"issue":"1","key":"409_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548316000134","volume":"26","author":"B Bukh","year":"2017","unstructured":"Bukh, B., Jiang, Z.: A bound on the number of edges in graphs without an even cycle. Combin. Probab. Comput. 26(1), 1\u201315 (2017)","journal-title":"Combin. Probab. Comput."},{"key":"409_CR5","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Fischer, E., Schwartzman, G., Vasudev, Y.: Fast distributed algorithms for testing graph properties. In: Distributed Computing: 30th International Symposium, DISC 2016. Proceedings, pp. 43\u201356 (2016)","DOI":"10.1007\/978-3-662-53426-7_4"},{"key":"409_CR6","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pages 143\u2013152 (2015)","DOI":"10.1145\/2767386.2767414"},{"key":"409_CR7","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Pettie, S., Zhang, H.: Distributed triangle detection via expander decomposition. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 821\u2013840 (2019)","DOI":"10.1137\/1.9781611975482.51"},{"key":"409_CR8","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Saranurak, T.: Improved distributed expander decomposition and nearly optimal triangle enumeration. CoRR, abs\/1904.08037, 2019. arXiv:1904.08037","DOI":"10.1145\/3293611.3331618"},{"issue":"1","key":"409_CR9","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"409_CR10","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost tight bounds for rumour spreading with conductance. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM symposium on theory of computing STOC, pp. 399\u2013408. ACM (2010)","DOI":"10.1145\/1806689.1806745"},{"key":"409_CR11","unstructured":"Czumaj, A., Konrad, C.: Detecting cliques in CONGEST networks. In: 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15\u201319, 2018, pp. 16:1\u201316:15 (2018)"},{"key":"409_CR12","doi-asserted-by":"crossref","unstructured":"Daga, M., Henzinger, M., Nanongkai, D., Saranurak, T.: Distributed edge connectivity in sublinear time. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 343\u2013354 (2019)","DOI":"10.1145\/3313276.3316346"},{"key":"409_CR13","doi-asserted-by":"crossref","unstructured":"Dolev, D., Lenzen, C., Peled, S.: \u201ctri, tri again\u201d: Finding triangles and small subgraphs in a distributed setting. In: Distributed Computing: 26th International Symposium, DISC 2012. Proceedings, pp. 195\u2013209 (2012)","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"409_CR14","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC \u201914, pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"key":"409_CR15","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: Distributed strong diameter network decomposition. In: Proceedings of the 35th ACM Symposium on Principles of Distributed Computing (PODC), pp. 211\u2013216 (2016)","DOI":"10.1145\/2933057.2933094"},{"key":"409_CR16","unstructured":"Even, G., Fischer, O., Fraigniaud, P., Gonen, T., Levi, R., Medina, M., Montealegre, P., Olivetti, D., Oshman, R., Rapaport, I., Todinca, I.: Three notes on distributed property testing. In: 31st International Symposium on Distributed Computing (DISC 2017), vol. 91 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 15:1\u201315:30 (2017)"},{"key":"409_CR17","doi-asserted-by":"crossref","unstructured":"Fischer, O., Gonen, T., Kuhn, F., Oshman, R.: Possibilities and impossibilities for distributed subgraph detection. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018, pp. 153\u2013162 (2018)","DOI":"10.1145\/3210377.3210401"},{"key":"409_CR18","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Olivetti, D.: Distributed detection of cycles. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington DC, USA, July 24\u201326, 2017, pp. 153\u2013162 (2017)","DOI":"10.1145\/3087556.3087571"},{"key":"409_CR19","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Rapaport, I., Salo, V., Todinca, I.: Distributed testing of excluded subgraphs. In: Distributed Computing: 30th International Symposium, DISC 2016. Proceedings, pp. 342\u2013356 (2016)","DOI":"10.1007\/978-3-662-53426-7_25"},{"key":"409_CR20","doi-asserted-by":"crossref","unstructured":"F\u00fcredi, Z., Simonovits, M.: The history of degenerate (bipartite) extremal graph problems. In: Lov\u00e1sz, L., Ruzsa, I.Z., S\u00f3s, V.T. (eds.) Erd\u0151s Centennial, pp. 169\u2013264. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-39286-3_7"},{"key":"409_CR21","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: Near-optimal scheduling of distributed algorithms. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pp. 3\u201312 (2015)","DOI":"10.1145\/2767386.2767417"},{"key":"409_CR22","unstructured":"Ghaffari, M., Kuhn, F.: Derandomizing distributed algorithms with small messages: Spanners and dominating set. In: 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pp. 29:1\u201329:17 (2018)"},{"key":"409_CR23","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Su, H.-H.: Distributed MST and routing in almost mixing time. In: Proceedings of the ACM symposium on principles of distributed computing, PODC 2017, Washington, DC, USA, July 25\u201327, 2017, pp. 131\u2013140 (2017)","DOI":"10.1145\/3087801.3087827"},{"key":"409_CR24","unstructured":"Ghaffari, M., Li, J.: New distributed algorithms in almost mixing time via transformations from parallel algorithms. In: 32nd International Symposium on Distributed Computing (DISC), pp. 31:1\u201331:16 (2018)"},{"key":"409_CR25","unstructured":"Golovnev, A., Kulikov, A.S., Ryan W.R.: Circuit depth reductions. In: Lee, J.R. (ed.) 12th Innovations in Theoretical Computer Science Conference, ITCS, volume 185 of LIPIcs, pp. 24:1\u201324:20. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"409_CR26","unstructured":"Gonen, T., Oshman, R.: Lower bounds for subgraph detection in the congest model. To appear in OPODIS 2017 (2017)"},{"key":"409_CR27","doi-asserted-by":"crossref","unstructured":"Izumi, T., Le Gall, F.: Triangle finding and listing in congest networks. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC \u201917, pp. 381\u2013389 (2017)","DOI":"10.1145\/3087801.3087811"},{"key":"409_CR28","doi-asserted-by":"crossref","unstructured":"Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM J. Comput. 18(6), 1149\u20131178 (1989)","DOI":"10.1137\/0218077"},{"key":"409_CR29","unstructured":"Korhonen, J.H., Rybicki, J.: Deterministic subgraph detection in broadcast CONGEST. In: 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017, pp. 4:1\u20134:16 (2017)"},{"key":"409_CR30","unstructured":"Malpani, A., Agrawal, D.: Efficient information dissemination in computer networks. In: Proceedings of the 14th Conference on Local Computer Networks, LCN 1989, 1989, Minneapolis, Minnesota, USA, pp. 202\u2013211 (1989)"},{"key":"409_CR31","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Peng, R., Xu, S.C.: Parallel graph decompositions using random shifts. In: Proceedings of the 5th Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 196\u2013203 (2013)","DOI":"10.1145\/2486159.2486180"},{"key":"409_CR32","doi-asserted-by":"crossref","unstructured":"Naor, A., Verstra\u00ebte, J.: A note on bipartite graphs without 2k-cycles. Comb. Probab. Comput. 14(5\u20136), 845\u2013849 (2005)","DOI":"10.1017\/S0963548305007029"},{"issue":"1","key":"409_CR33","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"1","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 1(1), 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"key":"409_CR34","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: On the distributed complexity of large-scale graph computations. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16\u201318, 2018, pp. 405\u2013414 (2018)","DOI":"10.1145\/3210377.3210409"},{"issue":"2","key":"409_CR35","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"AA Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"409_CR36","doi-asserted-by":"crossref","unstructured":"Rozhon, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: Konstantin, M., Yury, M., Madhur, T., Gautam, K., Julia, C. (eds.) Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 350\u2013363. ACM (2020)","DOI":"10.1145\/3357713.3384298"},{"issue":"5","key":"409_CR37","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"AD Sarma","year":"2012","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"key":"409_CR38","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-hoeffding bounds for applications with limited independence. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201993, pp. 331\u2013340 (1993)"},{"issue":"4","key":"409_CR39","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.socnet.2010.06.001","volume":"32","author":"M Szell","year":"2010","unstructured":"Szell, M., Thurner, S.: Measuring social dynamics in a massive multiplayer online game. Soc. Netw. 32(4), 313\u2013329 (2010)","journal-title":"Soc. Netw."},{"key":"409_CR40","doi-asserted-by":"crossref","unstructured":"Verstra\u00ebte, J.: Extremal problems for cycles in graphs. In: Recent Trends in Combinatorics, pp. 83\u2013116. Springer (2016)","DOI":"10.1007\/978-3-319-24298-9_4"},{"key":"409_CR41","doi-asserted-by":"crossref","unstructured":"Wasserman, S., Faust, K.: Social network analysis: methods and applications. Structural Analysis in the Social Sciences. Cambridge University Press, (1994)","DOI":"10.1017\/CBO9780511815478"},{"key":"409_CR42","doi-asserted-by":"crossref","unstructured":"Watts, D.J.: Collective dynamics of \u2019small-world\u2019 networks. Nature 393, 440 (1998)","DOI":"10.1038\/30918"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00409-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00409-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00409-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T06:08:41Z","timestamp":1652854121000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00409-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,26]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["409"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00409-3","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,26]]},"assertion":[{"value":"5 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}