@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},
}

@article{22318,
  abstract     = {Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously
over a long period of time, making more statistical releases as either queries come in or the dataset is updated.
In this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that
support dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion
of neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition
theorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries
and dataset updates to the different composed mechanisms. Previous concurrent composition theorems for
differential privacy were only for the case when the dataset is static, with no adaptive updates. We also give
the first interactive and continual generalizations of the “parallel composition theorem” for noninteractive
differential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem
holds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure
differential privacy, but it fails to hold for composing approximately differentially private mechanisms with
dataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent
filter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We
extend these results to other measures of differential privacy, including Rényi DP and 𝑓 -DP.
We 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
theorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular
privacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the
case of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.
We also provide a framework that simplifies the analysis of local differential privacy when the protocol
includes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core
decomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5].},
  author       = {Henzinger, Monika H and Safavi Hemami, Roodabeh and Vadhan, Salil},
  issn         = {2836-6573},
  journal      = {Proceedings of the ACM on Management of Data},
  keywords     = {differential privacy, concurrent composition, continual release, continual observation, data streaming, continual mechanisms, concurrent parallel composition, concurrent filter composition},
  number       = {2},
  pages        = {1--26},
  publisher    = {Association for Computing Machinery},
  title        = {{Concurrent composition for differentially private continual mechanisms}},
  doi          = {10.1145/3801895},
  volume       = {4},
  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},
}