---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '21159'
abstract:
- lang: eng
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."
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).
article_number: '5'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Yiting
full_name: Wang, Yiting
id: 1917d194-076e-11ed-97cd-837255f88785
last_name: Wang
orcid: 0000-0002-2856-767X
citation:
ama: Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs.
Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8
apa: Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings
in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8
chicago: Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting
Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature,
2026. https://doi.org/10.1007/s00493-025-00194-8.
ieee: M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in
Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 2026.
ista: Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac
hypergraphs. Combinatorica. 46, 5.
mla: Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.”
Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8.
short: M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).
corr_author: '1'
date_created: 2026-02-08T23:02:49Z
date_published: 2026-02-01T00:00:00Z
date_updated: 2026-02-16T09:55:17Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
- _id: MoHe
doi: 10.1007/s00493-025-00194-8
external_id:
arxiv:
- '2408.09589'
file:
- access_level: open_access
checksum: 47b0031d90b0e6b9a843f422a1486089
content_type: application/pdf
creator: dernst
date_created: 2026-02-16T09:52:38Z
date_updated: 2026-02-16T09:52:38Z
file_id: '21228'
file_name: 2026_Combinatorica_Kwan.pdf
file_size: 539646
relation: main_file
success: 1
file_date_updated: 2026-02-16T09:52:38Z
has_accepted_license: '1'
intvolume: ' 46'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '02'
oa: 1
oa_version: Published Version
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting perfect matchings in Dirac hypergraphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '20533'
abstract:
- lang: eng
text: We give an introduction into differential privacy in the dynamic setting,
called the continual observation setting.
alternative_title:
- LIPIcs
article_number: '2'
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
citation:
ama: 'Henzinger M, Safavi Hemami R. Securing dynamic data: A primer on differentially
private data structures. In: 33rd Annual European Symposium on Algorithms.
Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.2'
apa: 'Henzinger, M., & Safavi Hemami, R. (2025). Securing dynamic data: A primer
on differentially private data structures. In 33rd Annual European Symposium
on Algorithms (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.2'
chicago: 'Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data:
A Primer on Differentially Private Data Structures.” In 33rd Annual European
Symposium on Algorithms, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.2.'
ieee: 'M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially
private data structures,” in 33rd Annual European Symposium on Algorithms,
Warsaw, Poland, 2025, vol. 351.'
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.'
mla: 'Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer
on Differentially Private Data Structures.” 33rd Annual European Symposium
on Algorithms, vol. 351, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025, doi:10.4230/LIPIcs.ESA.2025.2.'
short: M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-09-17
location: Warsaw, Poland
name: 'ESA: European Symposium on Algorithms'
start_date: 2025-09-15
corr_author: '1'
date_created: 2025-10-26T23:01:34Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2025-10-27T08:00:13Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2025.2
file:
- access_level: open_access
checksum: 094e0466d90664fbea397b469a60acbb
content_type: application/pdf
creator: dernst
date_created: 2025-10-27T07:57:00Z
date_updated: 2025-10-27T07:57:00Z
file_id: '20541'
file_name: 2025_LIPIcs.ESA_Henzinger.pdf
file_size: 770227
relation: main_file
success: 1
file_date_updated: 2025-10-27T07:57:00Z
has_accepted_license: '1'
intvolume: ' 351'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: 33rd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773959'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Securing dynamic data: A primer on differentially private data structures'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 351
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20536'
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."
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."
alternative_title:
- LIPIcs
article_number: '47'
article_processing_charge: No
arxiv: 1
author:
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Martin P.
full_name: Seybold, Martin P.
last_name: Seybold
citation:
ama: 'Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized
block search trees with high load. In: 19th International Symposium on Algorithms
and Data Structures. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2025. doi:10.4230/LIPIcs.WADS.2025.47'
apa: 'Safavi Hemami, R., & Seybold, M. P. (2025). B-Treaps revised: Write efficient
randomized block search trees with high load. In 19th International Symposium
on Algorithms and Data Structures (Vol. 349). Toronto, Canada: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.WADS.2025.47'
chicago: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write
Efficient Randomized Block Search Trees with High Load.” In 19th International
Symposium on Algorithms and Data Structures, Vol. 349. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.WADS.2025.47.'
ieee: 'R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized
block search trees with high load,” in 19th International Symposium on Algorithms
and Data Structures, Toronto, Canada, 2025, vol. 349.'
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.'
mla: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient
Randomized Block Search Trees with High Load.” 19th International Symposium
on Algorithms and Data Structures, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, doi:10.4230/LIPIcs.WADS.2025.47.'
short: R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms
and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-08-15
location: Toronto, Canada
name: 'WADS: Algorithms and Data Structures Symposium'
start_date: 2025-08-11
corr_author: '1'
date_created: 2025-10-26T23:01:35Z
date_published: 2025-08-29T00:00:00Z
date_updated: 2025-10-27T07:10:49Z
day: '29'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.WADS.2025.47
ec_funded: 1
external_id:
arxiv:
- '2303.04722'
file:
- access_level: open_access
checksum: 196af33762831a78e87f4f95ecd8677b
content_type: application/pdf
creator: dernst
date_created: 2025-10-27T07:09:41Z
date_updated: 2025-10-27T07:09:41Z
file_id: '20540'
file_name: 2025_LIPIcs.WADS_Safavi.pdf
file_size: 1081870
relation: main_file
success: 1
file_date_updated: 2025-10-27T07:09:41Z
has_accepted_license: '1'
intvolume: ' 349'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: 19th International Symposium on Algorithms and Data Structures
publication_identifier:
isbn:
- '9783959773980'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'B-Treaps revised: Write efficient randomized block search trees with high
load'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 349
year: '2025'
...
---
_id: '12102'
abstract:
- lang: eng
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.'
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."
article_number: '29'
article_processing_charge: No
author:
- first_name: Ali
full_name: Ahmadi, Ali
last_name: Ahmadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
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: 42nd
IARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.FSTTCS.2022.29'
apa: 'Ahmadi, A., Chatterjee, K., Goharshady, A. K., Meggendorfer, T., Safavi Hemami,
R., & Zikelic, D. (2022). Algorithms and hardness results for computing cores
of Markov chains. In 42nd IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (Vol. 250). Madras, India: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29'
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 42nd IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, Vol. 250. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29.
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 42nd IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, Madras, India, 2022, vol. 250.
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.'
mla: Ahmadi, Ali, et al. “Algorithms and Hardness Results for Computing Cores of
Markov Chains.” 42nd IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, vol. 250, 29, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022, doi:10.4230/LIPIcs.FSTTCS.2022.29.
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.
conference:
end_date: 2022-12-20
location: Madras, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2022-12-18
corr_author: '1'
date_created: 2023-01-01T23:00:50Z
date_published: 2022-12-14T00:00:00Z
date_updated: 2025-07-10T11:50:23Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
doi: 10.4230/LIPIcs.FSTTCS.2022.29
ec_funded: 1
file:
- access_level: open_access
checksum: 6660c802489013f034c9e8bd57f4d46e
content_type: application/pdf
creator: dernst
date_created: 2023-01-20T10:39:44Z
date_updated: 2023-01-20T10:39:44Z
file_id: '12324'
file_name: 2022_LIPICs_Ahmadi.pdf
file_size: 872534
relation: main_file
success: 1
file_date_updated: 2023-01-20T10:39:44Z
has_accepted_license: '1'
intvolume: ' 250'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: 42nd IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- '9783959772617'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithms and hardness results for computing cores of Markov chains
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 250
year: '2022'
...