---
OA_place: publisher
OA_type: gold
_id: '22617'
abstract:
- lang: eng
text: "Consider a 4-player version of Matching Pennies where a team of three players
competes against the Devil. Each player simultaneously says \"Heads\" or \"Tails\".
The team wins if all four choices match; otherwise the Devil wins. If all team
players randomise independently, they win with probability 1/8; if all players
share a common source of randomness, they win with probability 1/2. What happens
when each pair of team players shares a source of randomness? Can the team do
better than win with probability 1/4? The surprising (and nontrivial) answer is
yes!\r\nWe introduce Dicey Games, a formal framework motivated by the study of
distributed systems with shared sources of randomness (of which the above example
is a specific instance). We characterise the existence, representation and computational
complexity of optimal strategies in Dicey Games, and we study the problem of allocating
limited sources of randomness optimally within a team."
acknowledgement: "This work was supported in part by the ERC-2020-AdG 101020093 (VAMOS).\r\nLéonard
Brice: Part of this work was realised when this author was an FNRS aspirant at Université
libre de Bruxelles.\r\nK. S. Thejaswini: Part of this work was realised when this
author was a post-doctoral researcher at IST Austria.\r\nAcknowledgements We thank
all our colleagues who took the time to hear our puzzle and wasted several hours
of their research time in pursuit of the optimal bounds for the 3-player matching.\r\npennies
problem.\r\n"
alternative_title:
- LIPIcs
article_number: 23:1-23:26
article_processing_charge: No
arxiv: 1
author:
- first_name: Leonard J
full_name: Brice, Leonard J
id: ce3b3409-db6c-11f0-aa64-ad678f7fd937
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.
last_name: Thejaswini
citation:
ama: 'Brice LJ, Henzinger TA, Thejaswini KS. Dicey games: Shared sources of randomness
in distributed systems. In: 41st Annual Symposium on Logic in Computer Science.
Vol 380. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.LICS.2026.23'
apa: 'Brice, L. J., Henzinger, T. A., & Thejaswini, K. S. (2026). Dicey games:
Shared sources of randomness in distributed systems. In 41st Annual Symposium
on Logic in Computer Science (Vol. 380). Lisbon, Portugal: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.LICS.2026.23'
chicago: 'Brice, Leonard J, Thomas A Henzinger, and K. S. Thejaswini. “Dicey Games:
Shared Sources of Randomness in Distributed Systems.” In 41st Annual Symposium
on Logic in Computer Science, Vol. 380. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026. https://doi.org/10.4230/LIPIcs.LICS.2026.23.'
ieee: 'L. J. Brice, T. A. Henzinger, and K. S. Thejaswini, “Dicey games: Shared
sources of randomness in distributed systems,” in 41st Annual Symposium on
Logic in Computer Science, Lisbon, Portugal, 2026, vol. 380.'
ista: 'Brice LJ, Henzinger TA, Thejaswini KS. 2026. Dicey games: Shared sources
of randomness in distributed systems. 41st Annual Symposium on Logic in Computer
Science. LICS: Logic in Computer Science, LIPIcs, vol. 380, 23:1-23:26.'
mla: 'Brice, Leonard J., et al. “Dicey Games: Shared Sources of Randomness in Distributed
Systems.” 41st Annual Symposium on Logic in Computer Science, vol. 380,
23:1-23:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.LICS.2026.23.'
short: L.J. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 41st Annual Symposium on
Logic in Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026.
conference:
end_date: 2026-07-23
location: Lisbon, Portugal
name: 'LICS: Logic in Computer Science'
start_date: 2026-07-20
corr_author: '1'
das_tickbox: '0'
date_created: 2026-08-02T22:01:52Z
date_published: 2026-07-09T00:00:00Z
date_updated: 2026-08-03T07:03:28Z
day: '09'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.LICS.2026.23
ec_funded: 1
external_id:
arxiv:
- '2601.18303'
file:
- access_level: open_access
checksum: 5d0ff4d267565188a8b4c7502e1bd243
content_type: application/pdf
creator: dernst
date_created: 2026-08-03T07:02:30Z
date_updated: 2026-08-03T07:02:30Z
file_id: '22625'
file_name: 2026_LIPICSLICS_Brice.pdf
file_size: 919708
relation: main_file
success: 1
file_date_updated: 2026-08-03T07:02:30Z
fulldoi: https://doi.org/10.4230/LIPIcs.LICS.2026.23
has_accepted_license: '1'
intvolume: ' 380'
keyword:
- Concurrent games
- Shared randomness
- Topology
- Algebraic Geometry
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
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: 41st Annual Symposium on Logic in Computer Science
publication_identifier:
isbn:
- '9783959774345'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Dicey games: Shared sources of randomness in distributed systems'
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: 380
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22916'
abstract:
- lang: eng
text: "In the imprecise geometry model, the input is a family of regions F = (R₁,
R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some
function of the points p₁,p₂,… p_n, in our case an implicit representation of
their Pareto front. To this end, one may query a region R_i to retrieve its contained
point p_i ∈ R_i. In this model, efficiency is interpreted in two ways: minimizing
(i) the number of retrievals, and (ii) the computation time both for preprocessing,
and the execution of the query stage, i.e. for computing which points to query
and constructing the output. \r\nWe present an algorithm to construct (an implicit
representation of) the Pareto front for possibly overlapping rectangles, that
is instance-optimal with respect to the number of retrievals. This means that
for every fixed input (F, P), there is no algorithm that retrieves asymptotically
fewer regions to compute the output. This is a strong algorithmic quality, as
it means that our algorithm is competitive even to clairvoyant algorithms which
only have to verify the correctness of a correct guess. In terms of algorithmic
running time, instance-optimality is provably unobtainable. We instead present
an algorithm which is within a log n-factor of instance optimality. This generalizes
earlier results which assumed the regions to not overlap, at only a minor cost
in running time. \r\nFor unit squares, we present an algorithm that is not only
instance optimal in the number of retrievals, but also universally optimal in
terms of running time. This means that for any fixed set of regions F, no algorithm
has a better worst-case running time for all possible point sets P. Thus, this
work presents the first universally optimal algorithm for overlapping planar input.
Compared to previous work, our result improves the degree to which the input regions
may overlap, the preprocessing time, the number of retrievals, and the running
time."
acknowledgement: This work was supported by the the VILLUM Foundation grant (VIL37507)
"Efficient Recomputations for Changeful Problems".
alternative_title:
- LIPIcs
article_number: '106'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sarita
full_name: De Berg, Sarita
last_name: De Berg
- first_name: Nynne Maria Foldager
full_name: Bække, Nynne Maria Foldager
last_name: Bække
- first_name: Frida Astrup
full_name: Eriksen, Frida Astrup
last_name: Eriksen
- first_name: Ivor
full_name: Van Der Hoog, Ivor
last_name: Van Der Hoog
- first_name: Eva
full_name: Rotenberg, Eva
last_name: Rotenberg
- first_name: Daniel P
full_name: Rutschmann, Daniel P
id: 7397d908-b582-11f0-bf73-88b902e86527
last_name: Rutschmann
citation:
ama: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
DP. Instance optimal and universally optimal bounds for imprecise pareto fronts.
In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.106'
apa: 'De Berg, S., Bække, N. M. F., Eriksen, F. A., Van Der Hoog, I., Rotenberg,
E., & Rutschmann, D. P. (2026). Instance optimal and universally optimal bounds
for imprecise pareto fronts. In 34th Annual European Symposium on Algorithms
(Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2026.106'
chicago: De Berg, Sarita, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor
Van Der Hoog, Eva Rotenberg, and Daniel P Rutschmann. “Instance Optimal and Universally
Optimal Bounds for Imprecise Pareto Fronts.” In 34th Annual European Symposium
on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026. https://doi.org/10.4230/LIPIcs.ESA.2026.106.
ieee: S. De Berg, N. M. F. Bække, F. A. Eriksen, I. Van Der Hoog, E. Rotenberg,
and D. P. Rutschmann, “Instance optimal and universally optimal bounds for imprecise
pareto fronts,” in 34th Annual European Symposium on Algorithms, L’Aquila,
Italy, 2026, vol. 388.
ista: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
DP. 2026. Instance optimal and universally optimal bounds for imprecise pareto
fronts. 34th Annual European Symposium on Algorithms. ESA: European Symposium
on Algorithms, LIPIcs, vol. 388, 106.'
mla: De Berg, Sarita, et al. “Instance Optimal and Universally Optimal Bounds for
Imprecise Pareto Fronts.” 34th Annual European Symposium on Algorithms,
vol. 388, 106, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.106.
short: S. De Berg, N.M.F. Bække, F.A. Eriksen, I. Van Der Hoog, E. Rotenberg, D.P.
Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T08:59:49Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.106
external_id:
arxiv:
- '2605.07523'
file:
- access_level: open_access
checksum: 75cfae9e9773be4b06f9aab66041f0f3
content_type: application/pdf
creator: dernst
date_created: 2026-09-16T08:58:04Z
date_updated: 2026-09-16T08:58:04Z
file_id: '22935'
file_name: 2026_LIPIcsESA_deBerg.pdf
file_size: 1102214
relation: main_file
success: 1
file_date_updated: 2026-09-16T08:58:04Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.106
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Pareto front
- imprecise geometry
- instance optimality
- universal optimality
- preprocessing model
- partial information
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959774451'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Instance optimal and universally optimal bounds for imprecise pareto fronts
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: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22915'
abstract:
- lang: eng
text: "The element distinctness problem takes as input a list I of n values from
a totally ordered universe, where pairwise comparisons between values are allowed,
and the goal is to decide whether I contains any duplicates. It is a well-studied
problem with a classical worst-case Ω(n log n) comparison-based lower bound by
Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm
more efficient than the naive approach of sorting I and comparing adjacent elements.
However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For
instance, if I contains n/2 identical elements, a median-finding algorithm will,
regardless of the input order, find a duplicate in linear time. This raises a
natural question: Are there comparison-based lower bounds for element distinctness
that are sensitive to the amount of duplicates in the input instance?\r\nTo address
this question, we derive instance-specific lower bounds. For any input instance
I, we represent the combinatorial structure of the duplicates in I by an undirected
graph G(I) that connects identical elements. Each such graph G is a union of cliques,
and we study algorithms by their worst-case running time over all inputs I' with
G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic
algorithm \U0001D49C, there exists a graph G and an algorithm \U0001D49C' that,
for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than \U0001D49C.
Consequently, no deterministic algorithm can be o(log log n)-competitive for all
graphs G. We complement this with an O(log log n)-competitive deterministic algorithm,
thereby obtaining tight bounds for element distinctness that go beyond classical
worst-case analysis. Subsequently, we study the related problem of set intersection.
We show that no deterministic set intersection algorithm can be o(log n)-competitive,
and provide an O(log n)-competitive deterministic algorithm. We find it interesting
and surprising to discover tight O(log log n)-competitive bounds for element distinctness.
Moreover, we find the separation between element distinctness and the set intersection
problem unexpected."
acknowledgement: "Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the
VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems”
for supporting this work.\r\nDaniel Rutschmann is supported by the European Research
Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation
programme (No. 101019564) "
alternative_title:
- LIPIcs
article_number: '101'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ivor
full_name: Van Der Hoog, Ivor
last_name: Van Der Hoog
- first_name: Eva
full_name: Rotenberg, Eva
last_name: Rotenberg
- first_name: Daniel P
full_name: Rutschmann, Daniel P
id: 7397d908-b582-11f0-bf73-88b902e86527
last_name: Rutschmann
citation:
ama: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. Tight Better-Than-Worst-Case bounds
for element distinctness and set intersection. In: 34th Annual European Symposium
on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2026. doi:10.4230/LIPIcs.ESA.2026.101'
apa: 'Van Der Hoog, I., Rotenberg, E., & Rutschmann, D. P. (2026). Tight Better-Than-Worst-Case
bounds for element distinctness and set intersection. In 34th Annual European
Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.101'
chicago: Van Der Hoog, Ivor, Eva Rotenberg, and Daniel P Rutschmann. “Tight Better-Than-Worst-Case
Bounds for Element Distinctness and Set Intersection.” In 34th Annual European
Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.101.
ieee: I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Tight Better-Than-Worst-Case
bounds for element distinctness and set intersection,” in 34th Annual European
Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.
ista: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Tight Better-Than-Worst-Case
bounds for element distinctness and set intersection. 34th Annual European Symposium
on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 101.'
mla: Van Der Hoog, Ivor, et al. “Tight Better-Than-Worst-Case Bounds for Element
Distinctness and Set Intersection.” 34th Annual European Symposium on Algorithms,
vol. 388, 101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.101.
short: I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European
Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T09:21:35Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.101
ec_funded: 1
external_id:
arxiv:
- '2511.02954'
file:
- access_level: open_access
checksum: c552853bfa37e4b9a0f060107e464ed0
content_type: application/pdf
creator: dernst
date_created: 2026-09-16T09:20:49Z
date_updated: 2026-09-16T09:20:49Z
file_id: '22937'
file_name: 2026_LIPIcsESA_vanderHoog.pdf
file_size: 892322
relation: main_file
success: 1
file_date_updated: 2026-09-16T09:20:49Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.101
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Comparison-based analysis
- set intersection
- universal optimality
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
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959774451'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Tight Better-Than-Worst-Case bounds for element distinctness and set intersection
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: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22918'
abstract:
- lang: eng
text: "Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating
DAGs D_1,… ,D_g such that all distances are approximately preserved: for every
pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number
of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein
[STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This
paper initiates the study of Steiner DAG cover, where the DAGs are allowed to
contain Steiner points. \r\nWe obtain Steiner DAG covers on the important classes
of planar digraphs and low-treewidth digraphs. Specifically, we show that any
digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar
digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover.\r\nWe also demonstrate
a stark difference between Steiner and non-Steiner DAG covers. As a lower bound,
we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch
t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs."
acknowledgement: "This work was initiated at Dagstuhl Seminar 25212: Metric Sketching
and\r\nDynamic Algorithms for Geometric and Topological Graphs. We thank the organizers
and other\r\nparticipants for a productive environment.\r\nujoy Bhore: Work supported
in part by ANRF ARG-MATRICS, Grant 002465.\r\nHsien-Chih Chang: Supported by the
U.S. National Science Foundation Grant No. CCF-2443017.\r\nJonathan Conroy: Supported
by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nArnold Filtser:
This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No.\r\n1042/22).\r\nEunjin
Oh: Supported by Institute of Information & Communications Technology Planning &\r\nEvaluation
(IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00440239, Sublinear\r\nScalable
Algorithms for Large-Scale Data Analysis) and the National Research Foundation of
Korea\r\n(NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505).\r\nNicole
Wein: Supported by NSF CAREER award 2541910.\r\nDa Wei Zheng: This project has received
funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open
access purposes, the author has applied a CC BY public copyright\r\nlicense to any
author-accepted manuscript version arising from this submission."
alternative_title:
- LIPIcs
article_number: 94:1-94:18
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sujoy
full_name: Bhore, Sujoy
last_name: Bhore
- first_name: Hsien Chih
full_name: Chang, Hsien Chih
last_name: Chang
- first_name: Jonathan
full_name: Conroy, Jonathan
last_name: Conroy
- first_name: Arnold
full_name: Filtser, Arnold
last_name: Filtser
- first_name: Eunjin
full_name: Oh, Eunjin
last_name: Oh
- first_name: Nicole
full_name: Wein, Nicole
last_name: Wein
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Bhore S, Chang HC, Conroy J, et al. DAG covers for structured graphs: The
Steiner point effect. In: 34th Annual European Symposium on Algorithms.
Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.94'
apa: 'Bhore, S., Chang, H. C., Conroy, J., Filtser, A., Oh, E., Wein, N., &
Zheng, D. W. (2026). DAG covers for structured graphs: The Steiner point effect.
In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.94'
chicago: 'Bhore, Sujoy, Hsien Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin
Oh, Nicole Wein, and Da Wei Zheng. “DAG Covers for Structured Graphs: The Steiner
Point Effect.” In 34th Annual European Symposium on Algorithms, Vol. 388.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.94.'
ieee: 'S. Bhore et al., “DAG covers for structured graphs: The Steiner point
effect,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy,
2026, vol. 388.'
ista: 'Bhore S, Chang HC, Conroy J, Filtser A, Oh E, Wein N, Zheng DW. 2026. DAG
covers for structured graphs: The Steiner point effect. 34th Annual European Symposium
on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 94:1-94:18.'
mla: 'Bhore, Sujoy, et al. “DAG Covers for Structured Graphs: The Steiner Point
Effect.” 34th Annual European Symposium on Algorithms, vol. 388, 94:1-94:18,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.94.'
short: S. Bhore, H.C. Chang, J. Conroy, A. Filtser, E. Oh, N. Wein, D.W. Zheng,
in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:53Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T10:27:46Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.94
external_id:
arxiv:
- '2604.04186'
file:
- access_level: open_access
checksum: 2082683b3b72865c6a795305e5d61276
content_type: application/pdf
creator: dernst
date_created: 2026-09-17T10:09:22Z
date_updated: 2026-09-17T10:09:22Z
file_id: '22948'
file_name: 2026_LIPIcsESA_Bhore.pdf
file_size: 1123327
relation: main_file
success: 1
file_date_updated: 2026-09-17T10:09:22Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.94
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Directed graphs
- DAG (directed acyclic graphs)
- distortion
- metric embeddings
- planar graph
- treewidth
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959774451'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: 'DAG covers for structured graphs: The Steiner point effect'
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: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22921'
abstract:
- lang: eng
text: 'Runtime monitoring of quantitative signals faces a fundamental trade-off
between volatility and over-aggregation: instantaneous observations are noisy,
while long-run averages obscure local structure. Localisation measures such as
discounted averages offer a principled middle ground, yet remain poorly understood
in runtime verification. This paper studies discounted sums from a monitoring
perspective, in both deterministic and stochastic settings. We formalize the discounted
monitoring problem and show that exact, sound monitoring of discounted sums cannot
be achieved with finite memory. To overcome this impossibility, we introduce ε-approximately
sound monitoring, deriving explicit bounds on memory and observation requirements.
We then extend the framework to stochastic processes via expected discounted sums,
defining pointwise and uniform (ε,δ)-soundness notions, establishing statistical
optimality, and proving impossibility beyond a precision threshold. We also formalize
the resource complexity of deterministic discounted monitoring via affine register
machines and prove a tight worst-case lower bound. Finally, we present a specification
language for arithmetic expressions over multiple discounted sums with synchronous
and asynchronous semantics, and evaluate our approach on practical scenarios including
algorithmic fairness.'
acknowledgement: "This work has been supported by the European Research Council under
Grant No.: ERC2020-AdG 101020093 and ERC-2021-AdG 101055412.\r\nFilip Cano: ERC-2020-AdG
101020093\r\nThomas A. Henzinger: ERC-2020-AdG 101020093\r\nKonstantin Kueffner:
ERC-2020-AdG 101020093\r\nN. Ege Saraç: ERC-2021-AdG 101055412"
alternative_title:
- LIPIcs
article_number: 22:1-22:19
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Filip
full_name: Cano Cordoba, Filip
id: 708cad98-e86a-11ef-8098-bdae2d7c6af1
last_name: Cano Cordoba
orcid: 0000-0002-0783-904X
- 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: Konstantin
full_name: Kueffner, Konstantin
id: 8121a2d0-dc85-11ea-9058-af578f3b4515
last_name: Kueffner
orcid: 0000-0001-8974-2542
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
citation:
ama: 'Cano Cordoba F, Henzinger TA, Kueffner K, Sarac NE. Monitoring discounted
sum properties. In: 37th International Conference on Concurrency Theory.
Vol 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.CONCUR.2026.22'
apa: 'Cano Cordoba, F., Henzinger, T. A., Kueffner, K., & Sarac, N. E. (2026).
Monitoring discounted sum properties. In 37th International Conference on Concurrency
Theory (Vol. 391). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2026.22'
chicago: Cano Cordoba, Filip, Thomas A Henzinger, Konstantin Kueffner, and Naci
E Sarac. “Monitoring Discounted Sum Properties.” In 37th International Conference
on Concurrency Theory, Vol. 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026. https://doi.org/10.4230/LIPIcs.CONCUR.2026.22.
ieee: F. Cano Cordoba, T. A. Henzinger, K. Kueffner, and N. E. Sarac, “Monitoring
discounted sum properties,” in 37th International Conference on Concurrency
Theory, Liverpool, United Kingdom, 2026, vol. 391.
ista: 'Cano Cordoba F, Henzinger TA, Kueffner K, Sarac NE. 2026. Monitoring discounted
sum properties. 37th International Conference on Concurrency Theory. CONCUR: Conference
on Concurrency Theory, LIPIcs, vol. 391, 22:1-22:19.'
mla: Cano Cordoba, Filip, et al. “Monitoring Discounted Sum Properties.” 37th
International Conference on Concurrency Theory, vol. 391, 22:1-22:19, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.CONCUR.2026.22.
short: F. Cano Cordoba, T.A. Henzinger, K. Kueffner, N.E. Sarac, in:, 37th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026.
conference:
end_date: 2026-09-04
location: Liverpool, United Kingdom
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2026-09-01
corr_author: '1'
das_tickbox: '1'
dataavailabilitystatement: "Software (Source Code): https://github.com/filipcano/monitoringdiscounted-sum-properties
[10]\r\narchived at swh:1:dir:cb99396415f279c985cd05206b44320227f64245\r\n"
date_created: 2026-09-13T22:01:54Z
date_published: 2026-08-24T00:00:00Z
date_updated: 2026-09-22T06:02:06Z
day: '24'
ddc:
- '000'
department:
- _id: ToHe
- _id: GradSch
doi: 10.4230/LIPIcs.CONCUR.2026.22
ec_funded: 1
external_id:
arxiv:
- '2606.25979'
file:
- access_level: open_access
checksum: f7b2e22428344fd7972c54f099df6aba
content_type: application/pdf
creator: dernst
date_created: 2026-09-22T05:59:03Z
date_updated: 2026-09-22T05:59:03Z
file_id: '22978'
file_name: 2026_LIPIcsCONCUR_Cano.pdf
file_size: 997156
relation: main_file
success: 1
file_date_updated: 2026-09-22T05:59:03Z
fulldoi: https://doi.org/10.4230/LIPIcs.CONCUR.2026.22
has_accepted_license: '1'
intvolume: ' 391'
keyword:
- Runtime Verification
- Probabilistic Systems
- Quantitative Verification
- Approximate Monitoring
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: 37th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959774475'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Monitoring discounted sum properties
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: 391
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22922'
abstract:
- lang: eng
text: In this note, we recall the history and our motivation behind the development
of Strategy Logic and we discuss some of the work that ensued from its introduction.
acknowledgement: " Krishnendu Chatterjee: Supported in part by the Austrian Science
Fund (FWF) COE\r\ngrant 10.55776/COE12 and the ERC CoG 863818 (ForM-SMArt).\r\nThomas
A. Henzinger: Supported in part by the ERC AdG 101020093 (VAMOS) and the FWF\r\nSFB
grant F8502 (SPyCoDe).\r\nNir Piterman: Supported in part by the Swedish research
council (VR) project no. 2025-05419 and\r\nthe Wallenberg AI, Autonomous Systems
and Software Program (WASP) funded by the Knut and\r\nAlice Wallenberg Foundation.\r\nAcknowledgements
We thank the jury that our paper introducing Strategy Logic at the Conference\r\non
Concurrency Theory (CONCUR) 2007 [10] was chosen for a CONCUR Test-of-Time Award
at\r\nCONCUR 2026."
alternative_title:
- LIPIcs
article_number: 6:1-6:7
article_processing_charge: Yes
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- 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: Nir
full_name: Piterman, Nir
last_name: Piterman
citation:
ama: 'Chatterjee K, Henzinger TA, Piterman N. A look back at strategy logic. In:
37th International Conference on Concurrency Theory. Vol 391. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.CONCUR.2026.6'
apa: 'Chatterjee, K., Henzinger, T. A., & Piterman, N. (2026). A look back at
strategy logic. In 37th International Conference on Concurrency Theory
(Vol. 391). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2026.6'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “A Look Back
at Strategy Logic.” In 37th International Conference on Concurrency Theory,
Vol. 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.CONCUR.2026.6.
ieee: K. Chatterjee, T. A. Henzinger, and N. Piterman, “A look back at strategy
logic,” in 37th International Conference on Concurrency Theory, Liverpool,
United Kingdom, 2026, vol. 391.
ista: 'Chatterjee K, Henzinger TA, Piterman N. 2026. A look back at strategy logic.
37th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 391, 6:1-6:7.'
mla: Chatterjee, Krishnendu, et al. “A Look Back at Strategy Logic.” 37th International
Conference on Concurrency Theory, vol. 391, 6:1-6:7, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026, doi:10.4230/LIPIcs.CONCUR.2026.6.
short: K. Chatterjee, T.A. Henzinger, N. Piterman, in:, 37th International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-09-04
location: Liverpool, United Kingdom
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2026-09-01
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:54Z
date_published: 2026-08-24T00:00:00Z
date_updated: 2026-09-22T05:54:30Z
day: '24'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2026.6
ec_funded: 1
file:
- access_level: open_access
checksum: f3995df175701f56a702bdb012e4f710
content_type: application/pdf
creator: dernst
date_created: 2026-09-22T05:53:16Z
date_updated: 2026-09-22T05:53:16Z
file_id: '22977'
file_name: 2026_LIPIcsCONCUR_Chatterjee.pdf
file_size: 517651
relation: main_file
success: 1
file_date_updated: 2026-09-22T05:53:16Z
fulldoi: https://doi.org/10.4230/LIPIcs.CONCUR.2026.6
has_accepted_license: '1'
intvolume: ' 391'
keyword:
- Strategy Logic
- Games
- Automata
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
- _id: 34a1b658-11ca-11ed-8bc3-c75229f0241e
grant_number: F8502
name: Interface Theory for Security and Privacy
publication: 37th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959774475'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: A look back at strategy logic
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: 391
year: '2026'
...
---
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
fulldoi: https://doi.org/10.4230/LIPIcs.ITCS.2025.82
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: '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
fulldoi: https://doi.org/10.4230/LIPIcs.SAND.2025.4
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
fulldoi: https://doi.org/10.4230/LIPIcs.CONCUR.2025.21
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
fulldoi: https://doi.org/10.4230/LIPIcs.MFCS.2025.30
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
fulldoi: https://doi.org/10.4230/LIPIcs.MFCS.2025.57
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
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2025.2
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
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2025.36
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
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2025.91
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
fulldoi: https://doi.org/10.4230/LIPIcs.WADS.2025.47
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: '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
fulldoi: https://doi.org/10.4230/LIPIcs.AFT.2025.16
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'
...
---
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
cryptoeprintid: 1
date_created: 2026-03-08T23:01:46Z
date_published: 2025-10-22T00:00:00Z
date_updated: 2026-09-16T07:27:09Z
day: '22'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.DISC.2025.23
ec_funded: 1
external_id:
arxiv:
- '2508.14524'
cryptoeprintid:
- 2025/1484
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
fulldoi: https://doi.org/10.4230/LIPIcs.DISC.2025.23
has_accepted_license: '1'
intvolume: ' 356'
language:
- iso: eng
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'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
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'
...
---
_id: '17144'
abstract:
- lang: eng
text: "We prove that the medial axis of closed sets is Hausdorff stable in the following
sense: Let \U0001D4AE ⊆ ℝ^d be a fixed closed set that contains a bounding sphere.
That is, the bounding sphere is part of the set \U0001D4AE. Consider the space
of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant.
The map from this space of diffeomorphisms (endowed with a Banach norm) to the
space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping
a diffeomorphism F to the closure of the medial axis of F(\U0001D4AE), is Lipschitz.
This extends a previous stability result of Chazal and Soufflet on the stability
of the medial axis of C² manifolds under C² ambient diffeomorphisms."
acknowledgement: "This research has been supported by the European Research Council
(ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF),
grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian
Science Fund (FWF), grant No. I 02979-N35.\r\nSupported by the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
grant agreement No. 754411, the Austrian science fund (FWF) grant No. M-3073, and
the welcome package from IDEX of the Université Cô d'Azur.\r\nWe are greatly indebted
to Fred Chazal for sharing his insights. We further thank Erin Chambers, Christopher
Fillmore, and Elizabeth Stephenson for early discussions and all members of the
Edelsbrunner group (Institute of Science and Technology Austria) and the Datashape
team (Inria) for the atmosphere in which this research was conducted."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: No
arxiv: 1
author:
- first_name: Hana
full_name: Kourimska, Hana
id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
last_name: Kourimska
orcid: 0000-0001-7841-0091
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Kourimska H, Lieutier A, Wintraecken M. The medial axis of any closed bounded
set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms.
In: 40th International Symposium on Computational Geometry. Vol 293. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.69'
apa: 'Kourimska, H., Lieutier, A., & Wintraecken, M. (2024). The medial axis
of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance
Under ambient diffeomorphisms. In 40th International Symposium on Computational
Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.69'
chicago: Kourimska, Hana, André Lieutier, and Mathijs Wintraecken. “The Medial Axis
of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance
Under Ambient Diffeomorphisms.” In 40th International Symposium on Computational
Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.SoCG.2024.69.
ieee: H. Kourimska, A. Lieutier, and M. Wintraecken, “The medial axis of any closed
bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient
diffeomorphisms,” in 40th International Symposium on Computational Geometry,
Athens, Greece, 2024, vol. 293.
ista: 'Kourimska H, Lieutier A, Wintraecken M. 2024. The medial axis of any closed
bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient
diffeomorphisms. 40th International Symposium on Computational Geometry. SoCG:
Symposium on Computational Geometry, LIPIcs, vol. 293, 69.'
mla: Kourimska, Hana, et al. “The Medial Axis of Any Closed Bounded Set Is Lipschitz
Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.”
40th International Symposium on Computational Geometry, vol. 293, 69, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.69.
short: H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium
on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
das_tickbox: '0'
date_created: 2024-06-16T22:01:06Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2026-10-02T11:46:39Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.69
ec_funded: 1
external_id:
arxiv:
- '2212.01118'
file:
- access_level: open_access
checksum: b40ff456c19294adb5d9613fcfd751c6
content_type: application/pdf
creator: dernst
date_created: 2024-06-17T08:33:40Z
date_updated: 2024-06-17T08:33:40Z
file_id: '17150'
file_name: 2024_LIPICS_Kourimska.pdf
file_size: 1612558
relation: main_file
success: 1
file_date_updated: 2024-06-17T08:33:40Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2024.69
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
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
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: 40th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959773164'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: The medial axis of any closed bounded set Is Lipschitz stable with respect
to the Hausdorff distance Under ambient diffeomorphisms
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: 293
year: '2024'
...
---
_id: '17146'
abstract:
- lang: eng
text: The Upper Bound Theorem for convex polytopes implies that the p-th Betti number
of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p
= O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions,
which prove that this upper bound is asymptotically tight. For example, we describe
a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number
of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of
the Čech complex at the other radius is n². In particular, there is an arrangement
of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers
a long-standing open question in computational geometry.
acknowledgement: "The first author is supported by the European Research Council (ERC),
grant no. 788183, and by the DFG Collaborative Research Center TRR 109, Austrian
Science Fund (FWF), grant no. {I 02979-N35.} The second author is supported by the
European Research Council (ERC), grant \"GeoScape\" and by the Hungarian Science
Foundation (NKFIH), grant K-131529. Both authors are supported by the Wittgenstein
Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.\r\nThe authors thank Matt
Kahle for communicating the question about extremal Čech complexes, Ben Schweinhart
for early discussions on the linked circles construction in three dimensions, and
Gábor Tardos for helpful remarks and suggestions."
alternative_title:
- LIPIcs
article_number: '53'
article_processing_charge: No
arxiv: 1
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
citation:
ama: 'Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: 40th
International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.53'
apa: 'Edelsbrunner, H., & Pach, J. (2024). Maximum Betti numbers of Čech complexes.
In 40th International Symposium on Computational Geometry (Vol. 293). Athens,
Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.53'
chicago: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.”
In 40th International Symposium on Computational Geometry, Vol. 293. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.53.
ieee: H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in
40th International Symposium on Computational Geometry, Athens, Greece,
2024, vol. 293.
ista: 'Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th
International Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, LIPIcs, vol. 293, 53.'
mla: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.”
40th International Symposium on Computational Geometry, vol. 293, 53, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.53.
short: H. Edelsbrunner, J. Pach, in:, 40th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2024-06-11
das_tickbox: '0'
date_created: 2024-06-16T22:01:06Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2026-10-02T11:48:01Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.53
ec_funded: 1
external_id:
arxiv:
- '2310.14801'
file:
- access_level: open_access
checksum: 5442d44fb89d77477a87668d6e61aac9
content_type: application/pdf
creator: dernst
date_created: 2024-06-17T08:46:33Z
date_updated: 2024-06-17T08:46:33Z
file_id: '17152'
file_name: 2024_LIPICS_Edelsbrunner.pdf
file_size: 766562
relation: main_file
success: 1
file_date_updated: 2024-06-17T08:46:33Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2024.53
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
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: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: 40th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959773164'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '20657'
relation: later_version
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Maximum Betti numbers of Čech complexes
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: 293
year: '2024'
...
---
_id: '17145'
abstract:
- lang: eng
text: Grid peeling is the process of repeatedly removing the convex hull vertices
of the grid points that lie inside a given convex curve. It has been conjectured
that, for a more and more refined grid, grid peeling converges to a continuous
process, the affine curve-shortening flow, which deforms the curve based on the
curvature. We prove this conjecture for one class of curves, parabolas with a
vertical axis, and we determine the value of the constant factor in the formula
that relates the two processes.
acknowledgement: Part of this work was done while G.R. enjoyed the hospitality of
the Institute of Science and Technology Austria (ISTA) as a visiting professor during
his sabbatical in the winter semester 2022/23.
alternative_title:
- LIPIcs
article_number: '76'
article_processing_charge: No
arxiv: 1
author:
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
- first_name: Moritz
full_name: Rüber, Moritz
last_name: Rüber
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: 'Rote G, Rüber M, Saghafian M. Grid peeling of parabolas. In: 40th International
Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.76'
apa: 'Rote, G., Rüber, M., & Saghafian, M. (2024). Grid peeling of parabolas.
In 40th International Symposium on Computational Geometry (Vol. 293). Athens,
Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.76'
chicago: Rote, Günter, Moritz Rüber, and Morteza Saghafian. “Grid Peeling of Parabolas.”
In 40th International Symposium on Computational Geometry, Vol. 293. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.76.
ieee: G. Rote, M. Rüber, and M. Saghafian, “Grid peeling of parabolas,” in 40th
International Symposium on Computational Geometry, Athens, Greece, 2024, vol.
293.
ista: 'Rote G, Rüber M, Saghafian M. 2024. Grid peeling of parabolas. 40th International
Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
LIPIcs, vol. 293, 76.'
mla: Rote, Günter, et al. “Grid Peeling of Parabolas.” 40th International Symposium
on Computational Geometry, vol. 293, 76, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.76.
short: G. Rote, M. Rüber, M. Saghafian, in:, 40th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-06-14
location: Athens, Greece
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2024-06-11
das_tickbox: '0'
date_created: 2024-06-16T22:01:06Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2026-10-02T11:47:18Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.76
external_id:
arxiv:
- '2402.15787'
file:
- access_level: open_access
checksum: fbad1de06383a6b7e8a1cb3e8c7205ce
content_type: application/pdf
creator: dernst
date_created: 2024-06-17T08:40:04Z
date_updated: 2024-06-17T08:40:04Z
file_id: '17151'
file_name: 2024_LIPICS_Rote.pdf
file_size: 1430896
relation: main_file
success: 1
file_date_updated: 2024-06-17T08:40:04Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2024.76
has_accepted_license: '1'
intvolume: ' 293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 40th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959773164'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Grid peeling of parabolas
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: 293
year: '2024'
...