{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005390,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":83,"publisher":"ACM","funder":[{"name":"European Research Council","award":["59557?ALGOCom, CODY 101039914"],"award-info":[{"award-number":["59557?ALGOCom, CODY 101039914"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718316","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"2305-2316","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0874-2356","authenticated-orcid":false,"given":"Joakim","family":"Blikstad","sequence":"first","affiliation":[{"name":"CWI, Amsterdam, Netherlands"},{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8485-6676","authenticated-orcid":false,"given":"Yonggang","family":"Jiang","sequence":"additional","affiliation":[{"name":"MPI-INF, Saarbr\u00fccken, Germany"},{"name":"Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3722-4679","authenticated-orcid":false,"given":"Sagnik","family":"Mukhopadhyay","sequence":"additional","affiliation":[{"name":"University of Birmingham, Birmingham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7169-0163","authenticated-orcid":false,"given":"Sorrachai","family":"Yingchareonthawornchai","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"},{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","series-title":"LIPIcs","first-page":"15","volume-title":"ESA","author":"Ashvinkumar Vikrant","unstructured":"Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, and Hsin-Hao Su. Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights. In ESA, volume 308 of LIPIcs, pages 13:1\u201313:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1137\/S0097539794271898"},{"key":"e_1_3_2_1_3_1","first-page":"790","volume-title":"FOCS","author":"Abraham Ittai","unstructured":"Ittai Abraham, Yair Bartal, and Ofer Neiman. Nearly tight low stretch spanning trees. In FOCS, pages 781\u2013790. IEEE Computer Society, 2008."},{"key":"e_1_3_2_1_4_1","series-title":"Lecture Notes in Computer Science","first-page":"538","volume-title":"ICALP (2)","author":"Ahn Kook Jin","unstructured":"Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. In ICALP (2), volume 6756 of Lecture Notes in Computer Science, pages 526\u2013538. Springer, 2011."},{"key":"e_1_3_2_1_5_1","first-page":"669","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Assadi Sepehr","unstructured":"Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Semi-streaming bipartite matching in fewer passes and optimal space. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627\u2013669. SIAM, 2022."},{"key":"e_1_3_2_1_6_1","series-title":"LIPIcs","first-page":"17","volume-title":"DISC","author":"Ahmadi Mohamad","unstructured":"Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed approximate maximum matching in the CONGEST model. In DISC, volume 121 of LIPIcs, pages 6:1\u20136:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018."},{"key":"e_1_3_2_1_7_1","first-page":"171","volume-title":"SOSA","author":"Assadi Sepehr","unstructured":"Sepehr Assadi, S. Cliff Liu, and Robert E. Tarjan. An auction algorithm for bipartite matching in streaming and massively parallel computation models. In SOSA, pages 165\u2013171. SIAM, 2021."},{"key":"e_1_3_2_1_8_1","first-page":"353","volume-title":"FOCS","author":"Assadi Sepehr","unstructured":"Sepehr Assadi and Ran Raz. Near-quadratic lower bounds for two-pass graph streaming algorithms. In FOCS, pages 342\u2013353. IEEE, 2020."},{"key":"e_1_3_2_1_9_1","first-page":"227","volume-title":"SOSA","author":"Assadi Sepehr","unstructured":"Sepehr Assadi and Vihan Shah. Tight bounds for vertex connectivity in dynamic streams. In SOSA, pages 213\u2013227. SIAM, 2023."},{"key":"e_1_3_2_1_10_1","volume-title":"Nearly optimal communication and query complexity of bipartite matching. arXiv preprint arXiv:2208.02526","author":"Blikstad Joakim","year":"2022","unstructured":"Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Nearly optimal communication and query complexity of bipartite matching. arXiv preprint arXiv:2208.02526, 2022."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1016\/0020-0190(82)90046-1"},{"key":"e_1_3_2_1_12_1","first-page":"930","volume-title":"FOCS","author":"van den Brand Jan","unstructured":"Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In FOCS, pages 919\u2013930. IEEE, 2020."},{"key":"e_1_3_2_1_13_1","first-page":"611","volume-title":"FOCS","author":"Bernstein Aaron","unstructured":"Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight single-source shortest paths in near-linear time. In FOCS, pages 600\u2013611. IEEE, 2022."},{"key":"e_1_3_2_1_14_1","first-page":"1185","volume-title":"FOCS","author":"Blikstad Joakim","unstructured":"Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Nearly optimal communication and query complexity of bipartite matching. In FOCS, pages 1174\u20131185. IEEE, 2022."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1007\/s10619-013-7131-9"},{"key":"e_1_3_2_1_16_1","first-page":"4372","volume-title":"SODA","author":"Cao Nairen","unstructured":"Nairen Cao and Jeremy T. Fineman. Parallel exact shortest paths in almost linear work and square root depth. In SODA, pages 4354\u20134372. SIAM, 2023."},{"key":"e_1_3_2_1_17_1","first-page":"165","volume-title":"PODC","author":"Censor-Hillel Keren","unstructured":"Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. Distributed connectivity decomposition. In PODC, pages 156\u2013165. ACM, 2014."},{"key":"e_1_3_2_1_18_1","volume-title":"Vladimir Lysikov, and Jeroen Zuiddam. Barriers for rectangular matrix multiplication. CoRR, abs\/2003.03019","author":"Christandl Matthias","year":"2020","unstructured":"Matthias Christandl, Fran\u00e7ois Le Gall, Vladimir Lysikov, and Jeroen Zuiddam. Barriers for rectangular matrix multiplication. CoRR, abs\/2003.03019, 2020."},{"key":"e_1_3_2_1_19_1","first-page":"623","volume-title":"FOCS","author":"Chen Li","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In FOCS, pages 612\u2013623. IEEE, 2022."},{"key":"e_1_3_2_1_20_1","first-page":"352","volume-title":"STOC","author":"Cohen Michael B.","unstructured":"Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving SDD linear systems in nearly mlog^1\/2n time. In STOC, pages 343\u2013352. ACM, 2014."},{"key":"e_1_3_2_1_21_1","first-page":"583","volume-title":"STOC","author":"Chen Lijie","unstructured":"Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Almost optimal super-constant-pass streaming lower bounds for reachability. In STOC, pages 570\u2013583. ACM, 2021."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1137\/0222013"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1137\/S0097539792236717"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1007\/BF01302965"},{"key":"e_1_3_2_1_25_1","first-page":"73","volume-title":"PODC","author":"Chang Yi-Jun","unstructured":"Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In PODC, pages 66\u201373. ACM, 2019."},{"key":"e_1_3_2_1_26_1","first-page":"388","volume-title":"FOCS","author":"Chang Yi-Jun","unstructured":"Yi-Jun Chang and Thatchaphol Saranurak. Deterministic distributed expander decomposition and routing with applications in distributed derandomization. In FOCS, pages 377\u2013388. IEEE, 2020."},{"key":"e_1_3_2_1_27_1","first-page":"401","volume-title":"STOC","author":"Cheriyan Joseph","unstructured":"Joseph Cheriyan and Ramakrishna Thurimella. Algorithms for parallel k-vertex connectivity and sparse certificates (extended abstract). In STOC, pages 391\u2013401. ACM, 1991."},{"key":"e_1_3_2_1_28_1","first-page":"1153","volume-title":"STOC","author":"Dory Michal","unstructured":"Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Distributed weighted min-cut in nearly-optimal time. In STOC, pages 1144\u20131153. ACM, 2021."},{"key":"e_1_3_2_1_29_1","first-page":"74","volume-title":"PODC","author":"de Vos Tijn","unstructured":"Tijn de Vos. Brief announcement: Minimum cost maximum flow in the CONGEST model. In PODC, pages 71\u201374. ACM, 2023."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1002\/net.3230140211"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.5555\/3226239.3226375"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1137\/0204043"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1137\/0204034"},{"key":"e_1_3_2_1_34_1","first-page":"999","volume-title":"FOCS","author":"Forster Sebastian","unstructured":"Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. Minor sparsifiers and the distributed laplacian paradigm. In FOCS, pages 989\u2013999. IEEE, 2021."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.1016\/j.jcss.2004.04.011"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1145\/1183907.1183912"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1137\/0209016"},{"key":"e_1_3_2_1_38_1","first-page":"280","volume-title":"SPAA","author":"Gianinazzi Lukas","unstructured":"Lukas Gianinazzi and Torsten Hoefler. Parallel planar subgraph isomorphism and vertex connectivity. In SPAA, pages 269\u2013280. ACM, 2020."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1007\/BF02122800"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1137\/0221011"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1006\/jagm.1993.1009"},{"key":"e_1_3_2_1_42_1","first-page":"291","volume-title":"PODC","author":"Ghaffari Mohsen","unstructured":"Mohsen Ghaffari and Goran Zuzic. Universally-optimal distributed exact min-cut. In PODC, pages 281\u2013291. ACM, 2022."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_43_1","DOI":"10.1006\/jagm.1997.0855"},{"key":"e_1_3_2_1_44_1","first-page":"82","volume-title":"STOC","author":"Haeupler Bernhard","unstructured":"Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, and Thatchaphol Saranurak. Low-step multi-commodity flow emulators. In STOC, pages 71\u201382. ACM, 2024."},{"key":"e_1_3_2_1_45_1","series-title":"LIPIcs","first-page":"152","volume-title":"FSTTCS","author":"Harsha Prahladh","unstructured":"Prahladh Harsha and Rahul Jain. A strong direct product theorem for the tribes function via the smooth-rectangle bound. In FSTTCS, volume 24 of LIPIcs, pages 141\u2013152. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2013."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1006\/jagm.1999.1055"},{"key":"e_1_3_2_1_47_1","first-page":"1338","volume-title":"STOC","author":"Haeupler Bernhard","unstructured":"Bernhard Haeupler, Harald R\u00e4cke, and Mohsen Ghaffari. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. In STOC, pages 1325\u20131338. ACM, 2022."},{"key":"e_1_3_2_1_48_1","first-page":"682","volume-title":"STOC","author":"Jayram T. S.","unstructured":"T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In STOC, pages 673\u2013682. ACM, 2003."},{"key":"e_1_3_2_1_49_1","first-page":"1801","volume-title":"STOC","author":"Jiang Yonggang","unstructured":"Yonggang Jiang and Sagnik Mukhopadhyay. Finding a small vertex cut on distributed networks. In STOC, pages 1791\u20131801. ACM, 2023."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_50_1","DOI":"10.1145\/331605.331608"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_51_1","DOI":"10.1109\/TCT.1969.1082941"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_52_1","DOI":"10.1007\/BF02579407"},{"key":"e_1_3_2_1_53_1","first-page":"1686","volume-title":"FOCS","author":"Liu Yang P.","unstructured":"Yang P. Liu, Arun Jambulapati, and Aaron Sidford. Parallel reachability in almost linear work and square root depth. In FOCS, pages 1664\u20131686. IEEE Computer Society, 2019."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_54_1","DOI":"10.1007\/BF02122557"},{"key":"e_1_3_2_1_55_1","first-page":"361","volume-title":"SPAA","author":"L\u00f3pez-Mart\u00ednez Andr\u00e9s","unstructured":"Andr\u00e9s L\u00f3pez-Mart\u00ednez, Sagnik Mukhopadhyay, and Danupon Nanongkai. Work-optimal parallel minimum cuts for non-sparse graphs. In SPAA, pages 351\u2013361. ACM, 2021."},{"key":"e_1_3_2_1_56_1","first-page":"329","volume-title":"STOC","author":"Li Jason","unstructured":"Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Vertex connectivity in poly-logarithmic max-flows. In STOC, pages 317\u2013329. ACM, 2021."},{"key":"e_1_3_2_1_57_1","first-page":"574","volume-title":"FCT","author":"Lov\u00e1sz L\u00e1szl\u00f3","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. On determinants, matchings, and random algorithms. In FCT, pages 565\u2013574. Akademie-Verlag, Berlin, 1979."},{"key":"e_1_3_2_1_58_1","first-page":"92","volume-title":"FOCS","author":"Li Jason","unstructured":"Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows. In FOCS, pages 85\u201392. IEEE, 2020."},{"key":"e_1_3_2_1_59_1","volume-title":"Improved distributed approximate matching. Journal of the ACM (JACM), 62(5):1\u201317","author":"Lotker Zvi","year":"2015","unstructured":"Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved distributed approximate matching. Journal of the ACM (JACM), 62(5):1\u201317, 2015."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_60_1","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_61_1","first-page":"251","volume-title":"FOCS","author":"Matula David W.","unstructured":"David W. Matula. Determining edge connectivity in o(nm). In FOCS, pages 249\u2013251. IEEE Computer Society, 1987."},{"key":"e_1_3_2_1_62_1","first-page":"509","volume-title":"STOC","author":"Mukhopadhyay Sagnik","unstructured":"Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. In STOC, pages 496\u2013509. ACM, 2020."},{"key":"e_1_3_2_1_63_1","volume-title":"A note on isolating cut lemma for submodular function minimization. CoRR, abs\/2103.15724","author":"Mukhopadhyay Sagnik","year":"2021","unstructured":"Sagnik Mukhopadhyay and Danupon Nanongkai. A note on isolating cut lemma for submodular function minimization. CoRR, abs\/2103.15724, 2021."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_64_1","DOI":"10.1145\/341800"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_65_1","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_1_66_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICALP","author":"Nanongkai Danupon","unstructured":"Danupon Nanongkai. Cross-paradigm graph algorithms (invited talk). In ICALP, volume 297 of LIPIcs, pages 3:1\u20133:1. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_67_1","DOI":"10.1016\/0020-0190(91)90157-D"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_68_1","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_2_1_69_1","volume-title":"34th International Symposium on Distributed Computing (DISC 2020","author":"Parter Merav","year":"2020","unstructured":"Merav Parter. Distributed planar reachability in nearly optimal time. In 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2020."},{"key":"e_1_3_2_1_70_1","first-page":"136","article-title":"An algorithm for finding the edge connectivity of graphs","volume":"2","author":"Podderyugin VD","year":"1973","unstructured":"VD Podderyugin. An algorithm for finding the edge connectivity of graphs. Vopr. Kibern, 2:136, 1973.","journal-title":"Vopr. Kibern"},{"key":"e_1_3_2_1_71_1","volume-title":"36th International Symposium on Distributed Computing (DISC 2022)","author":"Parter Merav","year":"2022","unstructured":"Merav Parter and Asaf Petruschka. Near-optimal distributed computation of small vertex cuts. In 36th International Symposium on Distributed Computing (DISC 2022), 2022."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_72_1","DOI":"10.1145\/2000807.2000814"},{"key":"e_1_3_2_1_73_1","first-page":"487","volume-title":"STOC","author":"Rozhon V\u00e1clav","unstructured":"V\u00e1clav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li. Undirected (1+\u220a)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In STOC, pages 478\u2013487. ACM, 2022."},{"key":"e_1_3_2_1_74_1","first-page":"238","volume-title":"SODA","author":"R\u00e4cke Harald","unstructured":"Harald R\u00e4cke, Chintan Shah, and Hanjo T\u00e4ubig. Computing cut-based hierarchical decompositions in almost linear time. In SODA, pages 227\u2013238. SIAM, 2014."},{"key":"e_1_3_2_1_75_1","first-page":"126","volume-title":"SODA","author":"Sankowski Piotr","unstructured":"Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In SODA, pages 118\u2013126. SIAM, 2007."},{"key":"e_1_3_2_1_76_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Number v. 1 in Algorithms and Combinatorics","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Number v. 1 in Algorithms and Combinatorics. Springer, 2003."},{"key":"e_1_3_2_1_77_1","first-page":"269","volume-title":"FOCS","author":"Sherman Jonah","unstructured":"Jonah Sherman. Nearly maximum flows in nearly linear time. In FOCS, pages 263\u2013269. IEEE Computer Society, 2013."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_78_1","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_3_2_1_79_1","first-page":"90","volume-title":"STOC","author":"Daniel","unstructured":"Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In STOC, pages 81\u201390. ACM, 2004."},{"key":"e_1_3_2_1_80_1","first-page":"800","volume-title":"FOCS","author":"Saranurak Thatchaphol","unstructured":"Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. Deterministic small vertex connectivity in almost linear time. In FOCS, pages 789\u2013800. IEEE, 2022."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_81_1","DOI":"10.1006\/jagm.1996.0832"},{"key":"e_1_3_2_1_82_1","volume-title":"Parallel minimum cost flow in near-linear work and square root depth for dense instances","author":"van den Brand Jan","year":"2025","unstructured":"Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, and Tijn de Vos. Parallel minimum cost flow in near-linear work and square root depth for dense instances, 2025."},{"key":"e_1_3_2_1_83_1","first-page":"480","volume-title":"FOCS","author":"van den Brand Jan","unstructured":"Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In FOCS, pages 456\u2013480. IEEE Computer Society, 2019."}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '25","name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:50:51Z","timestamp":1750693851000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":83,"alternative-id":["10.1145\/3717823.3718316","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718316","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}