---
_id: '17327'
abstract:
- lang: eng
text: Sequential decision-making in probabilistic environments is a fundamental
problem with many applications in AI and economics. In this paper, we present
an algorithm for synthesizing sequential decision-making agents that optimize
statistical properties such as maximum and average response times. In the general
setting of sequential decision-making, the environment is modeled as a random
process that generates inputs. The agent responds to each input, aiming to maximize
rewards and minimize costs within a specified time horizon. The corresponding
synthesis problem is known to be PSPACE-hard. We consider the special case where
the input distribution, reward, and cost depend on input-output statistics specified
by counter automata. For such problems, this paper presents the first PTIME synthesis
algorithms. We introduce the notion of statistical abstraction, which clusters
statistically indistinguishable input-output sequences into equivalence classes.
This abstraction allows for a dynamic programming algorithm whose complexity grows
polynomially with the considered horizon, making the statistical case exponentially
more efficient than the general case. We evaluate our algorithm on three different
application scenarios of a client-server protocol, where multiple clients compete
via bidding to gain access to the service offered by the server. The synthesized
policies optimize profit while guaranteeing that none of the server’s clients
is disproportionately starved of the service.
acknowledgement: "This work is partly supported by the European Research Council under
Grant No.: ERC2020-AdG 101020093. It is also partially supported by the State Government
of Styria, Austria –\r\nDepartment Zukunftsfonds Steiermark."
alternative_title:
- LIPIcs
article_number: '2'
article_processing_charge: Yes
author:
- first_name: Filip
full_name: Cano, Filip
last_name: Cano
- 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: Bettina
full_name: Könighofer, Bettina
last_name: Könighofer
- first_name: Konstantin
full_name: Kueffner, Konstantin
id: 8121a2d0-dc85-11ea-9058-af578f3b4515
last_name: Kueffner
orcid: 0000-0001-8974-2542
- first_name: Kaushik
full_name: Mallik, Kaushik
id: 0834ff3c-6d72-11ec-94e0-b5b0a4fb8598
last_name: Mallik
orcid: 0000-0001-9864-7475
citation:
ama: 'Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. Abstraction-based
decision making for statistical properties. In: 9th International Conference
on Formal Structures for Computation and Deduction. Vol 299. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.FSCD.2024.2'
apa: 'Cano, F., Henzinger, T. A., Könighofer, B., Kueffner, K., & Mallik, K.
(2024). Abstraction-based decision making for statistical properties. In 9th
International Conference on Formal Structures for Computation and Deduction
(Vol. 299). Tallinn, Estonia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.FSCD.2024.2'
chicago: Cano, Filip, Thomas A Henzinger, Bettina Könighofer, Konstantin Kueffner,
and Kaushik Mallik. “Abstraction-Based Decision Making for Statistical Properties.”
In 9th International Conference on Formal Structures for Computation and Deduction,
Vol. 299. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.FSCD.2024.2.
ieee: F. Cano, T. A. Henzinger, B. Könighofer, K. Kueffner, and K. Mallik, “Abstraction-based
decision making for statistical properties,” in 9th International Conference
on Formal Structures for Computation and Deduction, Tallinn, Estonia, 2024,
vol. 299.
ista: 'Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. 2024. Abstraction-based
decision making for statistical properties. 9th International Conference on Formal
Structures for Computation and Deduction. FSCD: Conference on Formal Structures
for Computation and Deduction, LIPIcs, vol. 299, 2.'
mla: Cano, Filip, et al. “Abstraction-Based Decision Making for Statistical Properties.”
9th International Conference on Formal Structures for Computation and Deduction,
vol. 299, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.FSCD.2024.2.
short: F. Cano, T.A. Henzinger, B. Könighofer, K. Kueffner, K. Mallik, in:, 9th
International Conference on Formal Structures for Computation and Deduction, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-07-13
location: Tallinn, Estonia
name: 'FSCD: Conference on Formal Structures for Computation and Deduction'
start_date: 2024-07-10
corr_author: '1'
date_created: 2024-07-28T22:01:09Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2025-12-02T13:43:50Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.FSCD.2024.2
ec_funded: 1
external_id:
isi:
- '001587746100002'
file:
- access_level: open_access
checksum: cc6bb89be0eaa404a6ce019392cd293e
content_type: application/pdf
creator: dernst
date_created: 2024-07-29T11:15:59Z
date_updated: 2024-07-29T11:15:59Z
file_id: '17341'
file_name: 2024_LIPICs_Cano.pdf
file_size: 1391381
relation: main_file
success: 1
file_date_updated: 2024-07-29T11:15:59Z
has_accepted_license: '1'
intvolume: ' 299'
isi: 1
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: 9th International Conference on Formal Structures for Computation and
Deduction
publication_identifier:
isbn:
- '9783959773232'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Abstraction-based decision making for statistical 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: 299
year: '2024'
...
---
_id: '18066'
abstract:
- lang: eng
text: 'Graph games lie at the algorithmic core of many automated design problems
in computer science. These are games usually played between two players on a given
graph, where the players keep moving a token along the edges according to pre-determined
rules (turn-based, concurrent, etc.), and the winner is decided based on the infinite
path (aka play) traversed by the token from a given initial position. In bidding
games, the players initially get some monetary budgets which they need to use
to bid for the privilege of moving the token at each step. Each round of bidding
affects the players'' available budgets, which is the only form of update that
the budgets experience. We introduce bidding games with charging where the players
can additionally improve their budgets during the game by collecting vertex-dependent
monetary rewards, aka the "charges." Unlike traditional bidding games (where all
charges are zero), bidding games with charging allow non-trivial recurrent behaviors.
For example, a reachability objective may require multiple detours to vertices
with high charges to earn additional budget. We show that, nonetheless, the central
property of traditional bidding games generalizes to bidding games with charging:
For each vertex there exists a threshold ratio, which is the necessary and sufficient
fraction of the total budget for winning the game from that vertex. While the
thresholds of traditional bidding games correspond to unique fixed points of linear
systems of equations, in games with charging, these fixed points are no longer
unique. This significantly complicates the proof of existence and the algorithmic
computation of thresholds for infinite-duration objectives. We also provide the
lower complexity bounds for computing thresholds for Rabin and Streett objectives,
which are the first known lower bounds in any form of bidding games (with or without
charging), and we solve the following repair problem for safety and reachability
games that have unsatisfiable objectives: Can we distribute a given amount of
charge to the players in a way such that the objective can be satisfied?'
acknowledgement: This work was supported in part by the ERC projects ERC-2020-AdG
101020093 and CoG 863818 (ForM-SMArt) and by ISF grant no. 1679/21.
alternative_title:
- LIPIcs
article_number: '8'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- first_name: Ehsan Kafshdar
full_name: Goharshady, Ehsan Kafshdar
last_name: Goharshady
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Kaushik
full_name: Mallik, Kaushik
id: 0834ff3c-6d72-11ec-94e0-b5b0a4fb8598
last_name: Mallik
orcid: 0000-0001-9864-7475
citation:
ama: 'Avni G, Goharshady EK, Henzinger TA, Mallik K. Bidding games with charging.
In: 35th International Conference on Concurrency Theory. Vol 311. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.CONCUR.2024.8'
apa: 'Avni, G., Goharshady, E. K., Henzinger, T. A., & Mallik, K. (2024). Bidding
games with charging. In 35th International Conference on Concurrency Theory
(Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CONCUR.2024.8'
chicago: Avni, Guy, Ehsan Kafshdar Goharshady, Thomas A Henzinger, and Kaushik Mallik.
“Bidding Games with Charging.” In 35th International Conference on Concurrency
Theory, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.CONCUR.2024.8.
ieee: G. Avni, E. K. Goharshady, T. A. Henzinger, and K. Mallik, “Bidding games
with charging,” in 35th International Conference on Concurrency Theory,
Calgary, Canada, 2024, vol. 311.
ista: 'Avni G, Goharshady EK, Henzinger TA, Mallik K. 2024. Bidding games with charging.
35th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 311, 8.'
mla: Avni, Guy, et al. “Bidding Games with Charging.” 35th International Conference
on Concurrency Theory, vol. 311, 8, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.CONCUR.2024.8.
short: G. Avni, E.K. Goharshady, T.A. Henzinger, K. Mallik, in:, 35th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2024-09-13
location: Calgary, Canada
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2024-09-09
corr_author: '1'
date_created: 2024-09-15T22:01:39Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:46:11Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2024.8
ec_funded: 1
external_id:
arxiv:
- '2407.06288'
isi:
- '001556847400008'
file:
- access_level: open_access
checksum: cb6f2254b84922cd7bf224f550b73f4a
content_type: application/pdf
creator: dernst
date_created: 2024-09-17T09:35:03Z
date_updated: 2024-09-17T09:35:03Z
file_id: '18083'
file_name: 2024_LIPICS_Avni.pdf
file_size: 854430
relation: main_file
success: 1
file_date_updated: 2024-09-17T09:35:03Z
has_accepted_license: '1'
intvolume: ' 311'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 35th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959773393'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bidding games with charging
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 311
year: '2024'
...
---
_id: '18067'
abstract:
- lang: eng
text: "An automaton \U0001D49C is history-deterministic if its nondeterminism can
be resolved on the fly, only using the prefix of the word read so far. This mild
form of nondeterminism has attracted particular attention for its applications
in synthesis problems. An automaton \U0001D49C is guidable with respect to a class
C of automata if it can fairly simulate every automaton in C, whose language is
contained in that of \U0001D49C. In other words, guidable automata are those for
which inclusion and simulation coincide, making them particularly interesting
for model-checking. We study the connection between these two notions, and specifically
the question of when they coincide. For classes of automata on which they do,
deciding guidability, an otherwise challenging decision problem, reduces to deciding
history-determinism, a problem that is starting to be well-understood for many
classes. We provide a selection of sufficient criteria for a class of automata
to guarantee the coincidence of the notions, and use them to show that the notions
coincide for the most common automata classes, among which are ω-regular automata
and many infinite-state automata with safety and reachability acceptance conditions,
including vector addition systems with states, one-counter nets, pushdown-, Parikh-,
and timed-automata. We also demonstrate that history-determinism and guidability
do not always coincide, for example, for the classes of timed automata with a
fixed number of clocks."
acknowledgement: "Udi Boker: Israel Science Foundation grant 2410/22\r\nThomas A.
Henzinger: ERC-2020-AdG 101020093 (VAMOS)\r\nKaroliina Lehtinen: ANR QUASY 23-CE48-0008-01\r\nAditya
Prakash: Chancellors’ International Scholarship from the University of Warwick and
Centre for Discrete Mathematics and Its Applications (DIMAP)"
alternative_title:
- LIPIcs
article_number: '12'
article_processing_charge: No
arxiv: 1
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Karoliina
full_name: Lehtinen, Karoliina
last_name: Lehtinen
- first_name: Aditya
full_name: Prakash, Aditya
last_name: Prakash
citation:
ama: 'Boker U, Henzinger TA, Lehtinen K, Prakash A. History-determinism vs fair
simulation. In: 35th International Conference on Concurrency Theory. Vol
311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.CONCUR.2024.12'
apa: 'Boker, U., Henzinger, T. A., Lehtinen, K., & Prakash, A. (2024). History-determinism
vs fair simulation. In 35th International Conference on Concurrency Theory
(Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CONCUR.2024.12'
chicago: Boker, Udi, Thomas A Henzinger, Karoliina Lehtinen, and Aditya Prakash.
“History-Determinism vs Fair Simulation.” In 35th International Conference
on Concurrency Theory, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024. https://doi.org/10.4230/LIPIcs.CONCUR.2024.12.
ieee: U. Boker, T. A. Henzinger, K. Lehtinen, and A. Prakash, “History-determinism
vs fair simulation,” in 35th International Conference on Concurrency Theory,
Calgary, Canada, 2024, vol. 311.
ista: 'Boker U, Henzinger TA, Lehtinen K, Prakash A. 2024. History-determinism vs
fair simulation. 35th International Conference on Concurrency Theory. CONCUR:
Conference on Concurrency Theory, LIPIcs, vol. 311, 12.'
mla: Boker, Udi, et al. “History-Determinism vs Fair Simulation.” 35th International
Conference on Concurrency Theory, vol. 311, 12, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024, doi:10.4230/LIPIcs.CONCUR.2024.12.
short: U. Boker, T.A. Henzinger, K. Lehtinen, A. Prakash, in:, 35th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2024-09-13
location: Calgary, Canada
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2024-09-09
corr_author: '1'
date_created: 2024-09-15T22:01:40Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:44:54Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2024.12
ec_funded: 1
external_id:
arxiv:
- '2407.08620'
isi:
- '001556847400012'
file:
- access_level: open_access
checksum: 66db11ef8e600a434079c278050c3f09
content_type: application/pdf
creator: dernst
date_created: 2024-09-17T07:31:18Z
date_updated: 2024-09-17T07:31:18Z
file_id: '18080'
file_name: 2024_LIPICS_Boker.pdf
file_size: 766902
relation: main_file
success: 1
file_date_updated: 2024-09-17T07:31:18Z
has_accepted_license: '1'
intvolume: ' 311'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 35th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959773393'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: History-determinism vs fair simulation
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 311
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18068'
abstract:
- lang: eng
text: "We study the following refinement relation between nondeterministic state-transition
models: model ℬ strategically dominates model \U0001D49C iff every deterministic
refinement of \U0001D49C is language contained in some deterministic refinement
of ℬ. While language containment is trace inclusion, and the (fair) simulation
preorder coincides with tree inclusion, strategic dominance falls strictly between
the two and can be characterized as \"strategy inclusion\" between \U0001D49C
and ℬ: every strategy that resolves the nondeterminism of \U0001D49C is dominated
by a strategy that resolves the nondeterminism of ℬ. Strategic dominance can be
checked in 2-ExpTime by a decidable first-order Presburger logic with quantification
over words and strategies, called resolver logic. We give several other applications
of resolver logic, including checking the co-safety, co-liveness, and history-determinism
of boolean and quantitative automata, and checking the inclusion between hyperproperties
that are specified by nondeterministic boolean and quantitative automata."
acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093. N.
Mazzocchi was affiliated with ISTA when this work was submitted for publication.
alternative_title:
- LIPIcs
article_number: '29'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Nicolas Adrien
full_name: Mazzocchi, Nicolas Adrien
id: b26baa86-3308-11ec-87b0-8990f34baa85
last_name: Mazzocchi
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
citation:
ama: 'Henzinger TA, Mazzocchi NA, Sarac NE. Strategic dominance: A new preorder
for nondeterministic processes. In: 35th International Conference on Concurrency
Theory. Vol 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024.
doi:10.4230/LIPIcs.CONCUR.2024.29'
apa: 'Henzinger, T. A., Mazzocchi, N. A., & Sarac, N. E. (2024). Strategic dominance:
A new preorder for nondeterministic processes. In 35th International Conference
on Concurrency Theory (Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2024.29'
chicago: 'Henzinger, Thomas A, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Strategic
Dominance: A New Preorder for Nondeterministic Processes.” In 35th International
Conference on Concurrency Theory, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024. https://doi.org/10.4230/LIPIcs.CONCUR.2024.29.'
ieee: 'T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Strategic dominance:
A new preorder for nondeterministic processes,” in 35th International Conference
on Concurrency Theory, Calgary, Canada, 2024, vol. 311.'
ista: 'Henzinger TA, Mazzocchi NA, Sarac NE. 2024. Strategic dominance: A new preorder
for nondeterministic processes. 35th International Conference on Concurrency Theory.
CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 311, 29.'
mla: 'Henzinger, Thomas A., et al. “Strategic Dominance: A New Preorder for Nondeterministic
Processes.” 35th International Conference on Concurrency Theory, vol. 311,
29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.CONCUR.2024.29.'
short: T.A. Henzinger, N.A. Mazzocchi, N.E. Sarac, in:, 35th International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-13
location: Calgary, Canada
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2024-09-09
corr_author: '1'
date_created: 2024-09-15T22:01:40Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:45:38Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
- _id: GradSch
doi: 10.4230/LIPIcs.CONCUR.2024.29
ec_funded: 1
external_id:
arxiv:
- '2407.10473'
isi:
- '001556847400029'
file:
- access_level: open_access
checksum: 555bd343e1fb38adeab8fc465ff4fad8
content_type: application/pdf
creator: dernst
date_created: 2024-09-17T07:48:56Z
date_updated: 2024-09-17T07:48:56Z
file_id: '18081'
file_name: 2024_LIPICS_Henzinger.pdf
file_size: 964124
relation: main_file
success: 1
file_date_updated: 2024-09-17T07:48:56Z
has_accepted_license: '1'
intvolume: ' 311'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 35th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959773393'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Strategic dominance: A new preorder for nondeterministic processes'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 311
year: '2024'
...
---
_id: '18156'
abstract:
- lang: eng
text: Privately counting distinct elements in a stream is a fundamental data analysis
problem with many applications in machine learning. In the turnstile model, Jain
et al. [NeurIPS2023] initiated the study of this problem parameterized by the
maximum flippancy of any element, i.e., the number of times that the count of
an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially
private algorithm whose additive error is tight with respect to that parameterization.
In this work, we show that a very simple algorithm based on the sparse vector
technique achieves a tight additive error for item-level (ε,δ)-differential privacy
and item-level ε-differential privacy with regards to a different parameterization,
namely the sum of all flippancies. Our second result is a bound which shows that
for a large class of algorithms, including all existing differentially private
algorithms for this problem, the lower bound from item-level differential privacy
extends to event-level differential privacy. This partially answers an open question
by Jain et al. [NeurIPS2023].
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nTeresa Anna
Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN."
alternative_title:
- LIPIcs
article_number: '40'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
- first_name: Teresa Anna
full_name: Steiner, Teresa Anna
last_name: Steiner
citation:
ama: 'Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements
in the turnstile model and extensions. In: International Conference on Approximation
Algorithms for Combinatorial Optimization Problems . Vol 317. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40'
apa: 'Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2024). Private counting
of distinct elements in the turnstile model and extensions. In International
Conference on Approximation Algorithms for Combinatorial Optimization Problems
(Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40'
chicago: Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting
of Distinct Elements in the Turnstile Model and Extensions.” In International
Conference on Approximation Algorithms for Combinatorial Optimization Problems
, Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40.
ieee: M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct
elements in the turnstile model and extensions,” in International Conference
on Approximation Algorithms for Combinatorial Optimization Problems , London,
United Kingdom, 2024, vol. 317.
ista: 'Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct
elements in the turnstile model and extensions. International Conference on Approximation
Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation
Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.'
mla: Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile
Model and Extensions.” International Conference on Approximation Algorithms
for Combinatorial Optimization Problems , vol. 317, 40, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40.
short: M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference
on Approximation Algorithms for Combinatorial Optimization Problems , Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-08-30
location: London, United Kingdom
name: 'APPROX: Conference on Approximation Algorithms for Combinatorial Optimization
Problems'
start_date: 2024-08-27
corr_author: '1'
date_created: 2024-09-29T22:01:38Z
date_published: 2024-09-16T00:00:00Z
date_updated: 2025-12-02T13:47:16Z
day: '16'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.APPROX/RANDOM.2024.40
ec_funded: 1
external_id:
arxiv:
- '2408.11637'
isi:
- '001545634500040'
file:
- access_level: open_access
checksum: c08b41c896e4d8c69570044808b40e0b
content_type: application/pdf
creator: dernst
date_created: 2024-10-01T10:07:14Z
date_updated: 2024-10-01T10:07:14Z
file_id: '18166'
file_name: 2024_LIPICs_HenzingerM.pdf
file_size: 973917
relation: main_file
success: 1
file_date_updated: 2024-10-01T10:07:14Z
has_accepted_license: '1'
intvolume: ' 317'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: 'International Conference on Approximation Algorithms for Combinatorial
Optimization Problems '
publication_identifier:
isbn:
- '9783959773485'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Private counting of distinct elements in the turnstile model and extensions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 317
year: '2024'
...
---
_id: '18175'
abstract:
- lang: eng
text: Large-scale software repositories are a source of insights for software engineering.
They offer an unmatched window into the software development process at scale.
Their sheer number and size holds the promise of broadly applicable results. At
the same time, that very size presents practical challenges for scaling tools
and algorithms to millions of projects. A reasonable approach is to limit studies
to representative samples of the population of interest. Broadly applicable conclusions
can then be obtained by generalizing to the entire population. The contribution
of this paper is a standardized experimental design methodology for choosing the
inputs of studies working with large-scale repositories. We advocate for a methodology
that clearly lays out what the population of interest is, how to sample it, and
that fosters reproducibility. Along the way, we discourage researchers from using
extrinsic attributes of projects such as stars, that measure some unclear notion
of popularity.
acknowledgement: "This work was supported by the Czech Ministry of Education, Youth
and Sports under\r\nprogram ERC-CZ, grant agreement LL2325, BigCode (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000421).
NSF grants CCF-1910850, CNS-1925644, and CCF-2139612, as well as the GACR EXPRO
grant 23-07580X. We would like to thank Digital Ocean for their involuntary contribution
of computational resources during the early data gathering phase of our research.
We acknoweldge the reviewers of ICSE’22, and thank the reviewers of ECOOP’23 for
their encouragments and for sticking around until 2024."
alternative_title:
- LIPIcs
article_number: '27'
article_processing_charge: No
author:
- first_name: Petr
full_name: Maj, Petr
last_name: Maj
- first_name: Stefanie
full_name: Muroya Lei, Stefanie
id: a376de31-8972-11ed-ae7b-d0251c13c8ff
last_name: Muroya Lei
- first_name: Konrad
full_name: Siek, Konrad
last_name: Siek
- first_name: Luca
full_name: Di Grazia, Luca
last_name: Di Grazia
- first_name: Jan
full_name: Vitek, Jan
last_name: Vitek
citation:
ama: 'Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. The fault in our stars:
Designing reproducible large-scale code analysis experiments. In: 38th European
Conference on Object-Oriented Programming. Vol 313. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.ECOOP.2024.27'
apa: 'Maj, P., Muroya Lei, S., Siek, K., Di Grazia, L., & Vitek, J. (2024).
The fault in our stars: Designing reproducible large-scale code analysis experiments.
In 38th European Conference on Object-Oriented Programming (Vol. 313).
Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ECOOP.2024.27'
chicago: 'Maj, Petr, Stefanie Muroya Lei, Konrad Siek, Luca Di Grazia, and Jan Vitek.
“The Fault in Our Stars: Designing Reproducible Large-Scale Code Analysis Experiments.”
In 38th European Conference on Object-Oriented Programming, Vol. 313. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ECOOP.2024.27.'
ieee: 'P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, and J. Vitek, “The fault in
our stars: Designing reproducible large-scale code analysis experiments,” in 38th
European Conference on Object-Oriented Programming, Vienna, Austria, 2024,
vol. 313.'
ista: 'Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. 2024. The fault in our
stars: Designing reproducible large-scale code analysis experiments. 38th European
Conference on Object-Oriented Programming. ECOOP: European Conference on Object-Oriented
Programming, LIPIcs, vol. 313, 27.'
mla: 'Maj, Petr, et al. “The Fault in Our Stars: Designing Reproducible Large-Scale
Code Analysis Experiments.” 38th European Conference on Object-Oriented Programming,
vol. 313, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ECOOP.2024.27.'
short: P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, J. Vitek, in:, 38th European
Conference on Object-Oriented Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024.
conference:
end_date: 2024-09-20
location: Vienna, Austria
name: 'ECOOP: European Conference on Object-Oriented Programming'
start_date: 2024-09-16
date_created: 2024-10-06T22:01:12Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:48:19Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.ECOOP.2024.27
external_id:
isi:
- '001533999700027'
file:
- access_level: open_access
checksum: 2e75d305a8c817d76a0c7f136ce34f86
content_type: application/pdf
creator: dernst
date_created: 2024-10-07T11:10:55Z
date_updated: 2024-10-07T11:10:55Z
file_id: '18184'
file_name: 2024_LIPICs_Maj.pdf
file_size: 1764222
relation: main_file
success: 1
file_date_updated: 2024-10-07T11:10:55Z
has_accepted_license: '1'
intvolume: ' 313'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: 38th European Conference on Object-Oriented Programming
publication_identifier:
isbn:
- '9783959773416'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The fault in our stars: Designing reproducible large-scale code analysis experiments'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 313
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18308'
abstract:
- lang: eng
text: We study in this paper the problem of maintaining a solution to k-median and
k-means clustering in a fully dynamic setting. To do so, we present an algorithm
to efficiently maintain a coreset, a compressed version of the dataset, that allows
easy computation of a clustering solution at query time. Our coreset algorithm
has near-optimal update time of Õ(k) in general metric spaces, which reduces to
Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and
O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means
clustering in Euclidean space, this directly leads to an algorithm with update
time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation,
the query time is reduced to Õ(kd).
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund
(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775
with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic:
Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon
2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement
No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from
the French National Research Agency (ANR)."
alternative_title:
- LIPIcs
article_number: '100'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Max Dupré
full_name: La Tour, Max Dupré
last_name: La Tour
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
citation:
ama: 'La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal
update time. In: 32nd Annual European Symposium on Algorithms. Vol 308.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.100'
apa: 'La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Fully dynamic k-means
coreset in near-optimal update time. In 32nd Annual European Symposium on Algorithms
(Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2024.100'
chicago: La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic
K-Means Coreset in near-Optimal Update Time.” In 32nd Annual European Symposium
on Algorithms, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024. https://doi.org/10.4230/LIPIcs.ESA.2024.100.
ieee: M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset
in near-optimal update time,” in 32nd Annual European Symposium on Algorithms,
London, United Kingdom, 2024, vol. 308.
ista: 'La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in
near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European
Symposium on Algorithms, LIPIcs, vol. 308, 100.'
mla: La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update
Time.” 32nd Annual European Symposium on Algorithms, vol. 308, 100, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.100.
short: M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-04
location: London, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2024-09-02
corr_author: '1'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-23T00:00:00Z
date_updated: 2025-12-02T13:49:11Z
day: '23'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.100
ec_funded: 1
external_id:
arxiv:
- '2406.19926'
isi:
- '001545622400100'
file:
- access_level: open_access
checksum: 8e8c0b13049f11bb0133dfac22e32718
content_type: application/pdf
creator: dernst
date_created: 2024-10-21T09:41:48Z
date_updated: 2024-10-21T09:41:48Z
file_id: '18454'
file_name: 2024_LIPICs_DuprelaTour.pdf
file_size: 873561
relation: main_file
success: 1
file_date_updated: 2024-10-21T09:41:48Z
has_accepted_license: '1'
intvolume: ' 308'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773386'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic k-means coreset in near-optimal update time
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 308
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18309'
abstract:
- lang: eng
text: 'The problem of designing connectivity oracles supporting vertex failures
is one of the basic data structures problems for undirected graphs. It is already
well understood: previous works [Duan-Pettie STOC''10; Long-Saranurak FOCS''22]
achieve query time linear in the number of failed vertices, and it is conditionally
optimal as long as we require preprocessing time polynomial in the size of the
graph and update time polynomial in the number of failed vertices. We revisit
this problem in the paradigm of algorithms with predictions: we ask if the query
time can be improved if the set of failed vertices can be predicted beforehand
up to a small number of errors. More specifically, we design a data structure
that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of
size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update
given as the symmetric difference between the predicted and the actual set of
failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time
Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed
from another perspective, our data structure provides an improvement over the
state of the art for the fully dynamic subgraph connectivity problem in the sensitivity
setting [Henzinger-Neumann ESA''16]. We argue that the preprocessing time and
query time of our data structure are conditionally optimal under standard fine-grained
complexity assumptions.'
acknowledgement: "Part of this work was done when Evangelos Kosinas was at University
of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n"
alternative_title:
- LIPIcs
article_number: '72'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Bingbing
full_name: Hu, Bingbing
last_name: Hu
- first_name: Evangelos
full_name: Kosinas, Evangelos
id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949
last_name: Kosinas
- first_name: Adam
full_name: Polak, Adam
last_name: Polak
citation:
ama: 'Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures.
In: 32nd Annual European Symposium on Algorithms. Vol 308. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.72'
apa: 'Hu, B., Kosinas, E., & Polak, A. (2024). Connectivity oracles for predictable
vertex failures. In 32nd Annual European Symposium on Algorithms (Vol.
308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2024.72'
chicago: Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles
for Predictable Vertex Failures.” In 32nd Annual European Symposium on Algorithms,
Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.72.
ieee: B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex
failures,” in 32nd Annual European Symposium on Algorithms, London, United
Kingdom, 2024, vol. 308.
ista: 'Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex
failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium
on Algorithms, LIPIcs, vol. 308, 72.'
mla: Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.”
32nd Annual European Symposium on Algorithms, vol. 308, 72, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.72.
short: B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-04
location: London, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2024-09-02
corr_author: '1'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-12-02T13:49:52Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.72
external_id:
arxiv:
- '2312.08489'
isi:
- '001545622400072'
file:
- access_level: open_access
checksum: ab1f2f9161549a8763eda15db40e022c
content_type: application/pdf
creator: dernst
date_created: 2024-10-21T10:03:48Z
date_updated: 2024-10-21T10:03:48Z
file_id: '18455'
file_name: 2024_LIPICs_Hu.pdf
file_size: 853914
relation: main_file
success: 1
file_date_updated: 2024-10-21T10:03:48Z
has_accepted_license: '1'
intvolume: ' 308'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773386'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Connectivity oracles for predictable vertex failures
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 308
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18557'
abstract:
- lang: eng
text: Broadcast and Consensus are most fundamental tasks in distributed computing.
These tasks are particularly challenging in dynamic networks where communication
across the network links may be unreliable, e.g., due to mobility or failures.
Over the last years, researchers have derived several impossibility results and
high time complexity lower bounds for these tasks. Specifically for the setting
where in each round of communication the adversary is allowed to choose one rooted
tree along which the information is disseminated, there is a lower as well as
an upper bound that is linear in the number n of nodes for Broadcast and for n
≥ 3 the adversary can guarantee that Consensus never happens. This setting is
called the oblivious message adversary for rooted trees. Also note that if the
adversary is allowed to choose a graph that does not contain a rooted tree, then
it can guarantee that Broadcast and Consensus will never happen. However, such
deterministic adversarial models may be overly pessimistic, as many processes
in real-world settings are stochastic in nature rather than worst-case. This paper
studies Broadcast on stochastic dynamic networks and shows that the situation
is very different to the deterministic case. In particular, we show that if information
dissemination occurs along random rooted trees and directed Erdős–Rényi graphs,
Broadcast completes in O(log n) rounds of communication with high probability.
The fundamental insight in our analysis is that key variables are mutually independent.
We then study two adversarial models, (a) one with Byzantine nodes and (b) one
where an adversary controls the edges. (a) Our techniques without Byzantine nodes
are general enough so that they can be extended to Byzantine nodes. (b) In the
spirit of smoothed analysis, we introduce the notion of randomized oblivious message
adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in
the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi
graph) is chosen uniformly at random among the set of all such graphs that include
these edges. We show that Broadcast completes in a finite number of rounds, which
is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All
Broadcast, and Consensus, and give lower bounds that show that most of our upper
bounds are tight.
acknowledgement: "Antoine El-Hayek: This project has received funding from the Austrian
Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the
netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received
funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon
2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian
Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant
DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung,
2020–2024.\r\nStefan Schmid: This project has received funding from the German Research
Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027."
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic
networks with Byzantine nodes and adversarial edges. In: 38th International
Symposium on Distributed Computing. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.DISC.2024.21'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2024). Broadcast and Consensus
in stochastic dynamic networks with Byzantine nodes and adversarial edges. In
38th International Symposium on Distributed Computing (Vol. 319). Madrid,
Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2024.21'
chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and
Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial
Edges.” In 38th International Symposium on Distributed Computing, Vol.
319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.DISC.2024.21.
ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges,” in 38th International
Symposium on Distributed Computing, Madrid, Spain, 2024, vol. 319.
ista: 'El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges. 38th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing,
LIPIcs, vol. 319, 21.'
mla: El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks
with Byzantine Nodes and Adversarial Edges.” 38th International Symposium on
Distributed Computing, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.DISC.2024.21.
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on
Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-11-01
location: Madrid, Spain
name: 'DISC: Symposium on Distributed Computing'
start_date: 2024-10-28
corr_author: '1'
date_created: 2024-11-17T23:01:47Z
date_published: 2024-10-24T00:00:00Z
date_updated: 2026-07-24T12:48:28Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.DISC.2024.21
ec_funded: 1
external_id:
arxiv:
- '2302.11988'
isi:
- '001542467600021'
file:
- access_level: open_access
checksum: d6c8277331cafa188c33ba1717206cf4
content_type: application/pdf
creator: dernst
date_created: 2024-11-18T08:02:45Z
date_updated: 2024-11-18T08:02:45Z
file_id: '18561'
file_name: 2024_LIPIcs_ElHayek.pdf
file_size: 809666
relation: main_file
success: 1
file_date_updated: 2024-11-18T08:02:45Z
has_accepted_license: '1'
intvolume: ' 319'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 38th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959773522'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes
and adversarial edges
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 319
year: '2024'
...
---
_id: '12760'
abstract:
- lang: eng
text: "Dynamic programming (DP) is one of the fundamental paradigms in algorithm
design. However,\r\nmany DP algorithms have to fill in large DP tables, represented
by two-dimensional arrays, which causes at least quadratic running times and space
usages. This has led to the development of improved algorithms for special cases
when the DPs satisfy additional properties like, e.g., the Monge property or total
monotonicity.\r\nIn this paper, we consider a new condition which assumes (among
some other technical assumptions) that the rows of the DP table are monotone.
Under this assumption, we introduce\r\na novel data structure for computing (1
+ ϵ)-approximate DP solutions in near-linear time and\r\nspace in the static setting,
and with polylogarithmic update times when the DP entries change\r\ndynamically.
To the best of our knowledge, our new condition is incomparable to previous conditions
and is the first which allows to derive dynamic algorithms based on existing DPs.
Instead of using two-dimensional arrays to store the DP tables, we store the rows
of the DP tables using monotone piecewise constant functions. This allows us to
store length-n DP table rows with entries in [0, W] using only polylog(n, W) bits,
and to perform operations, such as (min, +)-convolution or rounding, on these
functions in polylogarithmic time.\r\nWe further present several applications
of our data structure. For bicriteria versions of k-balanced graph partitioning
and simultaneous source location, we obtain the first dynamic algorithms with
subpolynomial update times, as well as the first static algorithms using only
near-linear time and space. Additionally, we obtain the currently fastest algorithm
for fully dynamic knapsack."
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project
“Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nStefan Neumann: This research
is supported by the the ERC Advanced Grant REBOUND (834862) and the EC H2020 RIA
project SoBigData++ (871042).\r\nStefan Schmid: Research supported by Austrian Science
Fund (FWF) project I 5025-N (DELTA), 2020-2024."
alternative_title:
- LIPIcs
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: Stefan
full_name: Neumann, Stefan
last_name: Neumann
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Henzinger M, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone
dynamic programs and applications. In: 40th International Symposium on Theoretical
Aspects of Computer Science. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.STACS.2023.36'
apa: 'Henzinger, M., Neumann, S., Räcke, H., & Schmid, S. (2023). Dynamic maintenance
of monotone dynamic programs and applications. In 40th International Symposium
on Theoretical Aspects of Computer Science (Vol. 254). Hamburg, Germany: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2023.36'
chicago: Henzinger, Monika, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic
Maintenance of Monotone Dynamic Programs and Applications.” In 40th International
Symposium on Theoretical Aspects of Computer Science, Vol. 254. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.36.
ieee: M. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance of
monotone dynamic programs and applications,” in 40th International Symposium
on Theoretical Aspects of Computer Science, Hamburg, Germany, 2023, vol. 254.
ista: 'Henzinger M, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of monotone
dynamic programs and applications. 40th International Symposium on Theoretical
Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer
Science, LIPIcs, vol. 254, 36.'
mla: Henzinger, Monika, et al. “Dynamic Maintenance of Monotone Dynamic Programs
and Applications.” 40th International Symposium on Theoretical Aspects of Computer
Science, vol. 254, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.STACS.2023.36.
short: M. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 40th International Symposium
on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-03-09
location: Hamburg, Germany
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2023-03-07
corr_author: '1'
date_created: 2023-03-26T22:01:07Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2025-09-09T12:22:44Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.STACS.2023.36
ec_funded: 1
external_id:
arxiv:
- '2301.01744'
isi:
- '001532693100036'
file:
- access_level: open_access
checksum: 22141ab8bc55188e2dfff665e5daecbd
content_type: application/pdf
creator: dernst
date_created: 2023-03-27T06:37:22Z
date_updated: 2023-03-27T06:37:22Z
file_id: '12769'
file_name: 2023_LIPICS_HenzingerM.pdf
file_size: 872706
relation: main_file
success: 1
file_date_updated: 2023-03-27T06:37:22Z
has_accepted_license: '1'
intvolume: ' 254'
isi: 1
language:
- iso: eng
month: '03'
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: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: 40th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
isbn:
- '9783959772662'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic maintenance of monotone dynamic programs and 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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 254
year: '2023'
...
---
_id: '14083'
abstract:
- lang: eng
text: "In this work we consider the list-decodability and list-recoverability of
arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable
if every radius pn Hamming ball contains less than L codewords; (p,\U0001D4C1,L)_q-list-recoverability
is a generalization where we place radius pn Hamming balls on every point of a
combinatorial rectangle with side length \U0001D4C1 and again stipulate that there
be less than L codewords.\r\nOur main contribution is to precisely calculate the
maximum value of p for which there exist infinite families of positive rate (p,\U0001D4C1,L)_q-list-recoverable
codes, the quantity we call the zero-rate threshold. Denoting this value by p_*,
we in fact show that codes correcting a p_*+ε fraction of errors must have size
O_ε(1), i.e., independent of n. Such a result is typically referred to as a \"Plotkin
bound.\" To complement this, a standard random code with expurgation construction
shows that there exist positive rate codes correcting a p_*-ε fraction of errors.
We also follow a classical proof template (typically attributed to Elias and Bassalygo)
to derive from the zero-rate threshold other tradeoffs between rate and decoding
radius for list-decoding and list-recovery.\r\nTechnically, proving the Plotkin
bound boils down to demonstrating the Schur convexity of a certain function defined
on the q-simplex as well as the convexity of a univariate function derived from
it. We remark that an earlier argument claimed similar results for q-ary list-decoding;
however, we point out that this earlier proof is flawed."
acknowledgement: "Nicolas Resch: Research supported in part by ERC H2020 grant No.74079
(ALGSTRONGCRYPTO). Chen Yuan: Research supported in part by the National Key Research
and Development Projects under Grant 2022YFA1004900 and Grant 2021YFE0109900, the
National Natural Science Foundation of China under Grant 12101403 and Grant 12031011.\r\nAcknowledgements
YZ is grateful to Shashank Vatedka, Diyuan Wu and Fengxing Zhu for inspiring discussions."
alternative_title:
- LIPIcs
article_number: '99'
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. Zero-rate thresholds and new capacity bounds for
list-decoding and list-recovery. In: 50th International Colloquium on Automata,
Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.99'
apa: 'Resch, N., Yuan, C., & Zhang, Y. (2023). Zero-rate thresholds and new
capacity bounds for list-decoding and list-recovery. In 50th International
Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.99'
chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New
Capacity Bounds for List-Decoding and List-Recovery.” In 50th International
Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.99.
ieee: N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds
for list-decoding and list-recovery,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds
for list-decoding and list-recovery. 50th International Colloquium on Automata,
Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs,
vol. 261, 99.'
mla: Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding
and List-Recovery.” 50th International Colloquium on Automata, Languages, and
Programming, vol. 261, 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.ICALP.2023.99.
short: N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: Automata, Languages and Programming'
start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:13Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-09-08T08:31:53Z
day: '01'
ddc:
- '000'
department:
- _id: MaMo
doi: 10.4230/LIPIcs.ICALP.2023.99
external_id:
arxiv:
- '2210.07754'
file:
- access_level: open_access
checksum: a449143fec3fbebb092cb8ef3b53c226
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T07:23:18Z
date_updated: 2023-08-21T07:23:18Z
file_id: '14091'
file_name: 2023_LIPIcsICALP_Resch.pdf
file_size: 1141497
relation: main_file
success: 1
file_date_updated: 2023-08-21T07:23:18Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '17330'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery
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: 261
year: '2023'
...
---
_id: '14084'
abstract:
- lang: eng
text: "A central problem in computational statistics is to convert a procedure for
sampling combinatorial objects into a procedure for counting those objects, and
vice versa. We will consider sampling problems which come from Gibbs distributions,
which are families of probability distributions over a discrete space Ω with probability
mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max]
and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor
Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log
Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts
c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²)
samples for integer-valued distributions (ignoring some second-order terms and
parameters), We show this is optimal up to logarithmic factors. We illustrate
with improved algorithms for counting connected subgraphs and perfect matchings
in a graph."
acknowledgement: We thank Heng Guo for helpful explanations of algorithms for sampling
connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the
Wang-Landau algorithm and its use in physics.
alternative_title:
- LIPIcs
article_number: '72'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: David G.
full_name: Harris, David G.
last_name: Harris
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. In:
50th International Colloquium on Automata, Languages, and Programming.
Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.72'
apa: 'Harris, D. G., & Kolmogorov, V. (2023). Parameter estimation for Gibbs
distributions. In 50th International Colloquium on Automata, Languages, and
Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.72'
chicago: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs
Distributions.” In 50th International Colloquium on Automata, Languages, and
Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.72.
ieee: D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,”
in 50th International Colloquium on Automata, Languages, and Programming,
Paderborn, Germany, 2023, vol. 261.
ista: 'Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions.
50th International Colloquium on Automata, Languages, and Programming. ICALP:
Automata, Languages and Programming, LIPIcs, vol. 261, 72.'
mla: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs
Distributions.” 50th International Colloquium on Automata, Languages, and Programming,
vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.72.
short: D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: Automata, Languages and Programming'
start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-07-10T11:50:45Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: VlKo
doi: 10.4230/LIPIcs.ICALP.2023.72
external_id:
arxiv:
- '2007.10824'
file:
- access_level: open_access
checksum: 6dee0684245bb1c524b9c955db1e933d
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T06:45:16Z
date_updated: 2023-08-21T06:45:16Z
file_id: '14088'
file_name: 2023_LIPIcsICALP_Harris.pdf
file_size: 917791
relation: main_file
success: 1
file_date_updated: 2023-08-21T06:45:16Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '18855'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Parameter estimation for Gibbs distributions
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: 261
year: '2023'
...
---
_id: '14085'
abstract:
- lang: eng
text: We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow
under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed,
unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm
in general sparse graphs with arbitrarily good approximation guarantee.
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(Grant agreement No.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic
Hierarchical Graph Decompositions”,\r\nI 5982-N, and project “Fast Algorithms for
a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the
netidee SCIENCE Stiftung, 2020–2024.\r\nThis work was done in part while Gramoz
Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There,
he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich
Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster
and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their
insightful comments."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: 'Goranci G, Henzinger M. Efficient data structures for incremental exact and
approximate maximum flow. In: 50th International Colloquium on Automata, Languages,
and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2023. doi:10.4230/LIPIcs.ICALP.2023.69'
apa: 'Goranci, G., & Henzinger, M. (2023). Efficient data structures for incremental
exact and approximate maximum flow. In 50th International Colloquium on Automata,
Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.69'
chicago: Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental
Exact and Approximate Maximum Flow.” In 50th International Colloquium on Automata,
Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
ieee: G. Goranci and M. Henzinger, “Efficient data structures for incremental exact
and approximate maximum flow,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Goranci G, Henzinger M. 2023. Efficient data structures for incremental exact
and approximate maximum flow. 50th International Colloquium on Automata, Languages,
and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261,
69.'
mla: Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental
Exact and Approximate Maximum Flow.” 50th International Colloquium on Automata,
Languages, and Programming, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.69.
short: G. Goranci, M. Henzinger, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: Automata, Languages and Programming'
start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-06-04T07:19:37Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.69
ec_funded: 1
external_id:
arxiv:
- '2211.09606'
file:
- access_level: open_access
checksum: 074177e815a1656de5d4071c7a3dffa6
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T06:59:05Z
date_updated: 2023-08-21T06:59:05Z
file_id: '14089'
file_name: 2023_LIPIcsICALP_Goranci.pdf
file_size: 875910
relation: main_file
success: 1
file_date_updated: 2023-08-21T06:59:05Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
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: 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: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient data structures for incremental exact and approximate maximum flow
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: 261
year: '2023'
...
---
_id: '14086'
abstract:
- lang: eng
text: "The maximization of submodular functions have found widespread application
in areas such as machine learning, combinatorial optimization, and economics,
where practitioners often wish to enforce various constraints; the matroid constraint
has been investigated extensively due to its algorithmic properties and expressive
power. Though tight approximation algorithms for general matroid constraints exist
in theory, the running times of such algorithms typically scale quadratically,
and are not practical for truly large scale settings. Recent progress has focused
on fast algorithms for important classes of matroids given in explicit form. Currently,
nearly-linear time algorithms only exist for graphic and partition matroids [Alina
Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone
submodular maximization constrained by graphic, transversal matroids, or laminar
matroids in time near-linear in the size of their representation. Our algorithms
achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate
the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the
running time of our algorithm cannot be improved within the fast continuous greedy
framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák,
2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures
that maintain bases with approximate maximum cardinality and weight under certain
element updates. These data structures need to support a weight decrease operation
and a novel Freeze operation that allows the algorithm to freeze elements (i.e.
force to be contained) in its basis regardless of future data structure operations.
For the laminar matroid, we present a new dynamic data structure using the top
tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et
al., 2005] that maintains the maximum weight basis under insertions and deletions
of elements in O(log n) time. This data structure needs to support certain subtree
query and path update operations that are performed every insertion and deletion
that are non-trivial to handle in conjunction. For the transversal matroid the
Freeze operation corresponds to requiring the data structure to keep a certain
set S of vertices matched, a property that we call S-stability. While there is
a large body of work on dynamic matching algorithms, none are S-stable and maintain
an approximate maximum weight matching under vertex updates. We give the first
such algorithm for bipartite graphs with total running time linear (up to log
factors) in the number of edges."
acknowledgement: " Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project
“Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast
Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by
NSF Award 2127781."
alternative_title:
- LIPIcs
article_number: '74'
article_processing_charge: Yes
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: Paul
full_name: Liu, Paul
last_name: Liu
- first_name: Jan
full_name: Vondrák, Jan
last_name: Vondrák
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
citation:
ama: 'Henzinger M, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for
several classes of matroids. In: 50th International Colloquium on Automata,
Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74'
apa: 'Henzinger, M., Liu, P., Vondrák, J., & Zheng, D. W. (2023). Faster submodular
maximization for several classes of matroids. In 50th International Colloquium
on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.74'
chicago: Henzinger, Monika, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular
Maximization for Several Classes of Matroids.” In 50th International Colloquium
on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74.
ieee: M. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization
for several classes of matroids,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Henzinger M, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization
for several classes of matroids. 50th International Colloquium on Automata, Languages,
and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261,
74.'
mla: Henzinger, Monika, et al. “Faster Submodular Maximization for Several Classes
of Matroids.” 50th International Colloquium on Automata, Languages, and Programming,
vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.74.
short: M. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium
on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: Automata, Languages and Programming'
start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-07-10T11:50:45Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.74
ec_funded: 1
external_id:
arxiv:
- '2305.00122'
file:
- access_level: open_access
checksum: a5eef225014e003efbfbe4830fdd23cb
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T07:04:36Z
date_updated: 2023-08-21T07:04:36Z
file_id: '14090'
file_name: 2023_LIPIcsICALP_HenzingerM.pdf
file_size: 930943
relation: main_file
success: 1
file_date_updated: 2023-08-21T07:04:36Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
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: 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: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster submodular maximization for several classes of matroids
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: 261
year: '2023'
...
---
_id: '14405'
abstract:
- lang: eng
text: We introduce hypernode automata as a new specification formalism for hyperproperties
of concurrent systems. They are finite automata with nodes labeled with hypernode
logic formulas and transitions labeled with actions. A hypernode logic formula
specifies relations between sequences of variable values in different system executions.
Unlike HyperLTL, hypernode logic takes an asynchronous view on execution traces
by constraining the values and the order of value changes of each variable without
correlating the timing of the changes. Different execution traces are synchronized
solely through the transitions of hypernode automata. Hypernode automata naturally
combine asynchronicity at the node level with synchronicity at the transition
level. We show that the model-checking problem for hypernode automata is decidable
over action-labeled Kripke structures, whose actions induce transitions of the
specification automata. For this reason, hypernode automaton is a suitable formalism
for specifying and verifying asynchronous hyperproperties, such as declassifying
observational determinism in multi-threaded programs.
acknowledgement: "This work was supported in part by the Austrian Science Fund (FWF)
SFB project\r\nSpyCoDe F8502, by the FWF projects ZK-35 and W1255-N23, and by the
ERC Advanced Grant\r\nVAMOS 101020093."
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ezio
full_name: Bartocci, Ezio
last_name: Bartocci
- 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: Dejan
full_name: Nickovic, Dejan
id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87
last_name: Nickovic
- first_name: Ana
full_name: Oliveira da Costa, Ana
id: f347ec37-6676-11ee-b395-a888cb7b4fb4
last_name: Oliveira da Costa
orcid: 0000-0002-8741-5799
citation:
ama: 'Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. Hypernode automata.
In: 34th International Conference on Concurrency Theory. Vol 279. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.CONCUR.2023.21'
apa: 'Bartocci, E., Henzinger, T. A., Nickovic, D., & Oliveira da Costa, A.
(2023). Hypernode automata. In 34th International Conference on Concurrency
Theory (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2023.21'
chicago: Bartocci, Ezio, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira da
Costa. “Hypernode Automata.” In 34th International Conference on Concurrency
Theory, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
https://doi.org/10.4230/LIPIcs.CONCUR.2023.21.
ieee: E. Bartocci, T. A. Henzinger, D. Nickovic, and A. Oliveira da Costa, “Hypernode
automata,” in 34th International Conference on Concurrency Theory, Antwerp,
Belgium, 2023, vol. 279.
ista: 'Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. 2023. Hypernode
automata. 34th International Conference on Concurrency Theory. CONCUR: Conference
on Concurrency Theory, LIPIcs, vol. 279, 21.'
mla: Bartocci, Ezio, et al. “Hypernode Automata.” 34th International Conference
on Concurrency Theory, vol. 279, 21, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2023, doi:10.4230/LIPIcs.CONCUR.2023.21.
short: E. Bartocci, T.A. Henzinger, D. Nickovic, A. Oliveira da Costa, in:, 34th
International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-09-22
location: Antwerp, Belgium
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2023-09-19
corr_author: '1'
date_created: 2023-10-08T22:01:16Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2026-01-05T12:27:40Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2023.21
ec_funded: 1
external_id:
arxiv:
- '2305.02836'
file:
- access_level: open_access
checksum: 215765e40454d806174ac0a223e8d6fa
content_type: application/pdf
creator: dernst
date_created: 2023-10-09T07:42:45Z
date_updated: 2023-10-09T07:42:45Z
file_id: '14413'
file_name: 2023_LIPcs_Bartocci.pdf
file_size: 795790
relation: main_file
success: 1
file_date_updated: 2023-10-09T07:42:45Z
has_accepted_license: '1'
intvolume: ' 279'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 34th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959772990'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '20866'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Hypernode 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: 279
year: '2023'
...
---
_id: '14485'
abstract:
- lang: eng
text: "Batching is a technique that stores multiple keys/values in each node of
a data structure. In sequential search data structures, batching reduces latency
by reducing the number of cache misses and shortening the chain of pointers to
dereference. Applying batching to concurrent data structures is challenging, because
it is difficult to maintain the search property and keep contention low in the
presence of batching.\r\nIn this paper, we present a general methodology for leveraging
batching in concurrent search data structures, called BatchBoost. BatchBoost builds
a search data structure from distinct \"data\" and \"index\" layers. The data
layer’s purpose is to store a batch of key/value pairs in each of its nodes. The
index layer uses an unmodified concurrent search data structure to route operations
to a position in the data layer that is \"close\" to where the corresponding key
should exist. The requirements on the index and data layers are low: with minimal
effort, we were able to compose three highly scalable concurrent search data structures
based on three original data structures as the index layers with a batched version
of the Lazy List as the data layer. The resulting BatchBoost data structures provide
significant performance improvements over their original counterparts."
alternative_title:
- LIPIcs
article_number: '35'
article_processing_charge: Yes
author:
- first_name: Vitaly
full_name: Aksenov, Vitaly
last_name: Aksenov
- first_name: Michael
full_name: Anoprenko, Michael
last_name: Anoprenko
- first_name: Alexander
full_name: Fedorov, Alexander
id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
last_name: Fedorov
- first_name: Michael
full_name: Spear, Michael
last_name: Spear
citation:
ama: 'Aksenov V, Anoprenko M, Fedorov A, Spear M. Brief announcement: BatchBoost:
Universal batching for concurrent data structures. In: 37th International Symposium
on Distributed Computing. Vol 281. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.DISC.2023.35'
apa: 'Aksenov, V., Anoprenko, M., Fedorov, A., & Spear, M. (2023). Brief announcement:
BatchBoost: Universal batching for concurrent data structures. In 37th International
Symposium on Distributed Computing (Vol. 281). L’Aquila, Italy: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2023.35'
chicago: 'Aksenov, Vitaly, Michael Anoprenko, Alexander Fedorov, and Michael Spear.
“Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures.”
In 37th International Symposium on Distributed Computing, Vol. 281. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.DISC.2023.35.'
ieee: 'V. Aksenov, M. Anoprenko, A. Fedorov, and M. Spear, “Brief announcement:
BatchBoost: Universal batching for concurrent data structures,” in 37th International
Symposium on Distributed Computing, L’Aquila, Italy, 2023, vol. 281.'
ista: 'Aksenov V, Anoprenko M, Fedorov A, Spear M. 2023. Brief announcement: BatchBoost:
Universal batching for concurrent data structures. 37th International Symposium
on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol.
281, 35.'
mla: 'Aksenov, Vitaly, et al. “Brief Announcement: BatchBoost: Universal Batching
for Concurrent Data Structures.” 37th International Symposium on Distributed
Computing, vol. 281, 35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.DISC.2023.35.'
short: V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium
on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
conference:
end_date: 2023-10-13
location: L'Aquila, Italy
name: 'DISC: Symposium on Distributed Computing'
start_date: 2023-10-09
corr_author: '1'
date_created: 2023-11-05T23:00:53Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-10-09T21:07:14Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
doi: 10.4230/LIPIcs.DISC.2023.35
file:
- access_level: open_access
checksum: d9f8d2915cccdf2df5905b7cd1b4a560
content_type: application/pdf
creator: dernst
date_created: 2023-11-06T11:45:21Z
date_updated: 2023-11-06T11:45:21Z
file_id: '14492'
file_name: 2023_LIPIcs_Aksenov.pdf
file_size: 646665
relation: main_file
success: 1
file_date_updated: 2023-11-06T11:45:21Z
has_accepted_license: '1'
intvolume: ' 281'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: 37th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959773010'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: BatchBoost: Universal batching for concurrent 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: 281
year: '2023'
...
---
_id: '14516'
abstract:
- lang: eng
text: 'We revisit decentralized random beacons with a focus on practical distributed
applications. Decentralized random beacons (Beaver and So, Eurocrypt''93) provide
the functionality for n parties to generate an unpredictable sequence of bits
in a way that cannot be biased, which is useful for any decentralized protocol
requiring trusted randomness. Existing beacon constructions are highly inefficient
in practical settings where protocol parties need to rejoin after crashes or disconnections,
and more significantly where smart contracts may rely on arbitrary index points
in high-volume streams. For this, we introduce a new notion of history-generating
decentralized random beacons (HGDRBs). Roughly, the history-generation property
of HGDRBs allows for previous beacon outputs to be efficiently generated knowing
only the current value and the public key. At application layers, history-generation
supports registering a sparser set of on-chain values if desired, so that apps
like lotteries can utilize on-chain values without incurring high-frequency costs,
enjoying all the benefits of DRBs implemented off-chain or with decoupled, special-purpose
chains. Unlike rollups, HG is tailored specifically to recovering and verifying
pseudorandom bit sequences and thus enjoys unique optimizations investigated in
this work. We introduce STROBE: an efficient HGDRB construction which generalizes
the original squaring-based RSA approach of Beaver and So. STROBE enjoys several
useful properties that make it suited for practical applications that use beacons:
1) history-generating: it can regenerate and verify high-throughput beacon streams,
supporting sparse (thus cost-effective) ledger entries; 2) concisely self-verifying:
NIZK-free, with state and validation employing a single ring element; 3) eco-friendly:
stake-based rather than work based; 4) unbounded: refresh-free, addressing limitations
of Beaver and So; 5) delay-free: results are immediately available. 6) storage-efficient:
the last beacon suffices to derive all past outputs, thus O(1) storage requirements
for nodes serving the whole history.'
acknowledgement: Work done when all the authors were at Novi Research, Meta.
alternative_title:
- LIPIcs
article_number: '7'
article_processing_charge: Yes
author:
- first_name: Donald
full_name: Beaver, Donald
last_name: Beaver
- first_name: Mahimna
full_name: Kelkar, Mahimna
last_name: Kelkar
- first_name: Kevin
full_name: Lewi, Kevin
last_name: Lewi
- first_name: Valeria
full_name: Nikolaenko, Valeria
last_name: Nikolaenko
- first_name: Alberto
full_name: Sonnino, Alberto
last_name: Sonnino
- first_name: Konstantinos
full_name: Chalkias, Konstantinos
last_name: Chalkias
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
- first_name: Ladi De
full_name: Naurois, Ladi De
last_name: Naurois
- first_name: Arnab
full_name: Roy, Arnab
last_name: Roy
citation:
ama: 'Beaver D, Kelkar M, Lewi K, et al. STROBE: Streaming Threshold Random Beacons.
In: 5th Conference on Advances in Financial Technologies. Vol 282. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.AFT.2023.7'
apa: 'Beaver, D., Kelkar, M., Lewi, K., Nikolaenko, V., Sonnino, A., Chalkias, K.,
… Roy, A. (2023). STROBE: Streaming Threshold Random Beacons. In 5th Conference
on Advances in Financial Technologies (Vol. 282). Princeton, NJ, United States:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2023.7'
chicago: 'Beaver, Donald, Mahimna Kelkar, Kevin Lewi, Valeria Nikolaenko, Alberto
Sonnino, Konstantinos Chalkias, Eleftherios Kokoris Kogias, Ladi De Naurois, and
Arnab Roy. “STROBE: Streaming Threshold Random Beacons.” In 5th Conference
on Advances in Financial Technologies, Vol. 282. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.AFT.2023.7.'
ieee: 'D. Beaver et al., “STROBE: Streaming Threshold Random Beacons,” in
5th Conference on Advances in Financial Technologies, Princeton, NJ, United
States, 2023, vol. 282.'
ista: 'Beaver D, Kelkar M, Lewi K, Nikolaenko V, Sonnino A, Chalkias K, Kokoris
Kogias E, Naurois LD, Roy A. 2023. STROBE: Streaming Threshold Random Beacons.
5th Conference on Advances in Financial Technologies. AFT: Conference on Advances
in Financial Technologies, LIPIcs, vol. 282, 7.'
mla: 'Beaver, Donald, et al. “STROBE: Streaming Threshold Random Beacons.” 5th
Conference on Advances in Financial Technologies, vol. 282, 7, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.AFT.2023.7.'
short: D. Beaver, M. Kelkar, K. Lewi, V. Nikolaenko, A. Sonnino, K. Chalkias, E.
Kokoris Kogias, L.D. Naurois, A. Roy, in:, 5th Conference on Advances in Financial
Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
conference:
end_date: 2023-10-25
location: Princeton, NJ, United States
name: 'AFT: Conference on Advances in Financial Technologies'
start_date: 2023-10-23
corr_author: '1'
date_created: 2023-11-12T23:00:55Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-10-09T21:07:17Z
day: '01'
ddc:
- '000'
department:
- _id: ElKo
doi: 10.4230/LIPIcs.AFT.2023.7
file:
- access_level: open_access
checksum: c1f98831cb5149d6c030c41999e6e960
content_type: application/pdf
creator: dernst
date_created: 2023-11-13T08:44:34Z
date_updated: 2023-11-13T08:44:34Z
file_id: '14521'
file_name: 2023_LIPIcs_Beaver.pdf
file_size: 793495
relation: main_file
success: 1
file_date_updated: 2023-11-13T08:44:34Z
has_accepted_license: '1'
intvolume: ' 282'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1643
month: '10'
oa: 1
oa_version: Published Version
publication: 5th Conference on Advances in Financial Technologies
publication_identifier:
isbn:
- '9783959773034'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'STROBE: Streaming Threshold Random Beacons'
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: 282
year: '2023'
...
---
_id: '22373'
abstract:
- lang: eng
text: "Data dissemination is a fundamental task in distributed computing. This paper
studies broadcast problems in various innovative models where the communication
network connecting n processes is dynamic (e.g., due to mobility or failures)
and controlled by an adversary. \r\nIn the first model, the processes transitively
communicate their ids in synchronous rounds along a rooted tree given in each
round by the adversary whose goal is to maximize the number of rounds until at
least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2
lower bound and an O(nlog log n) upper bound. We show the first linear upper bound
for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.\r\nWe extend these results to the
setting where the adversary gives in each round k-disjoint forests and their goal
is to maximize the number of rounds until there is a set of k ids such that each
process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and
a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.\r\nFinally, we study the setting
where the adversary gives in each round a directed graph with k roots and their
goal is to maximize the number of rounds until there exist k ids that are known
by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k
upper bound for this problem.\r\nFor the two latter problems no upper or lower
bounds were previously known."
acknowledgement: " This project has received funding from the European Research Council
(ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme
(grant agreement No.\r\n101019564). This work was further supported by the Austrian
Science Fund (FWF) and netIDEE\r\nSCIENCE project P 33775-N, as well as the FWF
project I 4800-N (ADVISE)"
alternative_title:
- LIPIcs
article_number: '47'
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
orcid: 0000-0002-7798-1711
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Asymptotically tight bounds on the time
complexity of broadcast and its variants in dynamic networks. In: Tauman Kalai
Y, ed. 14th Innovations in Theoretical Computer Science Conference. Vol
251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPICS.ITCS.2023.47'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2023). Asymptotically tight
bounds on the time complexity of broadcast and its variants in dynamic networks.
In Y. Tauman Kalai (Ed.), 14th Innovations in Theoretical Computer Science
Conference (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2023.47'
chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Asymptotically
Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.”
In 14th Innovations in Theoretical Computer Science Conference, edited
by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023. https://doi.org/10.4230/LIPICS.ITCS.2023.47.
ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Asymptotically tight bounds on
the time complexity of broadcast and its variants in dynamic networks,” in 14th
Innovations in Theoretical Computer Science Conference, Cambridge, Massachusetts,
USA, 2023, vol. 251.
ista: 'El-Hayek A, Henzinger M, Schmid S. 2023. Asymptotically tight bounds on the
time complexity of broadcast and its variants in dynamic networks. 14th Innovations
in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer
Science, LIPIcs, vol. 251, 47.'
mla: El-Hayek, Antoine, et al. “Asymptotically Tight Bounds on the Time Complexity
of Broadcast and Its Variants in Dynamic Networks.” 14th Innovations in Theoretical
Computer Science Conference, edited by Yael Tauman Kalai, vol. 251, 47, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPICS.ITCS.2023.47.
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, Y. Tauman Kalai (Ed.), 14th Innovations
in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-01-13
location: Cambridge, Massachusetts, USA
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2023-01-10
date_created: 2026-07-20T11:45:04Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '01'
ddc:
- '000'
doi: 10.4230/LIPICS.ITCS.2023.47
editor:
- first_name: Yael
full_name: Tauman Kalai, Yael
last_name: Tauman Kalai
extern: '1'
external_id:
arxiv:
- '2211.10151'
file:
- access_level: open_access
checksum: d7f45fdcbc5fccd61db69f56d775c636
content_type: application/pdf
creator: cchlebak
date_created: 2026-07-22T08:04:03Z
date_updated: 2026-07-22T08:04:03Z
file_id: '22383'
file_name: 2023_LIPIcs_El-Hayek.pdf
file_size: 1077427
relation: main_file
success: 1
file_date_updated: 2026-07-22T08:04:03Z
has_accepted_license: '1'
intvolume: ' 251'
keyword:
- broadcast
- cover
- k-broadcast
- dynamic radius
- dynamic graphs
- oblivious message adversary
- time complexity
- Theory of computation → Distributed algorithms
- Networks → Network algorithms
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: 14th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959772631'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Asymptotically tight bounds on the time complexity of broadcast and its variants
in dynamic networks
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 251
year: '2023'
...
---
_id: '11183'
abstract:
- lang: eng
text: "Subgraph detection has recently been one of the most studied problems in
the CONGEST model of distributed computing. In this work, we study the distributed
complexity of problems closely related to subgraph detection, mainly focusing
on induced subgraph detection. The main line of this work presents lower bounds
and parameterized algorithms w.r.t structural parameters of the input graph:\r\n-
On general graphs, we give unconditional lower bounds for induced detection of
cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions
from centralized parameterized complexity, we prove lower bounds in CONGEST for
detecting patterns with a 4-clique, and for induced path detection conditional
on the hardness of triangle detection in the congested clique.\r\n- On graphs
of bounded degeneracy, we show that induced paths can be detected fast in CONGEST
using techniques from parameterized algorithms, while detecting cycles and patterns
of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show
that induced subgraph detection is easy in CONGEST for any pattern graph. More
specifically, we adapt a centralized parameterized algorithm for a more general
maximum common induced subgraph detection problem to the distributed setting.
In addition to these induced subgraph detection results, we study various related
problems in the CONGEST and congested clique models, including for multicolored
versions of subgraph-detection-like problems."
acknowledgement: "Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070)
of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007)
operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported
by the European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François
Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced
subgraph detection [36]."
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: No
author:
- first_name: Amir
full_name: Nikabadi, Amir
last_name: Nikabadi
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
citation:
ama: 'Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs,
multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A,
eds. 25th International Conference on Principles of Distributed Systems.
Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.OPODIS.2021.15'
apa: 'Nikabadi, A., & Korhonen, J. (2022). Beyond distributed subgraph detection:
Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V.
Gramoli, & A. Milani (Eds.), 25th International Conference on Principles
of Distributed Systems (Vol. 217). Strasbourg, France: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15'
chicago: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” In 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas,
Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15.'
ieee: 'A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters,” in 25th International
Conference on Principles of Distributed Systems, Strasbourg, France, 2022,
vol. 217.'
ista: 'Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters. 25th International Conference
on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.'
mla: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas
et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
doi:10.4230/LIPIcs.OPODIS.2021.15.'
short: A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
corr_author: '1'
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2025-04-14T07:49:13Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.15
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
file:
- access_level: open_access
checksum: 626551c14de5d4091573200ed0535752
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T07:53:00Z
date_updated: 2022-05-02T07:53:00Z
file_id: '11345'
file_name: 2022_LIPICs_Nikabadi.pdf
file_size: 790396
relation: main_file
success: 1
file_date_updated: 2022-05-02T07:53:00Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Beyond distributed subgraph detection: Induced subgraphs, multicolored problems
and graph parameters'
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: 217
year: '2022'
...
---
_id: '11184'
abstract:
- lang: eng
text: "Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node.\r\nIn this work, we consider the more general setting where
G is an arbitrary regular graph, and present a technique for simulating protocols
designed for fully-connected networks in any connected regular graph. Our main
result is a simulation that is efficient on many interesting graph families: roughly,
the simulation overhead is polylogarithmic in the number of nodes, and quadratic
in the conductance of the graph. As a sample application, we show that, in any
regular graph with conductance φ, both leader election and exact majority can
be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability,
using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast
and space-efficient population protocols for leader election and exact majority
on graphs with good expansion properties. We believe our results will prove generally
useful, as they allow efficient technology transfer between the well-mixed (clique)
case, and the under-explored spatial setting."
acknowledgement: "Dan Alistarh: This project has received funding from the European
Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has
received from the European Union’s Horizon 2020 research and\r\ninnovation programme
under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements
We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock
construction to non-regular graphs. We also thank anonymous reviewers for their
useful comments on earlier versions of this manuscript."
alternative_title:
- LIPIcs
article_number: '14'
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols.
In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles
of Distributed Systems. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.OPODIS.2021.14'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2022). Fast graphical
population protocols. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems (Vol. 217).
Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14'
chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical
Population Protocols.” In 25th International Conference on Principles of Distributed
Systems, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol.
217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14.
ieee: D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population
protocols,” in 25th International Conference on Principles of Distributed Systems,
Strasbourg, France, 2022, vol. 217.
ista: Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols.
25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs,
vol. 217, 14.
mla: Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” 25th
International Conference on Principles of Distributed Systems, edited by Quentin
Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, doi:10.4230/LIPIcs.OPODIS.2021.14.
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A.
Milani (Eds.), 25th International Conference on Principles of Distributed Systems,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
corr_author: '1'
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2025-04-14T07:49:13Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.14
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: 2c7c982174c6f98c4ca6e92539d15086
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T08:06:33Z
date_updated: 2022-05-02T08:06:33Z
file_id: '11346'
file_name: 2022_LIPICs_Alistarh.pdf
file_size: 959406
relation: main_file
success: 1
file_date_updated: 2022-05-02T08:06:33Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast graphical population protocols
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: 217
year: '2022'
...