---
OA_place: publisher
OA_type: gold
_id: '19858'
abstract:
- lang: eng
text: "Given a graph G that undergoes a sequence of edge insertions and deletions,
we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different
colors, color as many edges of G as possible such that no two adjacent edges share
the same color. While this problem is different from simply maintaining a b-matching
with b = k, the two problems are related. However, maximum b-matching can be solved
efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for
k ≥ 2. \r\nWe present new results on both problems: For b-matching, we show a
new integrality gap result and we adapt Wajc’s matching sparsification scheme
[David Wajc, 2020] for the case where b is a constant.\r\nUsing these as basis,
we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm
builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and
Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation
in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA
algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya,
Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching
and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update
time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching
algorithm as a black box, so any future improvement in the approximation ratio
for dynamic b-matching will automatically translate into a better approximation
ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update
time, which guarantees a 2.16 approximation factor."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the\r\nEuropean Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422,
grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding
from the netidee SCIENCE Stiftung, 2020–2024. This work was further supported by
the Federal Ministry of Education and Research (BMBF) project, 6G-RIC: 6G Research
and Innovation Cluster, grant 16KISK020K."
alternative_title:
- LIPIcs
article_number: '4'
article_processing_charge: No
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- first_name: Kathrin
full_name: Hanauer, Kathrin
last_name: Hanauer
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum
k-edge coloring. In: 4th Symposium on Algorithmic Foundations of Dynamic Networks.
Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SAND.2025.4'
apa: 'El-Hayek, A., Hanauer, K., & Henzinger, M. (2025). On b-matching and fully-dynamic
maximum k-edge coloring. In 4th Symposium on Algorithmic Foundations of Dynamic
Networks (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2025.4'
chicago: El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching
and Fully-Dynamic Maximum k-Edge Coloring.” In 4th Symposium on Algorithmic
Foundations of Dynamic Networks, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SAND.2025.4.
ieee: A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic
maximum k-edge coloring,” in 4th Symposium on Algorithmic Foundations of Dynamic
Networks, Liverpool, United Kingdom, 2025, vol. 330.
ista: 'El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic
maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks.
SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330,
4.'
mla: El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.”
4th Symposium on Algorithmic Foundations of Dynamic Networks, vol. 330,
4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SAND.2025.4.
short: A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic
Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025.
conference:
end_date: 2025-06-11
location: Liverpool, United Kingdom
name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
start_date: 2025-06-09
corr_author: '1'
date_created: 2025-06-22T22:02:06Z
date_published: 2025-06-02T00:00:00Z
date_updated: 2025-09-30T13:37:28Z
day: '02'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.SAND.2025.4
ec_funded: 1
external_id:
arxiv:
- '2310.01149'
isi:
- '001532136900004'
file:
- access_level: open_access
checksum: ad93a1e052adb29d7bfe8bd551bab193
content_type: application/pdf
creator: dernst
date_created: 2025-06-23T11:23:29Z
date_updated: 2025-06-23T11:23:29Z
file_id: '19872'
file_name: 2025_LIPIcs_ElHayek.pdf
file_size: 995666
relation: main_file
success: 1
file_date_updated: 2025-06-23T11:23:29Z
has_accepted_license: '1'
intvolume: ' 330'
isi: 1
language:
- iso: eng
month: '06'
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: 4th Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
isbn:
- '9783959773683'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: On b-matching and fully-dynamic maximum k-edge coloring
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 330
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20253'
abstract:
- lang: eng
text: "A quantitative word automaton (QWA) defines a function from infinite words
to values. For example, every infinite run of a limit-average QWA \U0001D49C obtains
a mean payoff, and every word w ∈ Σ^ω is assigned the maximal mean payoff obtained
by nondeterministic runs of \U0001D49C over w. We introduce quantitative language
automata (QLAs) that define functions from language generators (i.e., implementations)
to values, where a language generator can be nonprobabilistic, defining a set
of infinite words, or probabilistic, defining a probability measure over infinite
words. A QLA consists of a QWA and an aggregator function. For example, given
a QWA \U0001D49C, the infimum aggregator maps each language L ⊆ Σ^ω to the greatest
lower bound assigned by \U0001D49C to any word in L. For boolean value sets, QWAs
define boolean properties of traces, and QLAs define boolean properties of sets
of traces, i.e., hyperproperties. For more general value sets, QLAs serve as a
specification language for a generalization of hyperproperties, called quantitative
hyperproperties. A nonprobabilistic (resp. probabilistic) quantitative hyperproperty
assigns a value to each set (resp. distribution) G of traces, e.g., the minimal
(resp. expected) average response time exhibited by the traces in G. We give several
examples of quantitative hyperproperties and investigate three paradigmatic problems
for QLAs: evaluation, nonemptiness, and universality. In the evaluation problem,
given a QLA \U0001D538 and an implementation G, we ask for the value that \U0001D538
assigns to G. In the nonemptiness (resp. universality) problem, given a QLA \U0001D538
and a value k, we ask whether \U0001D538 assigns at least k to some (resp. every)
language. We provide a comprehensive picture of decidability for these problems
for QLAs with common aggregators as well as their restrictions to ω-regular languages
and trace distributions generated by finite-state Markov chains."
acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093.
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Pavol
full_name: Kebis, Pavol
id: 2e0132b3-4e98-11ef-b275-cf7281c2802a
last_name: Kebis
- first_name: Nicolas Adrien
full_name: Mazzocchi, Nicolas Adrien
id: b26baa86-3308-11ec-87b0-8990f34baa85
last_name: Mazzocchi
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
citation:
ama: 'Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Quantitative language automata.
In: 36th International Conference on Concurrency Theory. Vol 348. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.CONCUR.2025.21'
apa: 'Henzinger, T. A., Kebis, P., Mazzocchi, N. A., & Sarac, N. E. (2025).
Quantitative language automata. In 36th International Conference on Concurrency
Theory (Vol. 348). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2025.21'
chicago: Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E
Sarac. “Quantitative Language Automata.” In 36th International Conference on
Concurrency Theory, Vol. 348. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.CONCUR.2025.21.
ieee: T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Quantitative
language automata,” in 36th International Conference on Concurrency Theory,
Aarhus, Denmark, 2025, vol. 348.
ista: 'Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. 2025. Quantitative language
automata. 36th International Conference on Concurrency Theory. CONCUR: Conference
on Concurrency Theory, LIPIcs, vol. 348, 21.'
mla: Henzinger, Thomas A., et al. “Quantitative Language Automata.” 36th International
Conference on Concurrency Theory, vol. 348, 21, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, doi:10.4230/LIPIcs.CONCUR.2025.21.
short: T.A. Henzinger, P. Kebis, N.A. Mazzocchi, N.E. Sarac, in:, 36th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025.
conference:
end_date: 2025-08-29
location: Aarhus, Denmark
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2025-08-26
corr_author: '1'
date_created: 2025-08-31T22:01:32Z
date_published: 2025-08-18T00:00:00Z
date_updated: 2025-12-01T12:36:52Z
day: '18'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2025.21
ec_funded: 1
external_id:
arxiv:
- '2506.0515'
isi:
- '001570540800021'
file:
- access_level: open_access
checksum: 9d4054058757a73477e6015b10ed6996
content_type: application/pdf
creator: dernst
date_created: 2025-09-03T10:01:53Z
date_updated: 2025-09-03T10:01:53Z
file_id: '20282'
file_name: 2025_CONCUR_HenzingerT.pdf
file_size: 1257397
relation: main_file
success: 1
file_date_updated: 2025-09-03T10:01:53Z
has_accepted_license: '1'
intvolume: ' 348'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 36th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959773898'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Quantitative language automata
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: 348
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20290'
abstract:
- lang: eng
text: 'We consider equilibria in multiplayer stochastic graph games with terminal-node
rewards. In such games, Nash equilibria are defined assuming that each player
seeks to maximise their expected payoff, ignoring their aversion or tolerance
to risk. We therefore study risk-sensitive equilibria (RSEs), where the expected
payoff is replaced by a risk measure. A classical risk measure in the literature
is the entropic risk measure, where each player has a real valued parameter capturing
their risk-averseness. We introduce the extreme risk measure, which corresponds
to extreme cases of entropic risk measure, where players are either extreme optimists
or extreme pessimists. Under extreme risk measure, every player is an extremist:
an extreme optimist perceives their reward as the maximum payoff that can be achieved
with positive probability, while an extreme pessimist expects the minimum payoff
achievable with positive probability. We argue that the extreme risk measure,
especially in multi-player graph based settings, is particularly relevant as they
can model several real life instances such as interactions between secure systems
and potential security threats, or distributed controls for safety critical systems.
We prove that RSEs defined with the extreme risk measure are guaranteed to exist
when all rewards are non-negative. Furthermore, we prove that the problem of deciding
whether a given game contains an RSE that generates risk measures within specified
intervals is decidable and NP-complete for our extreme risk measure, and even
PTIME-complete when all players are extreme optimists, while that same problem
is undecidable using the entropic risk measure or even the classical expected
payoff. This establishes, to our knowledge, the first decidable fragment for equilibria
in simple stochastic games without restrictions on strategy types or number of
players.'
acknowledgement: "This work is a part of project VAMOS that has received funding from
the European\r\nResearch Council (ERC), grant agreement No 101020093. We thank anonymous
reviewers for pointing us to the Hurwicz criterion and to the work of Gallego-Hernández
and Mansutti [13]. We thank Marie van den Bogaard for her valuable feedback on the
first author’s PhD dissertation, which helped improve the quality of this work. "
alternative_title:
- LIPIcs
article_number: '30'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Léonard
full_name: Brice, Léonard
last_name: Brice
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: K. S.
full_name: Thejaswini, K. S.
id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753
last_name: Thejaswini
citation:
ama: 'Brice L, Henzinger TA, Thejaswini KS. Finding equilibria: Simpler for pessimists,
simplest for optimists. In: 50th International Symposium on Mathematical Foundations
of Computer Science. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2025. doi:10.4230/LIPIcs.MFCS.2025.30'
apa: 'Brice, L., Henzinger, T. A., & Thejaswini, K. S. (2025). Finding equilibria:
Simpler for pessimists, simplest for optimists. In 50th International Symposium
on Mathematical Foundations of Computer Science (Vol. 345). Warsaw, Poland:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2025.30'
chicago: 'Brice, Léonard, Thomas A Henzinger, and K. S. Thejaswini. “Finding Equilibria:
Simpler for Pessimists, Simplest for Optimists.” In 50th International Symposium
on Mathematical Foundations of Computer Science, Vol. 345. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.MFCS.2025.30.'
ieee: 'L. Brice, T. A. Henzinger, and K. S. Thejaswini, “Finding equilibria: Simpler
for pessimists, simplest for optimists,” in 50th International Symposium on
Mathematical Foundations of Computer Science, Warsaw, Poland, 2025, vol. 345.'
ista: 'Brice L, Henzinger TA, Thejaswini KS. 2025. Finding equilibria: Simpler for
pessimists, simplest for optimists. 50th International Symposium on Mathematical
Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science,
LIPIcs, vol. 345, 30.'
mla: 'Brice, Léonard, et al. “Finding Equilibria: Simpler for Pessimists, Simplest
for Optimists.” 50th International Symposium on Mathematical Foundations of
Computer Science, vol. 345, 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025, doi:10.4230/LIPIcs.MFCS.2025.30.'
short: L. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 50th International Symposium
on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025.
conference:
end_date: 2025-08-29
location: Warsaw, Poland
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2025-08-25
corr_author: '1'
date_created: 2025-09-07T22:01:32Z
date_published: 2025-08-20T00:00:00Z
date_updated: 2025-09-08T07:15:40Z
day: '20'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2025.30
ec_funded: 1
external_id:
arxiv:
- '2502.0531'
file:
- access_level: open_access
checksum: 9bc6b8e537662d371d2a27444cbc0b75
content_type: application/pdf
creator: dernst
date_created: 2025-09-08T07:11:12Z
date_updated: 2025-09-08T07:11:12Z
file_id: '20306'
file_name: 2025_MFCS_Brice.pdf
file_size: 1149694
relation: main_file
success: 1
file_date_updated: 2025-09-08T07:11:12Z
has_accepted_license: '1'
intvolume: ' 345'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 50th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- '9783959773881'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Finding equilibria: Simpler for pessimists, simplest for optimists'
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: 345
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20291'
abstract:
- lang: eng
text: "We define and study classes of ω-regular automata for which the nondeterminism
can be resolved by a policy that uses a combination of memory and randomness on
any input word, based solely on the prefix read so far. We examine two settings
for providing the input word to an automaton. In the first setting, called adversarial
resolvability, the input word is constructed letter-by-letter by an adversary,
dependent on the resolver’s previous decisions. In the second setting, called
stochastic resolvability, the adversary pre-commits to an infinite word and reveals
it letter-by-letter. In each setting, we require the existence of an almost-sure
resolver, i.e., a policy that ensures that as long as the adversary provides a
word in the language of the underlying nondeterministic automaton, the run constructed
by the policy is accepting with probability 1.\r\nThe class of automata that are
adversarially resolvable is the well-studied class of history-deterministic automata.
The case of stochastically resolvable automata, on the other hand, defines a novel
class. Restricting the class of resolvers in both settings to stochastic policies
without memory introduces two additional new classes of automata. We show that
the new automata classes offer interesting trade-offs between succinctness, expressivity,
and computational complexity, providing a fine gradation between deterministic
automata and nondeterministic automata."
acknowledgement: This work is a part of project VAMOS that has received funding from
the European Research Council (ERC), grant agreement No 101020093.
alternative_title:
- LIPIcs
article_number: '57'
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Aditya
full_name: Prakash, Aditya
last_name: Prakash
- first_name: K. S.
full_name: Thejaswini, K. S.
id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753
last_name: Thejaswini
citation:
ama: 'Henzinger TA, Prakash A, Thejaswini KS. Resolving nondeterminism with randomness.
In: 50th International Symposium on Mathematical Foundations of Computer Science.
Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.MFCS.2025.57'
apa: 'Henzinger, T. A., Prakash, A., & Thejaswini, K. S. (2025). Resolving nondeterminism
with randomness. In 50th International Symposium on Mathematical Foundations
of Computer Science (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2025.57'
chicago: Henzinger, Thomas A, Aditya Prakash, and K. S. Thejaswini. “Resolving Nondeterminism
with Randomness.” In 50th International Symposium on Mathematical Foundations
of Computer Science, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.MFCS.2025.57.
ieee: T. A. Henzinger, A. Prakash, and K. S. Thejaswini, “Resolving nondeterminism
with randomness,” in 50th International Symposium on Mathematical Foundations
of Computer Science, Warsaw, Poland, 2025, vol. 345.
ista: 'Henzinger TA, Prakash A, Thejaswini KS. 2025. Resolving nondeterminism with
randomness. 50th International Symposium on Mathematical Foundations of Computer
Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 345,
57.'
mla: Henzinger, Thomas A., et al. “Resolving Nondeterminism with Randomness.” 50th
International Symposium on Mathematical Foundations of Computer Science, vol.
345, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.MFCS.2025.57.
short: T.A. Henzinger, A. Prakash, K.S. Thejaswini, in:, 50th International Symposium
on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025.
conference:
end_date: 2025-08-29
location: Warsaw, Poland
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2025-08-25
corr_author: '1'
date_created: 2025-09-07T22:01:32Z
date_published: 2025-08-20T00:00:00Z
date_updated: 2025-09-08T07:06:11Z
day: '20'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2025.57
ec_funded: 1
external_id:
arxiv:
- '2502.12872'
file:
- access_level: open_access
checksum: 6068b772aba6cb0d01f3e5a90abed973
content_type: application/pdf
creator: dernst
date_created: 2025-09-08T06:56:56Z
date_updated: 2025-09-08T06:56:56Z
file_id: '20305'
file_name: 2025_MFCS_HenzingerT.pdf
file_size: 1009644
relation: main_file
success: 1
file_date_updated: 2025-09-08T06:56:56Z
has_accepted_license: '1'
intvolume: ' 345'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 50th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- '9783959773881'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Resolving nondeterminism with randomness
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: 345
year: '2025'
...
---
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: '20534'
abstract:
- lang: eng
text: "A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves
all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible
data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier
upon request at any point during the sequence of updates. We employ simple dynamic
forest data structures to achieve a fast from-scratch construction of the sparsifier
at query time. Based on the strength of the adversary and desired type of time
bounds, the data structure comes with different guarantees. Specifically, let
G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our
data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case
time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that
has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees
hold against an adaptive adversary. Alternatively, the update and query times
can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees
are sufficient, or if the adversary is oblivious. Throughout the paper, we use
Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1))
factors.\r\nWe discuss two applications of our new data structure. First, it can
be used to efficiently report a cactus representation of all minimum cuts of a
fully dynamic simple graph. Building this cactus for the NMC sparsifier instead
of the original graph allows for a construction time that is sublinear in the
number of edges. Against an adaptive adversary, we can with high probability output
the cactus representation in worst-case Ô(n) time. Second, our data structure
allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected
simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier.
Specifically, we can compute with high probability the maximal k-edge-connected
subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This
improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to
the case of fully dynamic graphs."
acknowledgement: 'Monika Henzinger and Evangelos Kosinas: This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian
Science Fund (FWF) grant https://www.doi.org/10.55776/Z422 and grant https://www.doi.org/10.55776/I5982.
Harald Räcke and Robin Münk: This project has received funding from the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858.'
article_number: '36'
article_processing_charge: No
arxiv: 1
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: Evangelos
full_name: Kosinas, Evangelos
id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949
last_name: Kosinas
- first_name: Robin
full_name: Münk, Robin
last_name: Münk
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
citation:
ama: 'Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic
graphs - with applications. In: 33rd Annual European Symposium on Algorithms.
Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.36'
apa: 'Henzinger, M., Kosinas, E., Münk, R., & Räcke, H. (2025). Efficient contractions
of dynamic graphs - with applications. 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.36'
chicago: Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient
Contractions of Dynamic Graphs - with Applications.” 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.36.
ieee: M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of
dynamic graphs - with applications,” in 33rd Annual European Symposium on Algorithms,
Warsaw, Poland, 2025, vol. 351.
ista: 'Henzinger M, Kosinas E, Münk R, Räcke H. 2025. Efficient contractions of
dynamic graphs - with applications. 33rd Annual European Symposium on Algorithms.
ESA: European Symposium on Algorithms vol. 351, 36.'
mla: Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with
Applications.” 33rd Annual European Symposium on Algorithms, vol. 351,
36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ESA.2025.36.
short: M. Henzinger, E. Kosinas, R. Münk, H. Räcke, 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:05:46Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2025.36
ec_funded: 1
external_id:
arxiv:
- '2509.05157'
file:
- access_level: open_access
checksum: d2daf9a467e96fb5e7084a8a85321776
content_type: application/pdf
creator: dernst
date_created: 2025-10-27T08:03:36Z
date_updated: 2025-10-27T08:03:36Z
file_id: '20542'
file_name: 2025_LIPIcs.ESA_HenzingerM.pdf
file_size: 934846
relation: main_file
success: 1
file_date_updated: 2025-10-27T08:03:36Z
has_accepted_license: '1'
intvolume: ' 351'
language:
- iso: eng
month: '10'
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
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: Efficient contractions of dynamic graphs - with applications
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: '20535'
abstract:
- lang: eng
text: "Many differentially private and classical non-private graph algorithms rely
crucially on determining whether some property of each vertex meets a threshold.
For example, for the k-core decomposition problem, the classic peeling algorithm
iteratively removes a vertex if its induced degree falls below a threshold. The
sparse vector technique (SVT) is generally used to transform non-private threshold
queries into private ones with only a small additive loss in accuracy. However,
a naive application of SVT in the graph setting leads to an amplification of the
error by a factor of n due to composition, as SVT is applied to every vertex.
In this paper, we resolve this problem by formulating a novel generalized sparse
vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism
which generalizes SVT (applied to vectors with one dimension) to vectors with
multiple dimensions. When applied to vectors with n dimensions, we solve a number
of important graph problems with better bounds than previous work.\r\nSpecifically,
we apply our MAT mechanism to obtain a set of improved bounds for a variety of
problems including k-core decomposition, densest subgraph, low out-degree ordering,
and vertex coloring. We give a tight local edge differentially private (LEDP)
algorithm for k-core decomposition that results in an approximation with O(ε^{-1}
log n) additive error and no multiplicative error in O(n) rounds. We also give
a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in
O(log² n) rounds for any constant η > 0. Both of these results are asymptotically
tight against our new lower bound of Ω(log n) for any constant-factor approximation
algorithm for k-core decomposition. Our new algorithms for k-core decomposition
also directly lead to new algorithms for the related problems of densest subgraph
and low out-degree ordering. Finally, we give novel LEDP differentially private
defective coloring algorithms that use number of colors given in terms of the
arboricity of the graph."
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation\r\nprogramme (MoDynStruct, No. 101019564) and the Austrian
Science Fund (FWF) grant DOI\r\n10.55776/Z422 and grant DOI 10.55776/I5982. Laxman
Dhulipala and George Z. Li: supported by NSF award number CNS-2317194. Quanquan
C. Liu: supported by a Google Academic Research Award and by an NSF award number
CCF-2453323."
alternative_title:
- LIPIcs
article_number: '91'
article_processing_charge: No
arxiv: 1
author:
- first_name: Laxman
full_name: Dhulipala, Laxman
last_name: Dhulipala
- 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: George Z.
full_name: Li, George Z.
last_name: Li
- first_name: Quanquan C.
full_name: Liu, Quanquan C.
last_name: Liu
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
- first_name: Leqi
full_name: Zhu, Leqi
id: a2117c59-cee4-11ed-b9d0-874ecf0f8ac5
last_name: Zhu
citation:
ama: 'Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. Near-optimal
differentially private graph algorithms via the Multidimensional AboveThreshold
Mechanism. In: 33rd Annual European Symposium on Algorithms. Vol 351. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.91'
apa: 'Dhulipala, L., Henzinger, M., Li, G. Z., Liu, Q. C., Sricharan, A. R., &
Zhu, L. (2025). Near-optimal differentially private graph algorithms via the Multidimensional
AboveThreshold Mechanism. 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.91'
chicago: Dhulipala, Laxman, Monika Henzinger, George Z. Li, Quanquan C. Liu, A.
R. Sricharan, and Leqi Zhu. “Near-Optimal Differentially Private Graph Algorithms
via the Multidimensional AboveThreshold Mechanism.” 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.91.
ieee: L. Dhulipala, M. Henzinger, G. Z. Li, Q. C. Liu, A. R. Sricharan, and L. Zhu,
“Near-optimal differentially private graph algorithms via the Multidimensional
AboveThreshold Mechanism,” in 33rd Annual European Symposium on Algorithms,
Warsaw, Poland, 2025, vol. 351.
ista: 'Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. 2025. Near-optimal
differentially private graph algorithms via the Multidimensional AboveThreshold
Mechanism. 33rd Annual European Symposium on Algorithms. ESA: European Symposium
on Algorithms, LIPIcs, vol. 351, 91.'
mla: Dhulipala, Laxman, et al. “Near-Optimal Differentially Private Graph Algorithms
via the Multidimensional AboveThreshold Mechanism.” 33rd Annual European Symposium
on Algorithms, vol. 351, 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025, doi:10.4230/LIPIcs.ESA.2025.91.
short: L. Dhulipala, M. Henzinger, G.Z. Li, Q.C. Liu, A.R. Sricharan, L. Zhu, 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:35Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2025-10-27T07:02:06Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2025.91
ec_funded: 1
external_id:
arxiv:
- '2508.02182'
file:
- access_level: open_access
checksum: 19146e935b5b6ad5d33c8d08280ad8e7
content_type: application/pdf
creator: dernst
date_created: 2025-10-27T06:58:43Z
date_updated: 2025-10-27T06:58:43Z
file_id: '20539'
file_name: 2025_LIPIcs.ESA_Dhulipala.pdf
file_size: 870317
relation: main_file
success: 1
file_date_updated: 2025-10-27T06:58:43Z
has_accepted_license: '1'
intvolume: ' 351'
language:
- iso: eng
month: '10'
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
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: Near-optimal differentially private graph algorithms via the Multidimensional
AboveThreshold Mechanism
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'
...
---
OA_place: publisher
OA_type: gold
_id: '19281'
abstract:
- lang: eng
text: "In this work, we consider the list-decodability and list-recoverability of
codes in the zero-rate regime. Briefly, a code \U0001D49E ⊆ [q]ⁿ is (p,\U0001D4C1,L)-list-recoverable
if for all tuples of input lists (Y₁,… ,Y_n) with each Y_i ⊆ [q] and |Y_i| = \U0001D4C1,
the number of codewords c ∈ \U0001D49E such that c_i ∉ Y_i for at most pn choices
of i ∈ [n] is less than L; list-decoding is the special case of \U0001D4C1 = 1.
In recent work by Resch, Yuan and Zhang (ICALP 2023) the zero-rate threshold for
list-recovery was determined for all parameters: that is, the work explicitly
computes p_*: = p_*(q,\U0001D4C1,L) with the property that for all ε > 0 (a) there
exist positive-rate (p_*-ε,\U0001D4C1,L)-list-recoverable codes, and (b) any (p_*+ε,\U0001D4C1,L)-list-recoverable
code has rate 0. In fact, in the latter case the code has constant size, independent
on n. However, the constant size in their work is quite large in 1/ε, at least
|\U0001D49E| ≥ (1/(ε))^O(q^L).\r\nOur contribution in this work is to show that
for all choices of q,\U0001D4C1 and L with q ≥ 3, any (p_*+ε,\U0001D4C1,L)-list-recoverable
code must have size O_{q,\U0001D4C1,L}(1/ε), and furthermore this upper bound
is complemented by a matching lower bound Ω_{q,\U0001D4C1,L}(1/ε). This greatly
generalizes work by Alon, Bukh and Polyanskiy (IEEE Trans. Inf. Theory 2018) which
focused only on the case of binary alphabet (and thus necessarily only list-decoding).
We remark that we can in fact recover the same result for q = 2 and even L, as
obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work.
\r\nOur main technical contribution is to (a) properly define a linear programming
relaxation of the list-recovery condition over large alphabets; and (b) to demonstrate
that a certain function defined on a q-ary probability simplex is maximized by
the uniform distribution. This represents the core challenge in generalizing to
larger q (as a binary simplex can be naturally identified with a one-dimensional
interval). We can subsequently re-utilize certain Schur convexity and convexity
properties established for a related function by Resch, Yuan and Zhang along with
ideas of Alon, Bukh and Polyanskiy."
acknowledgement: "The research of C. Yuan was support in part by the National Key
R&D Program of China\r\nunder Grant 2023YFE0123900 and Natural Science Foundation
of Shanghai under the 2024 Shanghai Action Plan for Science, Technology and Innovation
Grant 24BC3200700. The research of N. Resch is supported in part by an NWO (Dutch
Research Council) grant with number C.2324.0590, and this work was done in part
while he was visiting the Simons Institute for the Theory of Computing, supported
by DOE grant #DE-SC0024124."
alternative_title:
- LIPIcs
article_number: '82'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Nicolas
full_name: Resch, Nicolas
last_name: Resch
- first_name: Chen
full_name: Yuan, Chen
last_name: Yuan
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
citation:
ama: 'Resch N, Yuan C, Zhang Y. Tight bounds on list-decodable and list-recoverable
zero-rate codes. In: 16th Innovations in Theoretical Computer Science Conference.
Vol 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ITCS.2025.82'
apa: 'Resch, N., Yuan, C., & Zhang, Y. (2025). Tight bounds on list-decodable
and list-recoverable zero-rate codes. In 16th Innovations in Theoretical Computer
Science Conference (Vol. 325). New York, NY, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2025.82'
chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Tight Bounds on List-Decodable
and List-Recoverable Zero-Rate Codes.” In 16th Innovations in Theoretical Computer
Science Conference, Vol. 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.82.
ieee: N. Resch, C. Yuan, and Y. Zhang, “Tight bounds on list-decodable and list-recoverable
zero-rate codes,” in 16th Innovations in Theoretical Computer Science Conference,
New York, NY, United States, 2025, vol. 325.
ista: 'Resch N, Yuan C, Zhang Y. 2025. Tight bounds on list-decodable and list-recoverable
zero-rate codes. 16th Innovations in Theoretical Computer Science Conference.
ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 325, 82.'
mla: Resch, Nicolas, et al. “Tight Bounds on List-Decodable and List-Recoverable
Zero-Rate Codes.” 16th Innovations in Theoretical Computer Science Conference,
vol. 325, 82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ITCS.2025.82.
short: N. Resch, C. Yuan, Y. Zhang, in:, 16th Innovations in Theoretical Computer
Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-01-10
location: New York, NY, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2025-01-07
corr_author: '1'
date_created: 2025-03-02T23:01:53Z
date_published: 2025-02-11T00:00:00Z
date_updated: 2025-09-30T10:42:35Z
day: '11'
ddc:
- '510'
- '000'
department:
- _id: MaMo
doi: 10.4230/LIPIcs.ITCS.2025.82
external_id:
arxiv:
- '2309.01800'
isi:
- '001532717300082'
file:
- access_level: open_access
checksum: df3921ddf1b360b07f43d427fea51242
content_type: application/pdf
creator: dernst
date_created: 2025-03-04T09:35:57Z
date_updated: 2025-03-04T09:35:57Z
file_id: '19286'
file_name: 2025_LIPIcs_Resch.pdf
file_size: 898601
relation: main_file
success: 1
file_date_updated: 2025-03-04T09:35:57Z
has_accepted_license: '1'
intvolume: ' 325'
isi: 1
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: 16th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959773614'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds on list-decodable and list-recoverable zero-rate codes
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 325
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '21412'
abstract:
- lang: eng
text: "Payment channel networks (PCNs) are a promising technology that alleviates
blockchain scalability by shifting the transaction load from the blockchain to
the PCN. Nevertheless, the network topology has to be carefully designed to maximise
the transaction throughput in PCNs. Additionally, users in PCNs also have to make
optimal decisions on which transactions to forward and which to reject to prolong
the lifetime of their channels. In this work, we consider an input sequence of
transactions over p parties. Each transaction consists of a transaction size,
source, and target, and can be either accepted or rejected (entailing a cost).
The goal is to design a PCN topology among the p cooperating parties, along with
the channel capacities, and then output a decision for each transaction in the
sequence to minimise the cost of creating and augmenting channels, as well as
the cost of rejecting transactions. Our main contribution is an \U0001D4AA(p)
approximation algorithm for the problem with p parties. We further show that with
some assumptions on the distribution of transactions, we can reduce the approximation
ratio to \U0001D4AA(√p). We complement our theoretical analysis with an empirical
study of our assumptions and approach in the context of the Lightning Network."
acknowledgement: "Chatterjee, Krishnendu: European Research Council CoG 863818 (ForM-SMArt)
and Austrian Science Fund 10.55776/COE12.\r\nKřišťan, Jan Matyáš: Czech Science
Foundation Grant no. 24-12046S.\r\nSchmid, Stefan: German Research Foundation (DFG)
project ReNO (SPP 2378) from 2023-2027.\r\nSvoboda, Jakub: European Research Council
CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.\r\nYeo, Michelle:
MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms)."
alternative_title:
- LIPIcs
article_number: '23'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Jan Matyáš
full_name: Křišťan, Jan Matyáš
last_name: Křišťan
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. Boosting payment channel
network liquidity with topology optimization and transaction selection. In: 39th
International Symposium on Distributed Computing. Vol 356. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.DISC.2025.23'
apa: 'Chatterjee, K., Křišťan, J. M., Schmid, S., Svoboda, J., & Yeo, M. X.
(2025). Boosting payment channel network liquidity with topology optimization
and transaction selection. In 39th International Symposium on Distributed Computing
(Vol. 356). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.DISC.2025.23'
chicago: Chatterjee, Krishnendu, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda,
and Michelle X Yeo. “Boosting Payment Channel Network Liquidity with Topology
Optimization and Transaction Selection.” In 39th International Symposium on
Distributed Computing, Vol. 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.DISC.2025.23.
ieee: K. Chatterjee, J. M. Křišťan, S. Schmid, J. Svoboda, and M. X. Yeo, “Boosting
payment channel network liquidity with topology optimization and transaction selection,”
in 39th International Symposium on Distributed Computing, Berlin, Germany,
2025, vol. 356.
ista: 'Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. 2025. Boosting payment
channel network liquidity with topology optimization and transaction selection.
39th International Symposium on Distributed Computing. DISC: Symposium on Distributed
Computing, LIPIcs, vol. 356, 23.'
mla: Chatterjee, Krishnendu, et al. “Boosting Payment Channel Network Liquidity
with Topology Optimization and Transaction Selection.” 39th International Symposium
on Distributed Computing, vol. 356, 23, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, doi:10.4230/LIPIcs.DISC.2025.23.
short: K. Chatterjee, J.M. Křišťan, S. Schmid, J. Svoboda, M.X. Yeo, in:, 39th International
Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025.
conference:
end_date: 2025-10-31
location: Berlin, Germany
name: 'DISC: Symposium on Distributed Computing'
start_date: 2025-10-27
date_created: 2026-03-08T23:01:46Z
date_published: 2025-10-22T00:00:00Z
date_updated: 2026-03-09T11:52:58Z
day: '22'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.DISC.2025.23
ec_funded: 1
external_id:
arxiv:
- '2508.14524'
file:
- access_level: open_access
checksum: 8e3d1594365df60163d9df22158a37b1
content_type: application/pdf
creator: dernst
date_created: 2026-03-09T11:51:59Z
date_updated: 2026-03-09T11:51:59Z
file_id: '21418'
file_name: 2025_DISC_Chatterjee.pdf
file_size: 1130069
relation: main_file
success: 1
file_date_updated: 2026-03-09T11:51:59Z
has_accepted_license: '1'
intvolume: ' 356'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1484.pdf
month: '10'
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'
publication: 39th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959774024'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Boosting payment channel network liquidity with topology optimization and transaction
selection
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: 356
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20587'
abstract:
- lang: eng
text: "The blocks in the Bitcoin blockchain \"record\" the amount of work W that
went into creating them through proofs of work. When honest parties control a
majority of the work, consensus is achieved by picking the chain with the highest
recorded weight. Resources other than work have been considered to secure such
longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via
a proof of space) and sequential computational steps V (through a VDF).\r\nIn
this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block
as a function of the recorded space, speed, and work) are secure in the sense
that whenever the weight of the resources controlled by honest parties is larger
than the weight of adversarial parties, the blockchain is secure against private
double-spending attacks.\r\nWe completely classify such functions in an idealized
\"continuous\" model: Γ(S,V,W) is secure against private double-spending attacks
if and only if it is homogeneous of degree one in the \"timed\" resources V and
W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) =
W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are
created at discrete time-points, one additionally needs some mild assumptions
on the dependency on S (basically, the weight should not grow too much if S is
slightly increased, say linear as in Chia).\r\nOur classification is more general
and allows various instantiations of the same resource. It provides a powerful
tool for designing new longest-chain blockchains. E.g., consider combining different
PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂.
Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g.,
√{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these
are much better choices."
acknowledgement: "This research was funded in whole or in part by the Austrian Science
Fund (FWF)\r\n10.55776/F85. For open access purposes, the author has applied a CC
BY public copyright license\r\nto any author-accepted manuscript version arising
from this submission."
alternative_title:
- LIPIcs
article_number: '16'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources.
In: 7th Conference on Advances in Financial Technologies. Vol 354. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.AFT.2025.16'
apa: 'Baig, M. A., Günther, C. U., & Pietrzak, K. Z. (2025). Nakamoto consensus
from multiple resources. In 7th Conference on Advances in Financial Technologies
(Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2025.16'
chicago: Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak.
“Nakamoto Consensus from Multiple Resources.” In 7th Conference on Advances
in Financial Technologies, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2025. https://doi.org/10.4230/LIPIcs.AFT.2025.16.
ieee: M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple
resources,” in 7th Conference on Advances in Financial Technologies, Pittsburgh,
PA, United States, 2025, vol. 354.
ista: 'Baig MA, Günther CU, Pietrzak KZ. 2025. Nakamoto consensus from multiple
resources. 7th Conference on Advances in Financial Technologies. AFT: Conference
on Advances in Financial Technologies, LIPIcs, vol. 354, 16.'
mla: Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” 7th
Conference on Advances in Financial Technologies, vol. 354, 16, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.AFT.2025.16.
short: M.A. Baig, C.U. Günther, K.Z. Pietrzak, in:, 7th Conference on Advances in
Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-10-10
location: Pittsburgh, PA, United States
name: 'AFT: Conference on Advances in Financial Technologies'
start_date: 2025-10-08
corr_author: '1'
date_created: 2025-11-02T23:01:34Z
date_published: 2025-10-06T00:00:00Z
date_updated: 2026-04-15T08:45:18Z
day: '06'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.AFT.2025.16
external_id:
arxiv:
- '2508.01448'
file:
- access_level: open_access
checksum: b638adcd4fbffa77116c35393e165eb7
content_type: application/pdf
creator: dernst
date_created: 2025-11-04T08:19:02Z
date_updated: 2025-11-04T08:19:02Z
file_id: '20598'
file_name: 2025_LIPIcsAFT_Baig.pdf
file_size: 1061847
relation: main_file
success: 1
file_date_updated: 2025-11-04T08:19:02Z
has_accepted_license: '1'
intvolume: ' 354'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1410
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
grant_number: F8512
name: Security and Privacy by Design for Complex Systems
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 7th Conference on Advances in Financial Technologies
publication_identifier:
isbn:
- '9783959774000'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '21651'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Nakamoto consensus from multiple resources
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: 354
year: '2025'
...
---
_id: '18066'
abstract:
- lang: eng
text: 'Graph games lie at the algorithmic core of many automated design problems
in computer science. These are games usually played between two players on a given
graph, where the players keep moving a token along the edges according to pre-determined
rules (turn-based, concurrent, etc.), and the winner is decided based on the infinite
path (aka play) traversed by the token from a given initial position. In bidding
games, the players initially get some monetary budgets which they need to use
to bid for the privilege of moving the token at each step. Each round of bidding
affects the players'' available budgets, which is the only form of update that
the budgets experience. We introduce bidding games with charging where the players
can additionally improve their budgets during the game by collecting vertex-dependent
monetary rewards, aka the "charges." Unlike traditional bidding games (where all
charges are zero), bidding games with charging allow non-trivial recurrent behaviors.
For example, a reachability objective may require multiple detours to vertices
with high charges to earn additional budget. We show that, nonetheless, the central
property of traditional bidding games generalizes to bidding games with charging:
For each vertex there exists a threshold ratio, which is the necessary and sufficient
fraction of the total budget for winning the game from that vertex. While the
thresholds of traditional bidding games correspond to unique fixed points of linear
systems of equations, in games with charging, these fixed points are no longer
unique. This significantly complicates the proof of existence and the algorithmic
computation of thresholds for infinite-duration objectives. We also provide the
lower complexity bounds for computing thresholds for Rabin and Streett objectives,
which are the first known lower bounds in any form of bidding games (with or without
charging), and we solve the following repair problem for safety and reachability
games that have unsatisfiable objectives: Can we distribute a given amount of
charge to the players in a way such that the objective can be satisfied?'
acknowledgement: This work was supported in part by the ERC projects ERC-2020-AdG
101020093 and CoG 863818 (ForM-SMArt) and by ISF grant no. 1679/21.
alternative_title:
- LIPIcs
article_number: '8'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- first_name: Ehsan Kafshdar
full_name: Goharshady, Ehsan Kafshdar
last_name: Goharshady
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Kaushik
full_name: Mallik, Kaushik
id: 0834ff3c-6d72-11ec-94e0-b5b0a4fb8598
last_name: Mallik
orcid: 0000-0001-9864-7475
citation:
ama: 'Avni G, Goharshady EK, Henzinger TA, Mallik K. Bidding games with charging.
In: 35th International Conference on Concurrency Theory. Vol 311. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.CONCUR.2024.8'
apa: 'Avni, G., Goharshady, E. K., Henzinger, T. A., & Mallik, K. (2024). Bidding
games with charging. In 35th International Conference on Concurrency Theory
(Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CONCUR.2024.8'
chicago: Avni, Guy, Ehsan Kafshdar Goharshady, Thomas A Henzinger, and Kaushik Mallik.
“Bidding Games with Charging.” In 35th International Conference on Concurrency
Theory, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.CONCUR.2024.8.
ieee: G. Avni, E. K. Goharshady, T. A. Henzinger, and K. Mallik, “Bidding games
with charging,” in 35th International Conference on Concurrency Theory,
Calgary, Canada, 2024, vol. 311.
ista: 'Avni G, Goharshady EK, Henzinger TA, Mallik K. 2024. Bidding games with charging.
35th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 311, 8.'
mla: Avni, Guy, et al. “Bidding Games with Charging.” 35th International Conference
on Concurrency Theory, vol. 311, 8, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.CONCUR.2024.8.
short: G. Avni, E.K. Goharshady, T.A. Henzinger, K. Mallik, in:, 35th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2024-09-13
location: Calgary, Canada
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2024-09-09
corr_author: '1'
date_created: 2024-09-15T22:01:39Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:46:11Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2024.8
ec_funded: 1
external_id:
arxiv:
- '2407.06288'
isi:
- '001556847400008'
file:
- access_level: open_access
checksum: cb6f2254b84922cd7bf224f550b73f4a
content_type: application/pdf
creator: dernst
date_created: 2024-09-17T09:35:03Z
date_updated: 2024-09-17T09:35:03Z
file_id: '18083'
file_name: 2024_LIPICS_Avni.pdf
file_size: 854430
relation: main_file
success: 1
file_date_updated: 2024-09-17T09:35:03Z
has_accepted_license: '1'
intvolume: ' 311'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 35th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959773393'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bidding games with charging
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: 311
year: '2024'
...
---
_id: '18067'
abstract:
- lang: eng
text: "An automaton \U0001D49C is history-deterministic if its nondeterminism can
be resolved on the fly, only using the prefix of the word read so far. This mild
form of nondeterminism has attracted particular attention for its applications
in synthesis problems. An automaton \U0001D49C is guidable with respect to a class
C of automata if it can fairly simulate every automaton in C, whose language is
contained in that of \U0001D49C. In other words, guidable automata are those for
which inclusion and simulation coincide, making them particularly interesting
for model-checking. We study the connection between these two notions, and specifically
the question of when they coincide. For classes of automata on which they do,
deciding guidability, an otherwise challenging decision problem, reduces to deciding
history-determinism, a problem that is starting to be well-understood for many
classes. We provide a selection of sufficient criteria for a class of automata
to guarantee the coincidence of the notions, and use them to show that the notions
coincide for the most common automata classes, among which are ω-regular automata
and many infinite-state automata with safety and reachability acceptance conditions,
including vector addition systems with states, one-counter nets, pushdown-, Parikh-,
and timed-automata. We also demonstrate that history-determinism and guidability
do not always coincide, for example, for the classes of timed automata with a
fixed number of clocks."
acknowledgement: "Udi Boker: Israel Science Foundation grant 2410/22\r\nThomas A.
Henzinger: ERC-2020-AdG 101020093 (VAMOS)\r\nKaroliina Lehtinen: ANR QUASY 23-CE48-0008-01\r\nAditya
Prakash: Chancellors’ International Scholarship from the University of Warwick and
Centre for Discrete Mathematics and Its Applications (DIMAP)"
alternative_title:
- LIPIcs
article_number: '12'
article_processing_charge: No
arxiv: 1
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Karoliina
full_name: Lehtinen, Karoliina
last_name: Lehtinen
- first_name: Aditya
full_name: Prakash, Aditya
last_name: Prakash
citation:
ama: 'Boker U, Henzinger TA, Lehtinen K, Prakash A. History-determinism vs fair
simulation. In: 35th International Conference on Concurrency Theory. Vol
311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.CONCUR.2024.12'
apa: 'Boker, U., Henzinger, T. A., Lehtinen, K., & Prakash, A. (2024). History-determinism
vs fair simulation. In 35th International Conference on Concurrency Theory
(Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CONCUR.2024.12'
chicago: Boker, Udi, Thomas A Henzinger, Karoliina Lehtinen, and Aditya Prakash.
“History-Determinism vs Fair Simulation.” In 35th International Conference
on Concurrency Theory, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024. https://doi.org/10.4230/LIPIcs.CONCUR.2024.12.
ieee: U. Boker, T. A. Henzinger, K. Lehtinen, and A. Prakash, “History-determinism
vs fair simulation,” in 35th International Conference on Concurrency Theory,
Calgary, Canada, 2024, vol. 311.
ista: 'Boker U, Henzinger TA, Lehtinen K, Prakash A. 2024. History-determinism vs
fair simulation. 35th International Conference on Concurrency Theory. CONCUR:
Conference on Concurrency Theory, LIPIcs, vol. 311, 12.'
mla: Boker, Udi, et al. “History-Determinism vs Fair Simulation.” 35th International
Conference on Concurrency Theory, vol. 311, 12, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024, doi:10.4230/LIPIcs.CONCUR.2024.12.
short: U. Boker, T.A. Henzinger, K. Lehtinen, A. Prakash, in:, 35th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2024-09-13
location: Calgary, Canada
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2024-09-09
corr_author: '1'
date_created: 2024-09-15T22:01:40Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:44:54Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2024.12
ec_funded: 1
external_id:
arxiv:
- '2407.08620'
isi:
- '001556847400012'
file:
- access_level: open_access
checksum: 66db11ef8e600a434079c278050c3f09
content_type: application/pdf
creator: dernst
date_created: 2024-09-17T07:31:18Z
date_updated: 2024-09-17T07:31:18Z
file_id: '18080'
file_name: 2024_LIPICS_Boker.pdf
file_size: 766902
relation: main_file
success: 1
file_date_updated: 2024-09-17T07:31:18Z
has_accepted_license: '1'
intvolume: ' 311'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 35th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959773393'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: History-determinism vs fair simulation
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: 311
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18068'
abstract:
- lang: eng
text: "We study the following refinement relation between nondeterministic state-transition
models: model ℬ strategically dominates model \U0001D49C iff every deterministic
refinement of \U0001D49C is language contained in some deterministic refinement
of ℬ. While language containment is trace inclusion, and the (fair) simulation
preorder coincides with tree inclusion, strategic dominance falls strictly between
the two and can be characterized as \"strategy inclusion\" between \U0001D49C
and ℬ: every strategy that resolves the nondeterminism of \U0001D49C is dominated
by a strategy that resolves the nondeterminism of ℬ. Strategic dominance can be
checked in 2-ExpTime by a decidable first-order Presburger logic with quantification
over words and strategies, called resolver logic. We give several other applications
of resolver logic, including checking the co-safety, co-liveness, and history-determinism
of boolean and quantitative automata, and checking the inclusion between hyperproperties
that are specified by nondeterministic boolean and quantitative automata."
acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093. N.
Mazzocchi was affiliated with ISTA when this work was submitted for publication.
alternative_title:
- LIPIcs
article_number: '29'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Nicolas Adrien
full_name: Mazzocchi, Nicolas Adrien
id: b26baa86-3308-11ec-87b0-8990f34baa85
last_name: Mazzocchi
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
citation:
ama: 'Henzinger TA, Mazzocchi NA, Sarac NE. Strategic dominance: A new preorder
for nondeterministic processes. In: 35th International Conference on Concurrency
Theory. Vol 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024.
doi:10.4230/LIPIcs.CONCUR.2024.29'
apa: 'Henzinger, T. A., Mazzocchi, N. A., & Sarac, N. E. (2024). Strategic dominance:
A new preorder for nondeterministic processes. In 35th International Conference
on Concurrency Theory (Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2024.29'
chicago: 'Henzinger, Thomas A, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Strategic
Dominance: A New Preorder for Nondeterministic Processes.” In 35th International
Conference on Concurrency Theory, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024. https://doi.org/10.4230/LIPIcs.CONCUR.2024.29.'
ieee: 'T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Strategic dominance:
A new preorder for nondeterministic processes,” in 35th International Conference
on Concurrency Theory, Calgary, Canada, 2024, vol. 311.'
ista: 'Henzinger TA, Mazzocchi NA, Sarac NE. 2024. Strategic dominance: A new preorder
for nondeterministic processes. 35th International Conference on Concurrency Theory.
CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 311, 29.'
mla: 'Henzinger, Thomas A., et al. “Strategic Dominance: A New Preorder for Nondeterministic
Processes.” 35th International Conference on Concurrency Theory, vol. 311,
29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.CONCUR.2024.29.'
short: T.A. Henzinger, N.A. Mazzocchi, N.E. Sarac, in:, 35th International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-13
location: Calgary, Canada
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2024-09-09
corr_author: '1'
date_created: 2024-09-15T22:01:40Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:45:38Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
- _id: GradSch
doi: 10.4230/LIPIcs.CONCUR.2024.29
ec_funded: 1
external_id:
arxiv:
- '2407.10473'
isi:
- '001556847400029'
file:
- access_level: open_access
checksum: 555bd343e1fb38adeab8fc465ff4fad8
content_type: application/pdf
creator: dernst
date_created: 2024-09-17T07:48:56Z
date_updated: 2024-09-17T07:48:56Z
file_id: '18081'
file_name: 2024_LIPICS_Henzinger.pdf
file_size: 964124
relation: main_file
success: 1
file_date_updated: 2024-09-17T07:48:56Z
has_accepted_license: '1'
intvolume: ' 311'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 35th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959773393'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Strategic dominance: A new preorder for nondeterministic processes'
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: 311
year: '2024'
...
---
_id: '18156'
abstract:
- lang: eng
text: Privately counting distinct elements in a stream is a fundamental data analysis
problem with many applications in machine learning. In the turnstile model, Jain
et al. [NeurIPS2023] initiated the study of this problem parameterized by the
maximum flippancy of any element, i.e., the number of times that the count of
an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially
private algorithm whose additive error is tight with respect to that parameterization.
In this work, we show that a very simple algorithm based on the sparse vector
technique achieves a tight additive error for item-level (ε,δ)-differential privacy
and item-level ε-differential privacy with regards to a different parameterization,
namely the sum of all flippancies. Our second result is a bound which shows that
for a large class of algorithms, including all existing differentially private
algorithms for this problem, the lower bound from item-level differential privacy
extends to event-level differential privacy. This partially answers an open question
by Jain et al. [NeurIPS2023].
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nTeresa Anna
Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN."
alternative_title:
- LIPIcs
article_number: '40'
article_processing_charge: No
arxiv: 1
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: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
- first_name: Teresa Anna
full_name: Steiner, Teresa Anna
last_name: Steiner
citation:
ama: 'Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements
in the turnstile model and extensions. In: International Conference on Approximation
Algorithms for Combinatorial Optimization Problems . Vol 317. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40'
apa: 'Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2024). Private counting
of distinct elements in the turnstile model and extensions. In International
Conference on Approximation Algorithms for Combinatorial Optimization Problems
(Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40'
chicago: Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting
of Distinct Elements in the Turnstile Model and Extensions.” In International
Conference on Approximation Algorithms for Combinatorial Optimization Problems
, Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40.
ieee: M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct
elements in the turnstile model and extensions,” in International Conference
on Approximation Algorithms for Combinatorial Optimization Problems , London,
United Kingdom, 2024, vol. 317.
ista: 'Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct
elements in the turnstile model and extensions. International Conference on Approximation
Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation
Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.'
mla: Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile
Model and Extensions.” International Conference on Approximation Algorithms
for Combinatorial Optimization Problems , vol. 317, 40, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40.
short: M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference
on Approximation Algorithms for Combinatorial Optimization Problems , Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-08-30
location: London, United Kingdom
name: 'APPROX: Conference on Approximation Algorithms for Combinatorial Optimization
Problems'
start_date: 2024-08-27
corr_author: '1'
date_created: 2024-09-29T22:01:38Z
date_published: 2024-09-16T00:00:00Z
date_updated: 2025-12-02T13:47:16Z
day: '16'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.APPROX/RANDOM.2024.40
ec_funded: 1
external_id:
arxiv:
- '2408.11637'
isi:
- '001545634500040'
file:
- access_level: open_access
checksum: c08b41c896e4d8c69570044808b40e0b
content_type: application/pdf
creator: dernst
date_created: 2024-10-01T10:07:14Z
date_updated: 2024-10-01T10:07:14Z
file_id: '18166'
file_name: 2024_LIPICs_HenzingerM.pdf
file_size: 973917
relation: main_file
success: 1
file_date_updated: 2024-10-01T10:07:14Z
has_accepted_license: '1'
intvolume: ' 317'
isi: 1
language:
- iso: eng
month: '09'
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: 'International Conference on Approximation Algorithms for Combinatorial
Optimization Problems '
publication_identifier:
isbn:
- '9783959773485'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Private counting of distinct elements in the turnstile model and extensions
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: 317
year: '2024'
...
---
_id: '18175'
abstract:
- lang: eng
text: Large-scale software repositories are a source of insights for software engineering.
They offer an unmatched window into the software development process at scale.
Their sheer number and size holds the promise of broadly applicable results. At
the same time, that very size presents practical challenges for scaling tools
and algorithms to millions of projects. A reasonable approach is to limit studies
to representative samples of the population of interest. Broadly applicable conclusions
can then be obtained by generalizing to the entire population. The contribution
of this paper is a standardized experimental design methodology for choosing the
inputs of studies working with large-scale repositories. We advocate for a methodology
that clearly lays out what the population of interest is, how to sample it, and
that fosters reproducibility. Along the way, we discourage researchers from using
extrinsic attributes of projects such as stars, that measure some unclear notion
of popularity.
acknowledgement: "This work was supported by the Czech Ministry of Education, Youth
and Sports under\r\nprogram ERC-CZ, grant agreement LL2325, BigCode (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000421).
NSF grants CCF-1910850, CNS-1925644, and CCF-2139612, as well as the GACR EXPRO
grant 23-07580X. We would like to thank Digital Ocean for their involuntary contribution
of computational resources during the early data gathering phase of our research.
We acknoweldge the reviewers of ICSE’22, and thank the reviewers of ECOOP’23 for
their encouragments and for sticking around until 2024."
alternative_title:
- LIPIcs
article_number: '27'
article_processing_charge: No
author:
- first_name: Petr
full_name: Maj, Petr
last_name: Maj
- first_name: Stefanie
full_name: Muroya Lei, Stefanie
id: a376de31-8972-11ed-ae7b-d0251c13c8ff
last_name: Muroya Lei
- first_name: Konrad
full_name: Siek, Konrad
last_name: Siek
- first_name: Luca
full_name: Di Grazia, Luca
last_name: Di Grazia
- first_name: Jan
full_name: Vitek, Jan
last_name: Vitek
citation:
ama: 'Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. The fault in our stars:
Designing reproducible large-scale code analysis experiments. In: 38th European
Conference on Object-Oriented Programming. Vol 313. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.ECOOP.2024.27'
apa: 'Maj, P., Muroya Lei, S., Siek, K., Di Grazia, L., & Vitek, J. (2024).
The fault in our stars: Designing reproducible large-scale code analysis experiments.
In 38th European Conference on Object-Oriented Programming (Vol. 313).
Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ECOOP.2024.27'
chicago: 'Maj, Petr, Stefanie Muroya Lei, Konrad Siek, Luca Di Grazia, and Jan Vitek.
“The Fault in Our Stars: Designing Reproducible Large-Scale Code Analysis Experiments.”
In 38th European Conference on Object-Oriented Programming, Vol. 313. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ECOOP.2024.27.'
ieee: 'P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, and J. Vitek, “The fault in
our stars: Designing reproducible large-scale code analysis experiments,” in 38th
European Conference on Object-Oriented Programming, Vienna, Austria, 2024,
vol. 313.'
ista: 'Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. 2024. The fault in our
stars: Designing reproducible large-scale code analysis experiments. 38th European
Conference on Object-Oriented Programming. ECOOP: European Conference on Object-Oriented
Programming, LIPIcs, vol. 313, 27.'
mla: 'Maj, Petr, et al. “The Fault in Our Stars: Designing Reproducible Large-Scale
Code Analysis Experiments.” 38th European Conference on Object-Oriented Programming,
vol. 313, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ECOOP.2024.27.'
short: P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, J. Vitek, in:, 38th European
Conference on Object-Oriented Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024.
conference:
end_date: 2024-09-20
location: Vienna, Austria
name: 'ECOOP: European Conference on Object-Oriented Programming'
start_date: 2024-09-16
date_created: 2024-10-06T22:01:12Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:48:19Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.ECOOP.2024.27
external_id:
isi:
- '001533999700027'
file:
- access_level: open_access
checksum: 2e75d305a8c817d76a0c7f136ce34f86
content_type: application/pdf
creator: dernst
date_created: 2024-10-07T11:10:55Z
date_updated: 2024-10-07T11:10:55Z
file_id: '18184'
file_name: 2024_LIPICs_Maj.pdf
file_size: 1764222
relation: main_file
success: 1
file_date_updated: 2024-10-07T11:10:55Z
has_accepted_license: '1'
intvolume: ' 313'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: 38th European Conference on Object-Oriented Programming
publication_identifier:
isbn:
- '9783959773416'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The fault in our stars: Designing reproducible large-scale code analysis experiments'
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: 313
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18308'
abstract:
- lang: eng
text: We study in this paper the problem of maintaining a solution to k-median and
k-means clustering in a fully dynamic setting. To do so, we present an algorithm
to efficiently maintain a coreset, a compressed version of the dataset, that allows
easy computation of a clustering solution at query time. Our coreset algorithm
has near-optimal update time of Õ(k) in general metric spaces, which reduces to
Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and
O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means
clustering in Euclidean space, this directly leads to an algorithm with update
time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation,
the query time is reduced to Õ(kd).
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund
(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775
with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic:
Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon
2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement
No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from
the French National Research Agency (ANR)."
alternative_title:
- LIPIcs
article_number: '100'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Max Dupré
full_name: La Tour, Max Dupré
last_name: La Tour
- 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: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
citation:
ama: 'La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal
update time. In: 32nd Annual European Symposium on Algorithms. Vol 308.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.100'
apa: 'La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Fully dynamic k-means
coreset in near-optimal update time. In 32nd Annual European Symposium on Algorithms
(Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2024.100'
chicago: La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic
K-Means Coreset in near-Optimal Update Time.” In 32nd Annual European Symposium
on Algorithms, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024. https://doi.org/10.4230/LIPIcs.ESA.2024.100.
ieee: M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset
in near-optimal update time,” in 32nd Annual European Symposium on Algorithms,
London, United Kingdom, 2024, vol. 308.
ista: 'La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in
near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European
Symposium on Algorithms, LIPIcs, vol. 308, 100.'
mla: La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update
Time.” 32nd Annual European Symposium on Algorithms, vol. 308, 100, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.100.
short: M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-04
location: London, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2024-09-02
corr_author: '1'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-23T00:00:00Z
date_updated: 2025-12-02T13:49:11Z
day: '23'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.100
ec_funded: 1
external_id:
arxiv:
- '2406.19926'
isi:
- '001545622400100'
file:
- access_level: open_access
checksum: 8e8c0b13049f11bb0133dfac22e32718
content_type: application/pdf
creator: dernst
date_created: 2024-10-21T09:41:48Z
date_updated: 2024-10-21T09:41:48Z
file_id: '18454'
file_name: 2024_LIPICs_DuprelaTour.pdf
file_size: 873561
relation: main_file
success: 1
file_date_updated: 2024-10-21T09:41:48Z
has_accepted_license: '1'
intvolume: ' 308'
isi: 1
language:
- iso: eng
month: '09'
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773386'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic k-means coreset in near-optimal update time
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: 308
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18309'
abstract:
- lang: eng
text: 'The problem of designing connectivity oracles supporting vertex failures
is one of the basic data structures problems for undirected graphs. It is already
well understood: previous works [Duan-Pettie STOC''10; Long-Saranurak FOCS''22]
achieve query time linear in the number of failed vertices, and it is conditionally
optimal as long as we require preprocessing time polynomial in the size of the
graph and update time polynomial in the number of failed vertices. We revisit
this problem in the paradigm of algorithms with predictions: we ask if the query
time can be improved if the set of failed vertices can be predicted beforehand
up to a small number of errors. More specifically, we design a data structure
that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of
size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update
given as the symmetric difference between the predicted and the actual set of
failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time
Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed
from another perspective, our data structure provides an improvement over the
state of the art for the fully dynamic subgraph connectivity problem in the sensitivity
setting [Henzinger-Neumann ESA''16]. We argue that the preprocessing time and
query time of our data structure are conditionally optimal under standard fine-grained
complexity assumptions.'
acknowledgement: "Part of this work was done when Evangelos Kosinas was at University
of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n"
alternative_title:
- LIPIcs
article_number: '72'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Bingbing
full_name: Hu, Bingbing
last_name: Hu
- first_name: Evangelos
full_name: Kosinas, Evangelos
id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949
last_name: Kosinas
- first_name: Adam
full_name: Polak, Adam
last_name: Polak
citation:
ama: 'Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures.
In: 32nd Annual European Symposium on Algorithms. Vol 308. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.72'
apa: 'Hu, B., Kosinas, E., & Polak, A. (2024). Connectivity oracles for predictable
vertex failures. In 32nd Annual European Symposium on Algorithms (Vol.
308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2024.72'
chicago: Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles
for Predictable Vertex Failures.” In 32nd Annual European Symposium on Algorithms,
Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.72.
ieee: B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex
failures,” in 32nd Annual European Symposium on Algorithms, London, United
Kingdom, 2024, vol. 308.
ista: 'Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex
failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium
on Algorithms, LIPIcs, vol. 308, 72.'
mla: Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.”
32nd Annual European Symposium on Algorithms, vol. 308, 72, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.72.
short: B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-04
location: London, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2024-09-02
corr_author: '1'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:49:52Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.72
external_id:
arxiv:
- '2312.08489'
isi:
- '001545622400072'
file:
- access_level: open_access
checksum: ab1f2f9161549a8763eda15db40e022c
content_type: application/pdf
creator: dernst
date_created: 2024-10-21T10:03:48Z
date_updated: 2024-10-21T10:03:48Z
file_id: '18455'
file_name: 2024_LIPICs_Hu.pdf
file_size: 853914
relation: main_file
success: 1
file_date_updated: 2024-10-21T10:03:48Z
has_accepted_license: '1'
intvolume: ' 308'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773386'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Connectivity oracles for predictable vertex failures
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: 308
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18556'
abstract:
- lang: eng
text: Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined
length of the minimum spanning trees of B and A⧵B divided by the length of the
minimum spanning tree of A. The question of the supremum, over all sets A, of
the maximum, over all subsets B, is related to the Steiner ratio, and we prove
this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional
lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin
the most difficult of these results is the upper bound for the inf-max, which
we prove by showing that the hexagonal lattice cannot have MST-ratio larger than
1.25.
acknowledgement: This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme,
grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, "Discretization
in Geometry and Dynamics", Austrian Science Fund (FWF), grant no. I 02979-N35.
alternative_title:
- LIPIcs
article_number: '3'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sebastiano
full_name: Cultrera di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera di Montesano
orcid: 0000-0001-6249-0832
- first_name: Ondrej
full_name: Draganov, Ondrej
id: 2B23F01E-F248-11E8-B48F-1D18A9856A87
last_name: Draganov
orcid: 0000-0003-0464-3823
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. The Euclidean
MST-ratio for bi-colored lattices. In: 32nd International Symposium on Graph
Drawing and Network Visualization. Vol 320. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.GD.2024.3'
apa: 'Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian,
M. (2024). The Euclidean MST-ratio for bi-colored lattices. In 32nd International
Symposium on Graph Drawing and Network Visualization (Vol. 320). Vienna, Austria:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.3'
chicago: Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner,
and Morteza Saghafian. “The Euclidean MST-Ratio for Bi-Colored Lattices.” In 32nd
International Symposium on Graph Drawing and Network Visualization, Vol. 320.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.GD.2024.3.
ieee: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian,
“The Euclidean MST-ratio for bi-colored lattices,” in 32nd International Symposium
on Graph Drawing and Network Visualization, Vienna, Austria, 2024, vol. 320.
ista: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2024. The
Euclidean MST-ratio for bi-colored lattices. 32nd International Symposium on Graph
Drawing and Network Visualization. GD: Graph Drawing and Network Visualization,
LIPIcs, vol. 320, 3.'
mla: Cultrera di Montesano, Sebastiano, et al. “The Euclidean MST-Ratio for Bi-Colored
Lattices.” 32nd International Symposium on Graph Drawing and Network Visualization,
vol. 320, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.GD.2024.3.
short: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, in:,
32nd International Symposium on Graph Drawing and Network Visualization, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-20
location: Vienna, Austria
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2024-09-18
corr_author: '1'
date_created: 2024-11-17T23:01:47Z
date_published: 2024-10-28T00:00:00Z
date_updated: 2025-12-02T13:50:50Z
day: '28'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.GD.2024.3
ec_funded: 1
external_id:
arxiv:
- '2403.10204'
isi:
- '001540278400001'
file:
- access_level: open_access
checksum: 5f9b35e115c3d375e99be78da9054cb4
content_type: application/pdf
creator: dernst
date_created: 2024-11-18T07:49:25Z
date_updated: 2024-11-18T07:49:25Z
file_id: '18560'
file_name: 2024_LIPIcs_CultreradiMontesano.pdf
file_size: 908541
relation: main_file
success: 1
file_date_updated: 2024-11-18T07:49:25Z
has_accepted_license: '1'
intvolume: ' 320'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: 32nd International Symposium on Graph Drawing and Network Visualization
publication_identifier:
isbn:
- '9783959773430'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Euclidean MST-ratio for bi-colored lattices
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: 320
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18557'
abstract:
- lang: eng
text: Broadcast and Consensus are most fundamental tasks in distributed computing.
These tasks are particularly challenging in dynamic networks where communication
across the network links may be unreliable, e.g., due to mobility or failures.
Over the last years, researchers have derived several impossibility results and
high time complexity lower bounds for these tasks. Specifically for the setting
where in each round of communication the adversary is allowed to choose one rooted
tree along which the information is disseminated, there is a lower as well as
an upper bound that is linear in the number n of nodes for Broadcast and for n
≥ 3 the adversary can guarantee that Consensus never happens. This setting is
called the oblivious message adversary for rooted trees. Also note that if the
adversary is allowed to choose a graph that does not contain a rooted tree, then
it can guarantee that Broadcast and Consensus will never happen. However, such
deterministic adversarial models may be overly pessimistic, as many processes
in real-world settings are stochastic in nature rather than worst-case. This paper
studies Broadcast on stochastic dynamic networks and shows that the situation
is very different to the deterministic case. In particular, we show that if information
dissemination occurs along random rooted trees and directed Erdős–Rényi graphs,
Broadcast completes in O(log n) rounds of communication with high probability.
The fundamental insight in our analysis is that key variables are mutually independent.
We then study two adversarial models, (a) one with Byzantine nodes and (b) one
where an adversary controls the edges. (a) Our techniques without Byzantine nodes
are general enough so that they can be extended to Byzantine nodes. (b) In the
spirit of smoothed analysis, we introduce the notion of randomized oblivious message
adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in
the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi
graph) is chosen uniformly at random among the set of all such graphs that include
these edges. We show that Broadcast completes in a finite number of rounds, which
is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All
Broadcast, and Consensus, and give lower bounds that show that most of our upper
bounds are tight.
acknowledgement: "Antoine El-Hayek: This project has received funding from the Austrian
Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the
netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received
funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon
2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian
Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant
DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung,
2020–2024.\r\nStefan Schmid: This project has received funding from the German Research
Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027."
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- 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: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic
networks with Byzantine nodes and adversarial edges. In: 38th International
Symposium on Distributed Computing. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.DISC.2024.21'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2024). Broadcast and Consensus
in stochastic dynamic networks with Byzantine nodes and adversarial edges. In
38th International Symposium on Distributed Computing (Vol. 319). Madrid,
Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2024.21'
chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and
Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial
Edges.” In 38th International Symposium on Distributed Computing, Vol.
319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.DISC.2024.21.
ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges,” in 38th International
Symposium on Distributed Computing, Madrid, Spain, 2024, vol. 319.
ista: 'El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges. 38th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing,
LIPIcs, vol. 319, 21.'
mla: El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks
with Byzantine Nodes and Adversarial Edges.” 38th International Symposium on
Distributed Computing, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.DISC.2024.21.
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on
Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-11-01
location: Madrid, Spain
name: 'DISC: Symposium on Distributed Computing'
start_date: 2024-10-28
corr_author: '1'
date_created: 2024-11-17T23:01:47Z
date_published: 2024-10-24T00:00:00Z
date_updated: 2025-12-02T13:51:28Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.DISC.2024.21
ec_funded: 1
external_id:
arxiv:
- '2302.11988'
isi:
- '001542467600021'
file:
- access_level: open_access
checksum: d6c8277331cafa188c33ba1717206cf4
content_type: application/pdf
creator: dernst
date_created: 2024-11-18T08:02:45Z
date_updated: 2024-11-18T08:02:45Z
file_id: '18561'
file_name: 2024_LIPIcs_ElHayek.pdf
file_size: 809666
relation: main_file
success: 1
file_date_updated: 2024-11-18T08:02:45Z
has_accepted_license: '1'
intvolume: ' 319'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 38th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959773522'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes
and adversarial edges
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: 319
year: '2024'
...