@article{21159, abstract = {One of the foundational theorems of extremal graph theory is Dirac’s theorem, which says that if an n-vertex graph G has minimum degree at least n/2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy, Selkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles and perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise description of the numbers of Hamilton cycles and perfect matchings in a Dirac graph G (in terms of an entropy-like parameter of G). In this paper we extend Cuckler and Kahn’s result to perfect matchings in hypergraphs. For positive integers d < k, and for n divisible by k, let md (k, n) be the minimum d-degree that ensures the existence of a perfect matching in an n-vertex k-uniform hypergraph. In general, it is an open question to determine (even asymptotically) the values of md (k, n), but we are nonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if an n-vertex k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n) (for any constantγ > 0), then the number of perfect matchings in G is controlled by an entropy-like parameter of G. This strengthens cruder estimates arising from work of Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.}, author = {Kwan, Matthew Alan and Safavi Hemami, Roodabeh and Wang, Yiting}, issn = {1439-6912}, journal = {Combinatorica}, publisher = {Springer Nature}, title = {{Counting perfect matchings in Dirac hypergraphs}}, doi = {10.1007/s00493-025-00194-8}, volume = {46}, year = {2026}, } @inproceedings{20533, abstract = {We give an introduction into differential privacy in the dynamic setting, called the continual observation setting.}, author = {Henzinger, Monika H and Safavi Hemami, Roodabeh}, booktitle = {33rd Annual European Symposium on Algorithms}, isbn = {9783959773959}, issn = {1868-8969}, location = {Warsaw, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Securing dynamic data: A primer on differentially private data structures}}, doi = {10.4230/LIPIcs.ESA.2025.2}, volume = {351}, year = {2025}, } @inproceedings{20536, abstract = {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. We 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]. Thus (α, ε)-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.}, author = {Safavi Hemami, Roodabeh and Seybold, Martin P.}, booktitle = {19th International Symposium on Algorithms and Data Structures}, isbn = {9783959773980}, issn = {1868-8969}, location = {Toronto, Canada}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{B-Treaps revised: Write efficient randomized block search trees with high load}}, doi = {10.4230/LIPIcs.WADS.2025.47}, volume = {349}, year = {2025}, } @inproceedings{12102, abstract = {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.}, author = {Ahmadi, Ali and Chatterjee, Krishnendu and Goharshady, Amir Kafshdar and Meggendorfer, Tobias and Safavi Hemami, Roodabeh and Zikelic, Dorde}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {9783959772617}, issn = {1868-8969}, location = {Madras, India}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Algorithms and hardness results for computing cores of Markov chains}}, doi = {10.4230/LIPIcs.FSTTCS.2022.29}, volume = {250}, year = {2022}, }