[{"type":"conference","file_date_updated":"2025-07-14T06:13:10Z","conference":{"location":"Prague, Czechia","end_date":"2025-06-27","name":"STOC: Symposium on Theory of Computing","start_date":"2025-06-23"},"doi":"10.1145/3717823.3718173","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"license":"https://creativecommons.org/licenses/by/4.0/","acknowledgement":"All authors were supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Michael Anastos was also supported in part by the Austrian Science Fund (FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. For Open Access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.","has_accepted_license":"1","corr_author":"1","publisher":"Association for Computing Machinery","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2098–2106.","ama":"Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:2098-2106. doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>","ista":"Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 2098–2106.","chicago":"Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis for Graph Isomorphism.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 2098–2106. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>.","ieee":"M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 2098–2106.","apa":"Anastos, M., Kwan, M. A., &#38; Moore, B. (2025). Smoothed analysis for graph isomorphism. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>","mla":"Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 2098–106, doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>."},"department":[{"_id":"MaKw"}],"article_processing_charge":"Yes (via OA deal)","publication_identifier":{"isbn":["9798400715105"],"issn":["0737-8017"]},"quality_controlled":"1","day":"15","arxiv":1,"OA_place":"publisher","date_published":"2025-06-15T00:00:00Z","page":"2098-2106","ec_funded":1,"abstract":[{"text":"There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph.","lang":"eng"}],"year":"2025","project":[{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"},{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"},{"name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","grant_number":"ESP3863424"}],"date_created":"2025-07-13T22:01:23Z","external_id":{"arxiv":["2410.06095"]},"oa_version":"Published Version","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","language":[{"iso":"eng"}],"_id":"20007","file":[{"relation":"main_file","content_type":"application/pdf","access_level":"open_access","file_name":"2025_STOC_Anastos.pdf","file_id":"20012","creator":"dernst","success":1,"date_created":"2025-07-14T06:13:10Z","date_updated":"2025-07-14T06:13:10Z","checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","file_size":706445}],"scopus_import":"1","status":"public","title":"Smoothed analysis for graph isomorphism","publication_status":"published","date_updated":"2025-07-14T06:33:50Z","ddc":["000"],"OA_type":"hybrid","author":[{"full_name":"Anastos, Michael","first_name":"Michael","last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore","first_name":"Benjamin","full_name":"Moore, Benjamin"}],"month":"06"},{"title":"Hardness of 4-colouring G-colourable graphs","scopus_import":"1","status":"public","file":[{"file_id":"20013","creator":"dernst","file_name":"2025_STOC_Avvakumov.pdf","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":940827,"checksum":"2c9ae7ad0102c41124976f4cb5182760","date_updated":"2025-07-14T06:42:58Z","success":1,"date_created":"2025-07-14T06:42:58Z"}],"_id":"20008","language":[{"iso":"eng"}],"publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","orcid":"0000-0002-7840-5062","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov"},{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","last_name":"Filakovský","full_name":"Filakovský, Marek","first_name":"Marek"},{"full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456","first_name":"Jakub","last_name":"Opršal","id":"ec596741-c539-11ec-b829-c79322a91242"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","last_name":"Tasinato","full_name":"Tasinato, Gianluca","first_name":"Gianluca"},{"orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"month":"06","OA_type":"hybrid","ddc":["000"],"date_updated":"2026-04-07T12:36:50Z","publication_status":"published","project":[{"grant_number":"P31312","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425"},{"grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"}],"year":"2025","abstract":[{"text":"We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory.","lang":"eng"}],"ec_funded":1,"page":"72-83","oa_version":"Published Version","date_created":"2025-07-13T22:01:23Z","related_material":{"record":[{"relation":"dissertation_contains","id":"20339","status":"public"}]},"publication_identifier":{"isbn":["9798400715105"],"issn":["0737-8017"]},"article_processing_charge":"Yes (in subscription journal)","citation":{"short":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 72–83.","ama":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring G-colourable graphs. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:72-83. doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>","ista":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.","apa":"Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., &#38; Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 72–83). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>","chicago":"Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 72–83. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>.","ieee":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of 4-colouring G-colourable graphs,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 72–83.","mla":"Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 72–83, doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"}],"publisher":"Association for Computing Machinery","date_published":"2025-06-15T00:00:00Z","OA_place":"publisher","day":"15","quality_controlled":"1","oa":1,"doi":"10.1145/3717823.3718154","conference":{"start_date":"2025-06-23","name":"STOC: Symposium on Theory of Computing","end_date":"2025-06-27","location":"Prague, Czechia"},"file_date_updated":"2025-07-14T06:42:58Z","type":"conference","corr_author":"1","has_accepted_license":"1","acknowledgement":"This research was supported by the Austrian Science Fund (FWF project P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed by the Ministry of Education, Youth and Sports of the Czech Republic. This project has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"month":"06","author":[{"full_name":"Daga, Mohit","first_name":"Mohit","last_name":"Daga"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"},{"full_name":"Saranurak, Thatchaphol","first_name":"Thatchaphol","last_name":"Saranurak"}],"publication_status":"published","date_updated":"2024-11-06T12:19:15Z","extern":"1","scopus_import":"1","status":"public","title":"Distributed edge connectivity in sublinear time","_id":"11865","language":[{"iso":"eng"}],"publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","oa_version":"Preprint","date_created":"2022-08-16T09:11:17Z","external_id":{"arxiv":["1904.04341"]},"year":"2019","abstract":[{"lang":"eng","text":"We present the first sublinear-time algorithm that can compute the edge connectivity λ of a network exactly on distributed message-passing networks (the CONGEST model), as long as the network contains no multi-edge. We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ(n1−1/353D1/353+n1−1/706) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ(n1−є)) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ=O(n1/8−є) [Thurimella PODC’95; Pritchard, Thurimella, ACM Trans. Algorithms’11; Nanongkai, Su, DISC’14] or (ii) approximately [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a k-edge connectivity certificate for any k=O(n1−є) in time Õ(√nk+D). The previous sublinear-time algorithm can do so only when k=o(√n) [Thurimella PODC’95]. In fact, our algorithm can be turned into the first parallel algorithm with polylogarithmic depth and near-linear work. Previous near-linear work algorithms are essentially sequential and previous polylogarithmic-depth algorithms require Ω(mk) work in the worst case (e.g. [Karger, Motwani, STOC’93]). Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA’19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC’15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the “trivial” ones). This leads to a simplification of the Kawarabayashi-Thorup framework (except that we are randomized while they are deterministic). This might make this framework more useful in other models of computation. Finally, by extending the tree packing technique from [Karger STOC’96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an Õ(n)-time algorithm for computing exact minimum cut for weighted graphs."}],"page":"343–354","date_published":"2019-06-01T00:00:00Z","day":"01","arxiv":1,"quality_controlled":"1","publication_identifier":{"isbn":["978-1-4503-6705-9"],"issn":["0737-8017"]},"article_processing_charge":"No","publisher":"Association for Computing Machinery","citation":{"ista":"Daga M, Henzinger M, Nanongkai D, Saranurak T. 2019. Distributed edge connectivity in sublinear time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 343–354.","ieee":"M. Daga, M. Henzinger, D. Nanongkai, and T. Saranurak, “Distributed edge connectivity in sublinear time,” in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, Phoenix, AZ, United States, 2019, pp. 343–354.","apa":"Daga, M., Henzinger, M., Nanongkai, D., &#38; Saranurak, T. (2019). Distributed edge connectivity in sublinear time. In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 343–354). Phoenix, AZ, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3313276.3316346\">https://doi.org/10.1145/3313276.3316346</a>","chicago":"Daga, Mohit, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. “Distributed Edge Connectivity in Sublinear Time.” In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, 343–354. Association for Computing Machinery, 2019. <a href=\"https://doi.org/10.1145/3313276.3316346\">https://doi.org/10.1145/3313276.3316346</a>.","mla":"Daga, Mohit, et al. “Distributed Edge Connectivity in Sublinear Time.” <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2019, pp. 343–354, doi:<a href=\"https://doi.org/10.1145/3313276.3316346\">10.1145/3313276.3316346</a>.","short":"M. Daga, M. Henzinger, D. Nanongkai, T. Saranurak, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2019, pp. 343–354.","ama":"Daga M, Henzinger M, Nanongkai D, Saranurak T. Distributed edge connectivity in sublinear time. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2019:343–354. doi:<a href=\"https://doi.org/10.1145/3313276.3316346\">10.1145/3313276.3316346</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"doi":"10.1145/3313276.3316346","main_file_link":[{"url":"https://arxiv.org/abs/1904.04341","open_access":"1"}],"conference":{"name":"STOC: Symposium on Theory of Computing","start_date":"2019-06-23","location":"Phoenix, AZ, United States","end_date":"2019-06-26"},"type":"conference"},{"date_updated":"2024-11-06T12:19:26Z","publication_status":"published","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Krinninger, Sebastian","first_name":"Sebastian","last_name":"Krinninger"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"month":"06","publication":"48th Annual ACM SIGACT Symposium on Theory of Computing","language":[{"iso":"eng"}],"_id":"11866","title":"A deterministic almost-tight distributed algorithm for approximating single-source shortest paths","status":"public","scopus_import":"1","extern":"1","external_id":{"arxiv":["1504.07056"]},"date_created":"2022-08-16T09:19:31Z","oa_version":"Preprint","page":"489 - 498","abstract":[{"text":"We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by Holzer et al. [PODC 2012].\r\n\r\nIn achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g. ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC 2014]. The second result partially answers an open problem raised by McGregor in 2006 [<pre>sublinear.info</pre>, Problem 14].","lang":"eng"}],"year":"2016","quality_controlled":"1","arxiv":1,"day":"01","date_published":"2016-06-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"M. Henzinger, S. Krinninger, D. Nanongkai, in:, 48th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp. 489–498.","ama":"Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2016:489-498. doi:<a href=\"https://doi.org/10.1145/2897518.2897638\">10.1145/2897518.2897638</a>","ista":"Henzinger M, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 489–498.","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, 489–98. Association for Computing Machinery, 2016. <a href=\"https://doi.org/10.1145/2897518.2897638\">https://doi.org/10.1145/2897518.2897638</a>.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2016). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 489–498). Cambridge, MA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2897518.2897638\">https://doi.org/10.1145/2897518.2897638</a>","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” in <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Cambridge, MA, United States, 2016, pp. 489–498.","mla":"Henzinger, Monika, et al. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2016, pp. 489–98, doi:<a href=\"https://doi.org/10.1145/2897518.2897638\">10.1145/2897518.2897638</a>."},"publisher":"Association for Computing Machinery","article_processing_charge":"No","publication_identifier":{"isbn":["978-145034132-5"],"issn":["0737-8017"]},"type":"conference","conference":{"location":"Cambridge, MA, United States","end_date":"2016-06-21","name":"STOC: Symposium on Theory of Computing","start_date":"2016-06-19"},"main_file_link":[{"url":"https://arxiv.org/abs/1504.07056","open_access":"1"}],"doi":"10.1145/2897518.2897638","oa":1},{"oa":1,"doi":"10.1145/2897518.2897568","main_file_link":[{"url":"https://arxiv.org/abs/1604.05765","open_access":"1"}],"conference":{"location":"Cambridge, MA, United States","end_date":"2016-06-21","name":"STOC: Symposium on Theory of Computing","start_date":"2016-06-19"},"type":"conference","publication_identifier":{"isbn":["978-145034132-5"],"issn":["0737-8017"]},"article_processing_charge":"No","publisher":"Association for Computing Machinery","citation":{"mla":"Bhattacharya, Sayan, et al. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2016, pp. 398–411, doi:<a href=\"https://doi.org/10.1145/2897518.2897568\">10.1145/2897518.2897568</a>.","apa":"Bhattacharya, S., Henzinger, M., &#38; Nanongkai, D. (2016). New deterministic approximation algorithms for fully dynamic matching. In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 398–411). Cambridge, MA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2897518.2897568\">https://doi.org/10.1145/2897518.2897568</a>","chicago":"Bhattacharya, Sayan, Monika Henzinger, and Danupon Nanongkai. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, 398–411. Association for Computing Machinery, 2016. <a href=\"https://doi.org/10.1145/2897518.2897568\">https://doi.org/10.1145/2897518.2897568</a>.","ieee":"S. Bhattacharya, M. Henzinger, and D. Nanongkai, “New deterministic approximation algorithms for fully dynamic matching,” in <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Cambridge, MA, United States, 2016, pp. 398–411.","ista":"Bhattacharya S, Henzinger M, Nanongkai D. 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 398–411.","ama":"Bhattacharya S, Henzinger M, Nanongkai D. New deterministic approximation algorithms for fully dynamic matching. In: <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2016:398-411. doi:<a href=\"https://doi.org/10.1145/2897518.2897568\">10.1145/2897518.2897568</a>","short":"S. Bhattacharya, M. Henzinger, D. Nanongkai, in:, 48th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp. 398–411."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2016-06-01T00:00:00Z","day":"01","arxiv":1,"quality_controlled":"1","year":"2016","abstract":[{"text":"We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+є)-approximate maximum matching in general graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an αK approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(logn)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.","lang":"eng"}],"page":"398 - 411","oa_version":"Preprint","external_id":{"arxiv":["1604.05765"]},"date_created":"2022-08-16T09:27:35Z","extern":"1","status":"public","scopus_import":"1","title":"New deterministic approximation algorithms for fully dynamic matching","_id":"11867","language":[{"iso":"eng"}],"publication":"48th Annual ACM SIGACT Symposium on Theory of Computing","author":[{"last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan","first_name":"Sayan"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"month":"06","publication_status":"published","date_updated":"2024-11-06T12:19:37Z"},{"type":"conference","conference":{"name":"STOC: Symposium on Theory of Computing","start_date":"2015-06-14","location":"Portland, OR, United States","end_date":"2015-06-17"},"main_file_link":[{"url":"https://arxiv.org/abs/1504.02268","open_access":"1"}],"doi":"10.1145/2746539.2746592","oa":1,"quality_controlled":"1","day":"01","arxiv":1,"date_published":"2015-06-01T00:00:00Z","publisher":"Association for Computing Machinery","citation":{"ista":"Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 173–182.","chicago":"Bhattacharya, Sayan, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” In <i>47th Annual ACM Symposium on Theory of Computing</i>, 173–82. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2746539.2746592\">https://doi.org/10.1145/2746539.2746592</a>.","apa":"Bhattacharya, S., Henzinger, M., Nanongkai, D., &#38; Tsourakakis, C. (2015). Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In <i>47th Annual ACM Symposium on Theory of Computing</i> (pp. 173–182). Portland, OR, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2746539.2746592\">https://doi.org/10.1145/2746539.2746592</a>","ieee":"S. Bhattacharya, M. Henzinger, D. Nanongkai, and C. Tsourakakis, “Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams,” in <i>47th Annual ACM Symposium on Theory of Computing</i>, Portland, OR, United States, 2015, pp. 173–182.","mla":"Bhattacharya, Sayan, et al. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” <i>47th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2015, pp. 173–82, doi:<a href=\"https://doi.org/10.1145/2746539.2746592\">10.1145/2746539.2746592</a>.","short":"S. Bhattacharya, M. Henzinger, D. Nanongkai, C. Tsourakakis, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015, pp. 173–182.","ama":"Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: <i>47th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2015:173-182. doi:<a href=\"https://doi.org/10.1145/2746539.2746592\">10.1145/2746539.2746592</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","publication_identifier":{"issn":["0737-8017"],"isbn":["978-145033536-2"]},"date_created":"2022-08-16T09:36:48Z","external_id":{"arxiv":["1504.02268"]},"oa_version":"Preprint","page":"173 - 182","abstract":[{"lang":"eng","text":"While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge.\r\n\r\nGiven an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor."}],"year":"2015","publication_status":"published","date_updated":"2024-11-06T12:20:01Z","month":"06","author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"},{"first_name":"Charalampos","full_name":"Tsourakakis, Charalampos","last_name":"Tsourakakis"}],"publication":"47th Annual ACM Symposium on Theory of Computing","language":[{"iso":"eng"}],"_id":"11869","scopus_import":"1","status":"public","title":"Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams","extern":"1"},{"year":"2014","abstract":[{"text":"We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem.\r\n\r\nIn this paper, we answer this question affirmatively. We obtain a randomized algorithm which, in a simplified form, achieves an Õ(mn0.984) expected total update time for SSR and (1 + ε)-approximate SSSP, where Õ(·) hides poly log n. We also extend our algorithm to achieve roughly the same running time for Strongly Connected Components (SCC), improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that improves the Õ (mn log W)-time algorithm of Bernstein (STOC 2013) for approximating SSSP on weighted directed graphs, where the edge weights are integers from 1 to W. All our algorithms have constant query time in the worst case.","lang":"eng"}],"oa_version":"Preprint","date_created":"2022-08-16T09:41:57Z","external_id":{"arxiv":["1504.07959"]},"extern":"1","scopus_import":"1","status":"public","title":"Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs","_id":"11870","language":[{"iso":"eng"}],"publication":"46th Annual ACM Symposium on Theory of Computing","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"last_name":"Krinninger","full_name":"Krinninger, Sebastian","first_name":"Sebastian"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"}],"month":"05","publication_status":"published","date_updated":"2024-11-06T12:20:12Z","oa":1,"doi":"10.1145/2591796.2591869","conference":{"name":"STOC: Symposium on Theory of Computing","start_date":"2014-05-31","location":"New York, NY, United States","end_date":"2014-06-03"},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1504.07959"}],"type":"conference","article_number":"674 - 683","publication_identifier":{"isbn":["978-145032710-7"],"issn":["0737-8017"]},"article_processing_charge":"No","publisher":"Association for Computing Machinery","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Henzinger M, Krinninger S, Nanongkai D. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In: <i>46th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2014. doi:<a href=\"https://doi.org/10.1145/2591796.2591869\">10.1145/2591796.2591869</a>","short":"M. Henzinger, S. Krinninger, D. Nanongkai, in:, 46th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2014.","mla":"Henzinger, Monika, et al. “Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs.” <i>46th Annual ACM Symposium on Theory of Computing</i>, 674–683, Association for Computing Machinery, 2014, doi:<a href=\"https://doi.org/10.1145/2591796.2591869\">10.1145/2591796.2591869</a>.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2014. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. 46th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 674–683.","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs,” in <i>46th Annual ACM Symposium on Theory of Computing</i>, New York, NY, United States, 2014.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2014). Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In <i>46th Annual ACM Symposium on Theory of Computing</i>. New York, NY, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2591796.2591869\">https://doi.org/10.1145/2591796.2591869</a>","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs.” In <i>46th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery, 2014. <a href=\"https://doi.org/10.1145/2591796.2591869\">https://doi.org/10.1145/2591796.2591869</a>."},"date_published":"2014-05-01T00:00:00Z","day":"01","arxiv":1,"quality_controlled":"1"}]