{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T13:12:39Z","timestamp":1778764359056,"version":"3.51.4"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T00:00:00Z","timestamp":1778716800000},"content-version":"vor","delay-in-days":2,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2402836"],"award-info":[{"award-number":["CCF-2402836"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2348346"],"award-info":[{"award-number":["CCF-2348346"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,12]]},"abstract":"<jats:p>\n                    We study the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -edge connectivity problem on undirected graphs in the distributed sketching model, where we have\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    nodes and a referee. Each node sends a single message to the referee based on its 1-hop neighborhood in the graph, and the referee must decide whether the graph is\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -edge connected by taking into account the received messages.\n                  <\/jats:p>\n                  <jats:p>\n                    We present the first lower bound for deciding a graph connectivity problem in this model with a deterministic algorithm. Concretely, we show that the worst case message length is \u03a9(\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ) bits for\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -edge connectivity, for any super-constant\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    =\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\u221a\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ). Previously, only a lower bound of \u03a9(log\n                    <jats:sup>3<\/jats:sup>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) bits was known for (1-edge) connectivity, due to Yu (SODA 2021). In fact, our result is the first super-polylogarithmic lower bound for a connectivity decision problem in the distributed graph sketching model.\n                  <\/jats:p>\n                  <jats:p>\n                    To obtain our result, we introduce a new lower bound graph construction, as well as a new communication complexity problem that we call Overlap. As this problem does not appear to be amenable to reductions to existing hard problems such as set disjointness or indexing due to correlations between the inputs of the three players, we leverage results from cross-intersecting set families to prove the hardness of Overlap for deterministic algorithms in the 3-party model with simultaneous messages. Finally, we obtain the sought lower bound for deciding\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -edge connectivity via a novel simulation argument that, in contrast to previous works, does not introduce any probability of error and thus works for deterministic algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3801897","type":"journal-article","created":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:50:22Z","timestamp":1778763022000},"page":"1-21","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Lower Bounds for k-Edge Connectivity in the Distributed Sketching Model"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7442-7002","authenticated-orcid":false,"given":"Peter","family":"Robinson","sequence":"first","affiliation":[{"name":"Augusta University, Augusta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5279-5314","authenticated-orcid":false,"given":"Ming Ming","family":"Tan","sequence":"additional","affiliation":[{"name":"Augusta University, Augusta, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_3_1","unstructured":"Vikrant Ashvinkumar Sepehr Assadi Chengyuan Deng Jie Gao and Chen Wang. 2023. Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. In APPROX\/RANDOM."},{"key":"e_1_2_1_4_1","volume-title":"Lower Bounds for Distributed Sketching. In 11th Workshop on Advances in Distributed Graph Algorithms (ADGA). https:\/\/adga-workshop.org\/2022\/assadi.pdf","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi. 2022. Lower Bounds for Distributed Sketching. In 11th Workshop on Advances in Distributed Graph Algorithms (ADGA). https:\/\/adga-workshop.org\/2022\/assadi.pdf"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405732"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.55"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09620-9_8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745763"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/18.1.369"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00058"},{"key":"e_1_2_1_11_1","volume-title":"Extremal combinatorics: with applications in computer science","author":"Jukna Stasys","unstructured":"Stasys Jukna. 2001. Extremal combinatorics: with applications in computer science. Vol. 29. Springer."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01325-7_24"},{"key":"e_1_2_1_13_1","volume-title":"31st International Symposium on Distributed Computing (DISC","author":"Jurdzinski Tomasz","year":"2017","unstructured":"Tomasz Jurdzinski and Krzysztof Nowicki. 2017. Brief announcement: on connectivity in the broadcast congested clique. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.50"},{"key":"e_1_2_1_15_1","volume-title":"Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. arXiv preprint arXiv:1704.00633","author":"Kapralov Michael","year":"2017","unstructured":"Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P Woodruff, and Mobin Yahyazadeh. 2017b. Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. arXiv preprint arXiv:1704.00633 (2017)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206317"},{"key":"e_1_2_1_17_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_2_1_18_1","volume-title":"Department of Applied Mathematics","author":"Matou\u0161ek Ji\u0159\u00ed","year":"2001","unstructured":"Ji\u0159\u00ed Matou\u0161ek and Jan Vondr\u00e1k. 2001. The probabilistic method. Lecture Notes, Department of Applied Mathematics, Charles University, Prague (2001)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933066"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.111"},{"key":"e_1_2_1_22_1","volume-title":"Connectivity Lower Bounds in Broadcast Congested Clique. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS","author":"Pai Shreyas","year":"2020","unstructured":"Shreyas Pai and Sriram V Pemmaraju. 2020. Connectivity Lower Bounds in Broadcast Congested Clique. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_23_1","volume-title":"Information and information stability of random variables and processes. Holden-Day","author":"Pinsker Mark S","year":"1964","unstructured":"Mark S Pinsker. 1964. Information and information stability of random variables and processes. Holden-Day (1964)."},{"key":"e_1_2_1_24_1","first-page":"32","volume-title":"37th International Symposium on Distributed Computing (DISC","author":"Robinson Peter","year":"2023","unstructured":"Peter Robinson. 2023. Distributed Sketching Lower Bounds for k-Edge Connected Spanning Subgraphs, BFS Trees, and LCL Problems. In 37th International Symposium on Distributed Computing (DISC 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 32-1."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2510.16336"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.111"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801897","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:51:17Z","timestamp":1778763077000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3801897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,12]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,12]]}},"alternative-id":["10.1145\/3801897"],"URL":"https:\/\/doi.org\/10.1145\/3801897","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,12]]}}}