[{"citation":{"apa":"Kolmogorov, V. (2025). A simpler and parallelizable O(√log n)-approximation algorithm for SPARSEST CUT. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3748723\">https://doi.org/10.1145/3748723</a>","ama":"Kolmogorov V. A simpler and parallelizable O(√log n)-approximation algorithm for SPARSEST CUT. <i>ACM Transactions on Algorithms</i>. 2025;21(4):1-22. doi:<a href=\"https://doi.org/10.1145/3748723\">10.1145/3748723</a>","ieee":"V. Kolmogorov, “A simpler and parallelizable O(√log n)-approximation algorithm for SPARSEST CUT,” <i>ACM Transactions on Algorithms</i>, vol. 21, no. 4. Association for Computing Machinery, pp. 1–22, 2025.","ista":"Kolmogorov V. 2025. A simpler and parallelizable O(√log n)-approximation algorithm for SPARSEST CUT. ACM Transactions on Algorithms. 21(4), 1–22.","chicago":"Kolmogorov, Vladimir. “A Simpler and Parallelizable O(√log n)-Approximation Algorithm for SPARSEST CUT.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3748723\">https://doi.org/10.1145/3748723</a>.","short":"V. Kolmogorov, ACM Transactions on Algorithms 21 (2025) 1–22.","mla":"Kolmogorov, Vladimir. “A Simpler and Parallelizable O(√log n)-Approximation Algorithm for SPARSEST CUT.” <i>ACM Transactions on Algorithms</i>, vol. 21, no. 4, Association for Computing Machinery, 2025, pp. 1–22, doi:<a href=\"https://doi.org/10.1145/3748723\">10.1145/3748723</a>."},"file":[{"file_name":"2025_ACMToA_Kolmogorov.pdf","date_created":"2026-01-21T09:38:09Z","file_id":"21031","file_size":2208302,"creator":"dernst","date_updated":"2026-01-21T09:38:09Z","success":1,"access_level":"open_access","relation":"main_file","checksum":"4a80fdb1e3711b9a2768d2bb8f6d3b4e","content_type":"application/pdf"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"status":"public","scopus_import":"1","doi":"10.1145/3748723","day":"01","publication_status":"published","department":[{"_id":"VlKo"}],"corr_author":"1","month":"10","related_material":{"record":[{"status":"public","relation":"shorter_version","id":"17236"}]},"quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"arxiv":1,"publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"date_created":"2026-01-20T10:04:02Z","publication":"ACM Transactions on Algorithms","abstract":[{"text":"Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes O(√(log n)/ε)-approximation using O(nε logO(1) n) maxflows for any ε∈[Θ(1/log n),Θ(1)]. It works by solving the SDP relaxation of [Arora-Rao-Vazirani, STOC 2004] using the Multiplicative Weights Update algorithm (MW) of [Arora-Kale, JACM 2016]. To implement one MW step, Sherman approximately solves a multicommodity flow problem using another application of MW. Nested MW steps are solved via a certain \"chaining\" algorithm that combines results of multiple calls to the maxflow algorithm. We present an alternative approach that avoids solving the multicommodity flow problem and instead computes \"violating paths\". This simplifies Sherman's algorithm by removing a need for a nested application of MW, and also allows parallelization: we show how to compute O(√(log n)/ε)-approximation via O(logO(1) n) maxflows using O(nε) processors. We also revisit Sherman's chaining algorithm, and present a simpler version together with a new analysis.","lang":"eng"}],"date_updated":"2026-01-21T09:46:26Z","type":"journal_article","file_date_updated":"2026-01-21T09:38:09Z","PlanS_conform":"1","OA_type":"hybrid","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"A simpler and parallelizable O(√log n)-approximation algorithm for SPARSEST CUT","OA_place":"publisher","article_type":"original","has_accepted_license":"1","oa":1,"ddc":["510"],"publisher":"Association for Computing Machinery","year":"2025","date_published":"2025-10-01T00:00:00Z","page":"1-22","article_processing_charge":"Yes (via OA deal)","intvolume":"        21","volume":21,"_id":"21007","issue":"4","external_id":{"arxiv":["2307.00115"]},"author":[{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","first_name":"Vladimir"}]},{"title":"Parameter estimation for Gibbs distributions","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"green","article_type":"original","OA_place":"repository","oa":1,"date_created":"2025-01-19T23:01:52Z","publication":"ACM Transactions on Algorithms","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"abstract":[{"lang":"eng","text":"A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n]. Two important parameters are the partition function, which is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the vector of pre-image counts c_x=|H^-1(x)|.\r\nWe develop black-box sampling algorithms to estimate the counts roughly Õ(n²/ε²) samples for integer-valued distributions and Õ(q/ε²) samples for general distributions, where q = (log Z(β_max))/Z(β_min)  (ignoring some second-order terms and parameters). We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we estimate all values of the partition function using Õ(n²/ε²) samples for integer-valued distributions and Õ(q/ε²) samples for general distributions. This improves over a prior algorithm of Huber (2015) which computes a single point estimate Z(β_max) and which uses a slightly larger amount of samples. We show matching lower bounds, demonstrating this complexity is optimal as a function of n and q up to logarithmic terms."}],"type":"journal_article","date_updated":"2025-07-10T11:50:44Z","publication_status":"published","department":[{"_id":"VlKo"}],"day":"01","doi":"10.1145/3685676","ec_funded":1,"related_material":{"record":[{"id":"14084","relation":"earlier_version","status":"public"}]},"corr_author":"1","month":"01","oa_version":"Preprint","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"citation":{"short":"D.G. Harris, V. Kolmogorov, ACM Transactions on Algorithms 21 (2025).","chicago":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3685676\">https://doi.org/10.1145/3685676</a>.","mla":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” <i>ACM Transactions on Algorithms</i>, vol. 21, no. 1, 3, Association for Computing Machinery, 2025, doi:<a href=\"https://doi.org/10.1145/3685676\">10.1145/3685676</a>.","ista":"Harris DG, Kolmogorov V. 2025. Parameter estimation for Gibbs distributions. ACM Transactions on Algorithms. 21(1), 3.","ieee":"D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,” <i>ACM Transactions on Algorithms</i>, vol. 21, no. 1. Association for Computing Machinery, 2025.","ama":"Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. <i>ACM Transactions on Algorithms</i>. 2025;21(1). doi:<a href=\"https://doi.org/10.1145/3685676\">10.1145/3685676</a>","apa":"Harris, D. G., &#38; Kolmogorov, V. (2025). Parameter estimation for Gibbs distributions. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3685676\">https://doi.org/10.1145/3685676</a>"},"status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2007.10824"}],"acknowledgement":"We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, and Maksym Serbyn for bringing to our attention the WL algorithm and its use in physics.\r\nThis is an extended version, which includes work under the same name from ICALP 2023, as well as the earlier work [22] appearing in COLT 2018.\r\nV. Kolmogorov was supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160","scopus_import":"1","_id":"18855","issue":"1","external_id":{"isi":["001399998600008"],"arxiv":["2007.10824"]},"author":[{"full_name":"Harris, David G.","last_name":"Harris","first_name":"David G."},{"first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov"}],"isi":1,"intvolume":"        21","volume":21,"date_published":"2025-01-01T00:00:00Z","article_processing_charge":"No","project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"publisher":"Association for Computing Machinery","year":"2025","article_number":"3"},{"article_type":"original","title":"Constant-time Dynamic (Δ +1)-Coloring","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ +1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω (log n) time per operation.","lang":"eng"}],"publication":"ACM Transactions on Algorithms","date_created":"2022-07-27T10:58:53Z","publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"type":"journal_article","date_updated":"2024-11-04T11:42:31Z","month":"03","publication_status":"published","doi":"10.1145/3501403","day":"04","language":[{"iso":"eng"}],"oa_version":"None","quality_controlled":"1","status":"public","citation":{"ieee":"M. Henzinger and P. Peng, “Constant-time Dynamic (Δ +1)-Coloring,” <i>ACM Transactions on Algorithms</i>, vol. 18, no. 2. Association for Computing Machinery, 2022.","ama":"Henzinger M, Peng P. Constant-time Dynamic (Δ +1)-Coloring. <i>ACM Transactions on Algorithms</i>. 2022;18(2). doi:<a href=\"https://doi.org/10.1145/3501403\">10.1145/3501403</a>","apa":"Henzinger, M., &#38; Peng, P. (2022). Constant-time Dynamic (Δ +1)-Coloring. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3501403\">https://doi.org/10.1145/3501403</a>","short":"M. Henzinger, P. Peng, ACM Transactions on Algorithms 18 (2022).","mla":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.” <i>ACM Transactions on Algorithms</i>, vol. 18, no. 2, 16, Association for Computing Machinery, 2022, doi:<a href=\"https://doi.org/10.1145/3501403\">10.1145/3501403</a>.","chicago":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3501403\">https://doi.org/10.1145/3501403</a>.","ista":"Henzinger M, Peng P. 2022. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions on Algorithms. 18(2), 16."},"scopus_import":"1","acknowledgement":"We want to thank an anonymous referee who pointed out a mistake in our conference paper as well as suggesting a fix using an approach in References.","_id":"11662","issue":"2","extern":"1","author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"first_name":"Pan","full_name":"Peng, Pan","last_name":"Peng"}],"intvolume":"        18","volume":18,"date_published":"2022-03-04T00:00:00Z","article_processing_charge":"No","publisher":"Association for Computing Machinery","year":"2022","article_number":"16"},{"article_processing_charge":"No","date_published":"2021-10-04T00:00:00Z","year":"2021","article_number":"29","publisher":"Association for Computing Machinery","author":[{"full_name":"Bernstein, Aaron","last_name":"Bernstein","first_name":"Aaron"},{"first_name":"Sebastian","last_name":"Forster","full_name":"Forster, Sebastian"},{"orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"issue":"4","_id":"11663","extern":"1","external_id":{"arxiv":["1810.10932"]},"volume":17,"intvolume":"        17","language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","arxiv":1,"publication_status":"published","day":"04","doi":"10.1145/3469833","month":"10","scopus_import":"1","acknowledgement":"The conference version of this article [10] had an error in the analysis of the dynamic matching algorithm. In particular, Lemma 4.5 assumed an independence between adversarial updates to the hierarchy that is in fact true, but which requires a sophisticated proof. We are very grateful to the anonymous reviewers of Transactions on Algorithms for pointing out this mistake in our analysis. The mistake is fixed in Section 4.5. Almost the entire fix is a matter of analysis: the only change to the algorithm itself is the introduction of responsible bits in Algorithm 2. The first author would like to thank Mikkel Thorup and Alan Roytman for a very helpful discussion of the proof of Theorem 1.1.","citation":{"mla":"Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 4, 29, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3469833\">10.1145/3469833</a>.","short":"A. Bernstein, S. Forster, M. Henzinger, ACM Transactions on Algorithms 17 (2021).","chicago":"Bernstein, Aaron, Sebastian Forster, and Monika Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3469833\">https://doi.org/10.1145/3469833</a>.","ista":"Bernstein A, Forster S, Henzinger M. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.","ieee":"A. Bernstein, S. Forster, and M. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 4. Association for Computing Machinery, 2021.","ama":"Bernstein A, Forster S, Henzinger M. A deamortization approach for dynamic spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>. 2021;17(4). doi:<a href=\"https://doi.org/10.1145/3469833\">10.1145/3469833</a>","apa":"Bernstein, A., Forster, S., &#38; Henzinger, M. (2021). A deamortization approach for dynamic spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3469833\">https://doi.org/10.1145/3469833</a>"},"status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1810.10932"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"A deamortization approach for dynamic spanner and dynamic maximal matching","article_type":"original","type":"journal_article","date_updated":"2024-11-06T12:05:37Z","publication":"ACM Transactions on Algorithms","date_created":"2022-07-27T11:09:06Z","publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"abstract":[{"lang":"eng","text":"Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability.\r\n\r\nIn this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem.\r\n\r\n(1)\r\n\r\nFor dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining a (2k-1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ(n1+1/k) edges.)\r\n\r\n(2)\r\n\r\nFor dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log 5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal.\r\n\r\nOur results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O(log 2(n)).\r\n\r\nThus, we achieve our results in two steps:\r\n\r\n(1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times.\r\n\r\n(2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms."}]},{"article_number":"16","year":"2021","ddc":["000"],"publisher":"Association for Computing Machinery","project":[{"grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"article_processing_charge":"No","date_published":"2021-06-01T00:00:00Z","volume":17,"intvolume":"        17","isi":1,"author":[{"last_name":"Czumaj","full_name":"Czumaj, Artur","first_name":"Artur"},{"orcid":"0000-0002-5646-9524","first_name":"Peter","last_name":"Davies","full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425"},{"first_name":"Merav","last_name":"Parter","full_name":"Parter, Merav"}],"issue":"2","_id":"9541","external_id":{"isi":["000661311300006"],"arxiv":["1912.05390"]},"scopus_import":"1","acknowledgement":"Institute of Science and Technology Austria (IST Austria). Email: peter.davies@ist.ac.at. Work partially\r\ndone at the Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick. Research partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411, the Centre for Discrete Mathematics and its Applications, a Weizmann-UK Making Connections Grant, and EPSRC award EP/N011163/1.","file":[{"success":1,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"a21c627683890c309a68f6389302c408","date_created":"2021-06-10T19:33:56Z","file_id":"9542","file_name":"MISMM-arxiv.pdf","date_updated":"2021-06-10T19:33:56Z","file_size":587404,"creator":"pdavies"}],"citation":{"ieee":"A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing massively parallel computation with low space,” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2. Association for Computing Machinery, 2021.","ama":"Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. 2021;17(2). doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>","short":"A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).","mla":"Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2, 16, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>.","ista":"Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 17(2), 16."},"status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1912.05390","open_access":"1"}],"quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Submitted Version","arxiv":1,"ec_funded":1,"day":"01","doi":"10.1145/3451992","department":[{"_id":"DaAl"}],"publication_status":"published","month":"06","related_material":{"record":[{"id":"7802","relation":"earlier_version","status":"public"}]},"date_updated":"2025-04-15T06:54:47Z","type":"journal_article","file_date_updated":"2021-06-10T19:33:56Z","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"date_created":"2021-06-10T19:31:05Z","publication":"ACM Transactions on Algorithms","abstract":[{"lang":"eng","text":"The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17]."}],"oa":1,"has_accepted_license":"1","title":"Graph sparsification for derandomizing massively parallel computation with low space","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original"},{"date_published":"2018-04-01T00:00:00Z","article_processing_charge":"No","publisher":"Association for Computing Machinery","article_number":"17","year":"2018","_id":"11664","extern":"1","issue":"2","external_id":{"arxiv":["1611.06500"]},"author":[{"full_name":"Goranci, Gramoz","last_name":"Goranci","first_name":"Gramoz"},{"last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"first_name":"Mikkel","last_name":"Thorup","full_name":"Thorup, Mikkel"}],"intvolume":"        14","volume":14,"day":"01","doi":"10.1145/3174803","publication_status":"published","month":"04","quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"arxiv":1,"citation":{"apa":"Goranci, G., Henzinger, M., &#38; Thorup, M. (2018). Incremental exact min-cut in polylogarithmic amortized update time. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3174803\">https://doi.org/10.1145/3174803</a>","ama":"Goranci G, Henzinger M, Thorup M. Incremental exact min-cut in polylogarithmic amortized update time. <i>ACM Transactions on Algorithms</i>. 2018;14(2). doi:<a href=\"https://doi.org/10.1145/3174803\">10.1145/3174803</a>","ieee":"G. Goranci, M. Henzinger, and M. Thorup, “Incremental exact min-cut in polylogarithmic amortized update time,” <i>ACM Transactions on Algorithms</i>, vol. 14, no. 2. Association for Computing Machinery, 2018.","ista":"Goranci G, Henzinger M, Thorup M. 2018. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 14(2), 17.","mla":"Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” <i>ACM Transactions on Algorithms</i>, vol. 14, no. 2, 17, Association for Computing Machinery, 2018, doi:<a href=\"https://doi.org/10.1145/3174803\">10.1145/3174803</a>.","short":"G. Goranci, M. Henzinger, M. Thorup, ACM Transactions on Algorithms 14 (2018).","chicago":"Goranci, Gramoz, Monika Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3174803\">https://doi.org/10.1145/3174803</a>."},"status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.06500"}],"acknowledgement":"We thank the two anonymous reviewers for their suggestions and comments, which improved the\r\nquality of the article.","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Incremental exact min-cut in polylogarithmic amortized update time","article_type":"original","oa":1,"publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"date_created":"2022-07-27T11:29:39Z","publication":"ACM Transactions on Algorithms","abstract":[{"text":"We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O(log3 n log log2 n) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup (2007). It also stays in sharp contrast to a polynomial conditional lower bound for the fully dynamic weighted minimum cut problem. Our algorithm is obtained by combining a sparsification technique of Kawarabayashi and Thorup (2015) or its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental algorithm of Henzinger (1997).\r\n\r\nWe also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(nlog n/ε2) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O((α (n) log3 n)/ε 2) amortized update time and constant query time, where α (n) stands for the inverse of Ackermann function.","lang":"eng"}],"date_updated":"2024-11-06T12:05:51Z","type":"journal_article"},{"article_number":"51","year":"2017","publisher":"Association for Computing Machinery","article_processing_charge":"No","date_published":"2017-10-01T00:00:00Z","volume":13,"intvolume":"        13","author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"last_name":"Nanongkai","full_name":"Nanongkai, Danupon","first_name":"Danupon"}],"issue":"4","_id":"11665","external_id":{"arxiv":["1512.08147"]},"extern":"1","scopus_import":"1","acknowledgement":"We thank the reviewers of ICALP 2013 for pointing to related articles and to an error in an example\r\ngiven in a previous version of this article. We also thank one of the reviewers of Transactions on\r\nAlgorithms for very detailed comments.","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1512.08147","open_access":"1"}],"citation":{"ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks,” <i>ACM Transactions on Algorithms</i>, vol. 13, no. 4. Association for Computing Machinery, 2017.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2017). Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3146550\">https://doi.org/10.1145/3146550</a>","ama":"Henzinger M, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. <i>ACM Transactions on Algorithms</i>. 2017;13(4). doi:<a href=\"https://doi.org/10.1145/3146550\">10.1145/3146550</a>","short":"M. Henzinger, S. Krinninger, D. Nanongkai, ACM Transactions on Algorithms 13 (2017).","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2017. <a href=\"https://doi.org/10.1145/3146550\">https://doi.org/10.1145/3146550</a>.","mla":"Henzinger, Monika, et al. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” <i>ACM Transactions on Algorithms</i>, vol. 13, no. 4, 51, Association for Computing Machinery, 2017, doi:<a href=\"https://doi.org/10.1145/3146550\">10.1145/3146550</a>.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2017. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. ACM Transactions on Algorithms. 13(4), 51."},"arxiv":1,"oa_version":"Preprint","quality_controlled":"1","language":[{"iso":"eng"}],"month":"10","doi":"10.1145/3146550","day":"01","publication_status":"published","date_updated":"2024-11-06T12:06:03Z","type":"journal_article","abstract":[{"lang":"eng","text":"We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic (1+ϵ)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network.\r\n\r\nOur technique also leads to a deterministic (1+ϵ)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011; Henzinger et al. 2015). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed."}],"publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"publication":"ACM Transactions on Algorithms","date_created":"2022-07-27T11:37:23Z","oa":1,"article_type":"original","title":"Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]