[{"OA_place":"publisher","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_number":"5","year":"2026","corr_author":"1","type":"journal_article","citation":{"short":"M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).","ama":"Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs. <i>Combinatorica</i>. 2026;46. doi:<a href=\"https://doi.org/10.1007/s00493-025-00194-8\">10.1007/s00493-025-00194-8</a>","ista":"Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 46, 5.","ieee":"M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in Dirac hypergraphs,” <i>Combinatorica</i>, vol. 46. Springer Nature, 2026.","mla":"Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.” <i>Combinatorica</i>, vol. 46, 5, Springer Nature, 2026, doi:<a href=\"https://doi.org/10.1007/s00493-025-00194-8\">10.1007/s00493-025-00194-8</a>.","apa":"Kwan, M. A., Safavi Hemami, R., &#38; Wang, Y. (2026). Counting perfect matchings in Dirac hypergraphs. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-025-00194-8\">https://doi.org/10.1007/s00493-025-00194-8</a>","chicago":"Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting Perfect Matchings in Dirac Hypergraphs.” <i>Combinatorica</i>. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/s00493-025-00194-8\">https://doi.org/10.1007/s00493-025-00194-8</a>."},"ddc":["510"],"date_created":"2026-02-08T23:02:49Z","file":[{"file_id":"21228","content_type":"application/pdf","success":1,"file_name":"2026_Combinatorica_Kwan.pdf","date_updated":"2026-02-16T09:52:38Z","relation":"main_file","access_level":"open_access","creator":"dernst","file_size":539646,"checksum":"47b0031d90b0e6b9a843f422a1486089","date_created":"2026-02-16T09:52:38Z"}],"publication":"Combinatorica","arxiv":1,"day":"01","scopus_import":"1","doi":"10.1007/s00493-025-00194-8","oa":1,"abstract":[{"text":"One of the foundational theorems of extremal graph theory is Dirac’s theorem, which\r\nsays that if an n-vertex graph G has minimum degree at least n/2, then G has a\r\nHamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy,\r\nSelkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles\r\nand perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise\r\ndescription of the numbers of Hamilton cycles and perfect matchings in a Dirac graph\r\nG (in terms of an entropy-like parameter of G). In this paper we extend Cuckler\r\nand Kahn’s result to perfect matchings in hypergraphs. For positive integers d < k,\r\nand for n divisible by k, let md (k, n) be the minimum d-degree that ensures the\r\nexistence of a perfect matching in an n-vertex k-uniform hypergraph. In general, it is\r\nan open question to determine (even asymptotically) the values of md (k, n), but we are\r\nnonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if\r\nan n-vertex k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n)\r\n(for any constantγ > 0), then the number of perfect matchings in G is controlled by\r\nan entropy-like parameter of G. This strengthens cruder estimates arising from work\r\nof Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.","lang":"eng"}],"author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan"},{"first_name":"Roodabeh","full_name":"Safavi Hemami, Roodabeh","last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154"},{"orcid":"0000-0002-2856-767X","first_name":"Yiting","full_name":"Wang, Yiting","id":"1917d194-076e-11ed-97cd-837255f88785","last_name":"Wang"}],"file_date_updated":"2026-02-16T09:52:38Z","intvolume":"        46","license":"https://creativecommons.org/licenses/by/4.0/","_id":"21159","language":[{"iso":"eng"}],"article_type":"original","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"OA_type":"hybrid","PlanS_conform":"1","month":"02","volume":46,"acknowledgement":"We would like to thank the referees for a number of helpful comments and suggestions, which have substantially improved the paper. Open access funding provided by Institute of Science and Technology (IST Austria).","quality_controlled":"1","status":"public","oa_version":"Published Version","department":[{"_id":"MaKw"},{"_id":"MoHe"}],"publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"date_published":"2026-02-01T00:00:00Z","publication_status":"published","date_updated":"2026-02-16T09:55:17Z","external_id":{"arxiv":["2408.09589"]},"publisher":"Springer Nature","title":"Counting perfect matchings in Dirac hypergraphs","article_processing_charge":"Yes (via OA deal)"},{"author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh","last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154"},{"first_name":"Salil","full_name":"Vadhan, Salil","last_name":"Vadhan"}],"file_date_updated":"2026-07-16T09:09:53Z","intvolume":"         4","_id":"22318","das_tickbox":"0","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"article_type":"original","supplementarymaterial":"no","OA_type":"gold","PlanS_conform":"1","month":"06","volume":4,"researchdata_availability":"no","acknowledgement":"1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi were supported by the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564), and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982, and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic copyright license to any author-accepted manuscript version arising from this submission.\r\nViews and opinions expressed are however those of the author(s)\r\nonly and do not necessarily reflect those of the European Union\r\nor the European Research Council Executive Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible for them.","quality_controlled":"1","status":"public","oa_version":"Published Version","department":[{"_id":"MoHe"}],"date_published":"2026-06-01T00:00:00Z","publication_identifier":{"issn":["2836-6573"]},"ec_funded":1,"publication_status":"published","date_updated":"2026-07-16T09:14:49Z","external_id":{"arxiv":["2411.03299"]},"title":"Concurrent composition for differentially private continual mechanisms","publisher":"Association for Computing Machinery","article_processing_charge":"Yes","OA_place":"publisher","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["differential privacy","concurrent composition","continual release","continual observation","data streaming","continual mechanisms","concurrent parallel composition","concurrent filter composition"],"year":"2026","corr_author":"1","type":"journal_article","citation":{"ista":"Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2), 1–26.","short":"M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26.","ama":"Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially private continual mechanisms. <i>Proceedings of the ACM on Management of Data</i>. 2026;4(2):1-26. doi:<a href=\"https://doi.org/10.1145/3801895\">10.1145/3801895</a>","chicago":"Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent Composition for Differentially Private Continual Mechanisms.” <i>Proceedings of the ACM on Management of Data</i>. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3801895\">https://doi.org/10.1145/3801895</a>.","apa":"Henzinger, M., Safavi Hemami, R., &#38; Vadhan, S. (2026). Concurrent composition for differentially private continual mechanisms. <i>Proceedings of the ACM on Management of Data</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3801895\">https://doi.org/10.1145/3801895</a>","ieee":"M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for differentially private continual mechanisms,” <i>Proceedings of the ACM on Management of Data</i>, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026.","mla":"Henzinger, Monika, et al. “Concurrent Composition for Differentially Private Continual Mechanisms.” <i>Proceedings of the ACM on Management of Data</i>, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:<a href=\"https://doi.org/10.1145/3801895\">10.1145/3801895</a>."},"ddc":["000"],"date_created":"2026-07-13T14:59:14Z","issue":"2","file":[{"file_size":655405,"checksum":"c6c5e256d02b90682c0690c3bee94040","date_created":"2026-07-16T09:09:53Z","access_level":"open_access","relation":"main_file","creator":"dernst","success":1,"file_name":"2026_ACMMgmtData_Henzinger.pdf","date_updated":"2026-07-16T09:09:53Z","content_type":"application/pdf","file_id":"22345"}],"publication":"Proceedings of the ACM on Management of Data","arxiv":1,"page":"1-26","day":"01","doi":"10.1145/3801895","scopus_import":"1","oa":1,"project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"}],"abstract":[{"text":"Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously\r\nover a long period of time, making more statistical releases as either queries come in or the dataset is updated.\r\nIn this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion\r\nof neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries\r\nand dataset updates to the different composed mechanisms. Previous concurrent composition theorems for\r\ndifferential privacy were only for the case when the dataset is static, with no adaptive updates. We also give\r\nthe first interactive and continual generalizations of the “parallel composition theorem” for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem\r\nholds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential privacy, but it fails to hold for composing approximately differentially private mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent\r\nfilter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend these results to other measures of differential privacy, including Rényi DP and 𝑓 -DP.\r\nWe then formalize a set of general conditions on a continual mechanism M that runs multiple continual submechanisms such that the privacy guarantees of M follow directly using the above concurrent composition\r\ntheorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.\r\nWe also provide a framework that simplifies the analysis of local differential privacy when the protocol\r\nincludes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5].","lang":"eng"}]},{"has_accepted_license":"1","conference":{"location":"Warsaw, Poland","name":"ESA: European Symposium on Algorithms","start_date":"2025-09-15","end_date":"2025-09-17"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","citation":{"ista":"Henzinger M, Safavi Hemami R. 2025. Securing dynamic data: A primer on differentially private data structures. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 351, 2.","short":"M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ama":"Henzinger M, Safavi Hemami R. Securing dynamic data: A primer on differentially private data structures. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>","ieee":"M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially private data structures,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","mla":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>.","chicago":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>.","apa":"Henzinger, M., &#38; Safavi Hemami, R. (2025). Securing dynamic data: A primer on differentially private data structures. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>"},"article_number":"2","alternative_title":["LIPIcs"],"corr_author":"1","year":"2025","type":"conference","publication":"33rd Annual European Symposium on Algorithms","file":[{"file_id":"20541","content_type":"application/pdf","success":1,"file_name":"2025_LIPIcs.ESA_Henzinger.pdf","date_updated":"2025-10-27T07:57:00Z","access_level":"open_access","relation":"main_file","creator":"dernst","file_size":770227,"checksum":"094e0466d90664fbea397b469a60acbb","date_created":"2025-10-27T07:57:00Z"}],"ddc":["000"],"date_created":"2025-10-26T23:01:34Z","abstract":[{"text":"We give an introduction into differential privacy in the dynamic setting, called the continual observation setting.","lang":"eng"}],"day":"01","scopus_import":"1","doi":"10.4230/LIPIcs.ESA.2025.2","oa":1,"_id":"20533","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh"}],"intvolume":"       351","file_date_updated":"2025-10-27T07:57:00Z","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"OA_type":"gold","quality_controlled":"1","status":"public","month":"10","volume":351,"title":"Securing dynamic data: A primer on differentially private data structures","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"No","oa_version":"Published Version","date_published":"2025-10-01T00:00:00Z","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773959"]},"department":[{"_id":"MoHe"}],"publication_status":"published","date_updated":"2025-10-27T08:00:13Z"},{"project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"abstract":[{"lang":"eng","text":"Uniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called \"strongly history independent\" structures in the literature.\r\nWe introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2].\r\nThus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound."}],"scopus_import":"1","doi":"10.4230/LIPIcs.WADS.2025.47","oa":1,"arxiv":1,"day":"29","file":[{"date_updated":"2025-10-27T07:09:41Z","file_name":"2025_LIPIcs.WADS_Safavi.pdf","success":1,"file_id":"20540","content_type":"application/pdf","date_created":"2025-10-27T07:09:41Z","checksum":"196af33762831a78e87f4f95ecd8677b","file_size":1081870,"creator":"dernst","relation":"main_file","access_level":"open_access"}],"publication":"19th International Symposium on Algorithms and Data Structures","date_created":"2025-10-26T23:01:35Z","ddc":["000"],"citation":{"ieee":"R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized block search trees with high load,” in <i>19th International Symposium on Algorithms and Data Structures</i>, Toronto, Canada, 2025, vol. 349.","mla":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” <i>19th International Symposium on Algorithms and Data Structures</i>, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>.","chicago":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” In <i>19th International Symposium on Algorithms and Data Structures</i>, Vol. 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>.","apa":"Safavi Hemami, R., &#38; Seybold, M. P. (2025). B-Treaps revised: Write efficient randomized block search trees with high load. In <i>19th International Symposium on Algorithms and Data Structures</i> (Vol. 349). Toronto, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>","ista":"Safavi Hemami R, Seybold MP. 2025. B-Treaps revised: Write efficient randomized block search trees with high load. 19th International Symposium on Algorithms and Data Structures. WADS: Algorithms and Data Structures Symposium, LIPIcs, vol. 349, 47.","ama":"Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized block search trees with high load. In: <i>19th International Symposium on Algorithms and Data Structures</i>. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>","short":"R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"year":"2025","alternative_title":["LIPIcs"],"corr_author":"1","type":"conference","article_number":"47","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Toronto, Canada","name":"WADS: Algorithms and Data Structures Symposium","start_date":"2025-08-11","end_date":"2025-08-15"},"has_accepted_license":"1","OA_place":"publisher","article_processing_charge":"No","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"B-Treaps revised: Write efficient randomized block search trees with high load","publication_status":"published","date_updated":"2025-10-27T07:10:49Z","external_id":{"arxiv":["2303.04722"]},"oa_version":"Published Version","ec_funded":1,"date_published":"2025-08-29T00:00:00Z","publication_identifier":{"isbn":["9783959773980"],"issn":["1868-8969"]},"department":[{"_id":"MoHe"}],"quality_controlled":"1","status":"public","acknowledgement":"This work was supported under the Australian Research Council Discovery Projects\r\nfunding scheme (project number DP180102870). This project has received funding from the\r\nEuropean Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project Z 422-N and project “Fast Algorithms for a Reactive Network Layer (ReactNet)” P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","volume":349,"month":"08","OA_type":"gold","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"_id":"20536","intvolume":"       349","file_date_updated":"2025-10-27T07:09:41Z","author":[{"first_name":"Roodabeh","full_name":"Safavi Hemami, Roodabeh","last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154"},{"first_name":"Martin P.","full_name":"Seybold, Martin P.","last_name":"Seybold"}]},{"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"author":[{"last_name":"Ahmadi","first_name":"Ali","full_name":"Ahmadi, Ali"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Amir Kafshdar","full_name":"Goharshady, Amir Kafshdar","orcid":"0000-0003-1702-6584","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Meggendorfer","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165"},{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","last_name":"Safavi Hemami","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh"},{"last_name":"Zikelic","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","first_name":"Dorde","full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699"}],"intvolume":"       250","file_date_updated":"2023-01-20T10:39:44Z","_id":"12102","oa_version":"Published Version","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"ec_funded":1,"publication_identifier":{"isbn":["9783959772617"],"issn":["1868-8969"]},"date_published":"2022-12-14T00:00:00Z","publication_status":"published","date_updated":"2025-07-10T11:50:23Z","title":"Algorithms and hardness results for computing cores of Markov chains","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"No","month":"12","volume":250,"acknowledgement":"The research was partially supported by the Hong Kong Research Grants Council ECS\r\nProject No. 26208122, ERC CoG 863818 (FoRM-SMArt), the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385, HKUST– Kaisa Joint Research Institute Project Grant HKJRI3A-055 and HKUST Startup Grant R9272. Ali Ahmadi and Roodabeh Safavi were interns at HKUST.","quality_controlled":"1","status":"public","article_number":"29","year":"2022","corr_author":"1","type":"conference","citation":{"ista":"Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic D. 2022. Algorithms and hardness results for computing cores of Markov chains. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science vol. 250, 29.","ama":"Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic D. Algorithms and hardness results for computing cores of Markov chains. In: <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">10.4230/LIPIcs.FSTTCS.2022.29</a>","short":"A. Ahmadi, K. Chatterjee, A.K. Goharshady, T. Meggendorfer, R. Safavi Hemami, D. Zikelic, in:, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","mla":"Ahmadi, Ali, et al. “Algorithms and Hardness Results for Computing Cores of Markov Chains.” <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 250, 29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">10.4230/LIPIcs.FSTTCS.2022.29</a>.","ieee":"A. Ahmadi, K. Chatterjee, A. K. Goharshady, T. Meggendorfer, R. Safavi Hemami, and D. Zikelic, “Algorithms and hardness results for computing cores of Markov chains,” in <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Madras, India, 2022, vol. 250.","apa":"Ahmadi, A., Chatterjee, K., Goharshady, A. K., Meggendorfer, T., Safavi Hemami, R., &#38; Zikelic, D. (2022). Algorithms and hardness results for computing cores of Markov chains. In <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 250). Madras, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>","chicago":"Ahmadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi Hemami, and Dorde Zikelic. “Algorithms and Hardness Results for Computing Cores of Markov Chains.” In <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>."},"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Madras, India","end_date":"2022-12-20","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","start_date":"2022-12-18"},"day":"14","scopus_import":"1","doi":"10.4230/LIPIcs.FSTTCS.2022.29","oa":1,"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","grant_number":"665385","call_identifier":"H2020"}],"abstract":[{"text":"Given a Markov chain M = (V, v_0, δ), with state space V and a starting state v_0, and a probability threshold ε, an ε-core is a subset C of states that is left with probability at most ε. More formally, C ⊆ V is an ε-core, iff ℙ[reach (V\\C)] ≤ ε. Cores have been applied in a wide variety of verification problems over Markov chains, Markov decision processes, and probabilistic programs, as a means of discarding uninteresting and low-probability parts of a probabilistic system and instead being able to focus on the states that are likely to be encountered in a real-world run. In this work, we focus on the problem of computing a minimal ε-core in a Markov chain. Our contributions include both negative and positive results: (i) We show that the decision problem on the existence of an ε-core of a given size is NP-complete. This solves an open problem posed in [Jan Kretínský and Tobias Meggendorfer, 2020]. We additionally show that the problem remains NP-complete even when limited to acyclic Markov chains with bounded maximal vertex degree; (ii) We provide a polynomial time algorithm for computing a minimal ε-core on Markov chains over control-flow graphs of structured programs. A straightforward combination of our algorithm with standard branch prediction techniques allows one to apply the idea of cores to find a subset of program lines that are left with low probability and then focus any desired static analysis on this core subset.","lang":"eng"}],"ddc":["000"],"date_created":"2023-01-01T23:00:50Z","publication":"42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","file":[{"creator":"dernst","access_level":"open_access","relation":"main_file","checksum":"6660c802489013f034c9e8bd57f4d46e","file_size":872534,"date_created":"2023-01-20T10:39:44Z","content_type":"application/pdf","file_id":"12324","file_name":"2022_LIPICs_Ahmadi.pdf","success":1,"date_updated":"2023-01-20T10:39:44Z"}]}]