---
OA_place: publisher
OA_type: hybrid
_id: '20053'
abstract:
- lang: eng
text: "Liquid democracy is a transitive vote delegation mechanism over voting graphs.
It enables each voter to delegate their vote(s) to another better-informed voter,
with the goal of collectively making a better decision. The question of whether
liquid democracy outperforms direct voting has been previously studied in the
context of local delegation mechanisms (where voters can only delegate to someone
in their neighbourhood) and binary decision problems. It has previously been shown
that it is impossible for local delegation mechanisms to outperform direct voting
in general graphs. This raises the question: for which classes of graphs do local
delegation mechanisms yield good results?\r\nIn this work, we analyse (1) properties
of specific graphs and (2) properties of local delegation mechanisms on these
graphs, determining where local delegation actually outperforms direct voting.
We show that a critical graph property enabling liquid democracy is that the voting
outcome of local delegation mechanisms preserves a sufficient amount of variance,
thereby avoiding situations where delegation falls behind direct voting1. These
insights allow us to prove our main results, namely that there exist local delegation
mechanisms that perform no worse and in fact quantitatively better than direct
voting in natural graph topologies like complete, random d-regular, and bounded
degree graphs, lending a more nuanced perspective to previous impossibility results."
acknowledgement: This work was partially supported by MOE-T2EP20122-0014 (DataDriven
Distributed Algorithms), German Research Foundation (DFG) project ReNO (SPP 2378)
from 2023-2027, ERC CoG 863818 (ForMSMArt) and Austrian Science Fund (FWF) 10.55776/COE12.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. When is liquid democracy
possible?: On the manipulation of variance. In: Proceedings of the ACM Symposium
on Principles of Distributed Computing. Association for Computing Machinery;
2025:241-251. doi:10.1145/3732772.3733544'
apa: 'Chatterjee, K., Gilbert, S., Schmid, S., Svoboda, J., & Yeo, M. X. (2025).
When is liquid democracy possible?: On the manipulation of variance. In Proceedings
of the ACM Symposium on Principles of Distributed Computing (pp. 241–251).
Huatulco, Mexico: Association for Computing Machinery. https://doi.org/10.1145/3732772.3733544'
chicago: 'Chatterjee, Krishnendu, Seth Gilbert, Stefan Schmid, Jakub Svoboda, and
Michelle X Yeo. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.”
In Proceedings of the ACM Symposium on Principles of Distributed Computing,
241–51. Association for Computing Machinery, 2025. https://doi.org/10.1145/3732772.3733544.'
ieee: 'K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, and M. X. Yeo, “When is
liquid democracy possible?: On the manipulation of variance,” in Proceedings
of the ACM Symposium on Principles of Distributed Computing, Huatulco, Mexico,
2025, pp. 241–251.'
ista: 'Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. 2025. When is liquid
democracy possible?: On the manipulation of variance. Proceedings of the ACM Symposium
on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
Computing, 241–251.'
mla: 'Chatterjee, Krishnendu, et al. “When Is Liquid Democracy Possible?: On the
Manipulation of Variance.” Proceedings of the ACM Symposium on Principles of
Distributed Computing, Association for Computing Machinery, 2025, pp. 241–51,
doi:10.1145/3732772.3733544.'
short: K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, M.X. Yeo, in:, Proceedings
of the ACM Symposium on Principles of Distributed Computing, Association for Computing
Machinery, 2025, pp. 241–251.
conference:
end_date: 2025-06-20
location: Huatulco, Mexico
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2025-06-16
corr_author: '1'
date_created: 2025-07-21T08:18:26Z
date_published: 2025-06-13T00:00:00Z
date_updated: 2026-02-16T11:46:51Z
day: '13'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1145/3732772.3733544
ec_funded: 1
external_id:
isi:
- '001525534800030'
file:
- access_level: open_access
checksum: cd628fe54d96e9fc6cc789bb8145422b
content_type: application/pdf
creator: dernst
date_created: 2025-08-05T07:15:31Z
date_updated: 2025-08-05T07:15:31Z
file_id: '20122'
file_name: 2025_PODC_Chatterjee.pdf
file_size: 783297
relation: main_file
success: 1
file_date_updated: 2025-08-05T07:15:31Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/745
month: '06'
oa: 1
oa_version: Published Version
page: 241-251
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9798400718854'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: 'When is liquid democracy possible?: On the manipulation of variance'
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
year: '2025'
...
---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '20254'
abstract:
- lang: eng
text: 'We examine population structures for their ability to maintain diversity
in neutral evolution. We use the general framework of evolutionary graph theory
and consider birth–death (bd) and death–birth (db) updating. The population is
of size N. Initially all individuals represent different types. The basic question
is: what is the time TN until one type takes over the population? This time is
known as consensus time in computer science and as total coalescent time in evolutionary
biology. For the complete graph, it is known that TN is quadratic in N for db
and bd. For the cycle, we prove that TN is cubic in N for db and bd. For the star,
we prove that TN is cubic for bd and quasilinear (N log N) for db. For the double
star, we show that TN is quartic for bd. We derive upper and lower bounds for
all undirected graphs for bd and db. We also show the Pareto front of graphs (of
size N = 8) that maintain diversity the longest for bd and db. Further, we show
that some graphs that quickly homogenize can maintain high levels of diversity
longer than graphs that slowly homogenize. For directed graphs, we give simple
contracting star-like structures that have superexponential time scales for maintaining
diversity.'
acknowledgement: J.S. and K.C. were supported by the European Research Council CoG
863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12. J.T. was supported
by GAČR grant 25-17377S and by Charles Univ. projects UNCE 24/SCI/008 and PRIMUS
24/SCI/012.
article_number: pgaf252
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: David A.
full_name: Brewster, David A.
last_name: Brewster
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Dylan
full_name: Roscow, Dylan
last_name: Roscow
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Martin A.
full_name: Nowak, Martin A.
last_name: Nowak
citation:
ama: Brewster DA, Svoboda J, Roscow D, Chatterjee K, Tkadlec J, Nowak MA. Maintaining
diversity in structured populations. PNAS Nexus. 2025;4(8). doi:10.1093/pnasnexus/pgaf252
apa: Brewster, D. A., Svoboda, J., Roscow, D., Chatterjee, K., Tkadlec, J., &
Nowak, M. A. (2025). Maintaining diversity in structured populations. PNAS
Nexus. Oxford University Press. https://doi.org/10.1093/pnasnexus/pgaf252
chicago: Brewster, David A., Jakub Svoboda, Dylan Roscow, Krishnendu Chatterjee,
Josef Tkadlec, and Martin A. Nowak. “Maintaining Diversity in Structured Populations.”
PNAS Nexus. Oxford University Press, 2025. https://doi.org/10.1093/pnasnexus/pgaf252.
ieee: D. A. Brewster, J. Svoboda, D. Roscow, K. Chatterjee, J. Tkadlec, and M. A.
Nowak, “Maintaining diversity in structured populations,” PNAS Nexus, vol.
4, no. 8. Oxford University Press, 2025.
ista: Brewster DA, Svoboda J, Roscow D, Chatterjee K, Tkadlec J, Nowak MA. 2025.
Maintaining diversity in structured populations. PNAS Nexus. 4(8), pgaf252.
mla: Brewster, David A., et al. “Maintaining Diversity in Structured Populations.”
PNAS Nexus, vol. 4, no. 8, pgaf252, Oxford University Press, 2025, doi:10.1093/pnasnexus/pgaf252.
short: D.A. Brewster, J. Svoboda, D. Roscow, K. Chatterjee, J. Tkadlec, M.A. Nowak,
PNAS Nexus 4 (2025).
date_created: 2025-08-31T22:01:32Z
date_published: 2025-08-01T00:00:00Z
date_updated: 2026-02-16T12:23:19Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1093/pnasnexus/pgaf252
ec_funded: 1
external_id:
arxiv:
- '2503.09841'
file:
- access_level: open_access
checksum: 8a5e82c6f842e3220ec96028c9374b69
content_type: application/pdf
creator: dernst
date_created: 2025-09-03T06:20:08Z
date_updated: 2025-09-03T06:20:08Z
file_id: '20280'
file_name: 2025_PNASNexus_Brewster.pdf
file_size: 1086419
relation: main_file
success: 1
file_date_updated: 2025-09-03T06:20:08Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '8'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: PNAS Nexus
publication_identifier:
eissn:
- 2752-6542
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maintaining diversity in structured populations
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19445'
abstract:
- lang: eng
text: "In reconfiguration, we are given two solutions to a graph problem, such as
Vertex Cover or Dominating Set, with each solution represented by a placement
of tokens on vertices of the graph. Our task is to reconfigure one into the other
using small steps while ensuring the intermediate configurations of tokens are
also valid solutions. The two commonly studied settings are Token Jumping and
Token Sliding, which allows moving a single token to an arbitrary or an adjacent
vertex, respectively.\r\n\r\nWe introduce new rules that generalize Token Jumping,
parameterized by the number of tokens allowed to move at once and by the maximum
distance of each move. Our main contribution is identifying minimal rules that
allow reconfiguring any possible given solution into any other for Independent
Set, Vertex Cover, and Dominating Set. For each minimal rule, we also provide
an efficient algorithm that finds a corresponding reconfiguration sequence.\r\n\r\nWe
further focus on the rule that allows each token to move to an adjacent vertex
in a single step. This natural variant turns out to be the minimal rule that guarantees
reconfigurability for Vertex Cover. We determine the computational complexity
of deciding whether a (shortest) reconfiguration sequence exists under this rule
for the three studied problems. While reachability for Vertex Cover is shown to
be in P, finding a shortest sequence is shown to be NP-complete. For Independent
Set and Dominating Set, even reachability is shown to be PSPACE-complete."
acknowledgement: J. M. Křišťan acknowledges the support of the Czech Science Foundation
Grant No. 24-12046S. This work was supported by the Grant Agency of the Czech Technical
University in Prague, grant No. SGS23/205/OHK3/3T/18. J. Svoboda acknowledges the
support of the ERC CoG 863818 (ForM-SMArt) grant.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jan Matyáš
full_name: Křišťan, Jan Matyáš
last_name: Křišťan
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Křišťan JM, Svoboda J. Reconfiguration using generalized token jumping. In:
19th International Conference and Workshops on Algorithms and Computation.
Vol 15411. Springer Nature; 2025:244-265. doi:10.1007/978-981-96-2845-2_16'
apa: 'Křišťan, J. M., & Svoboda, J. (2025). Reconfiguration using generalized
token jumping. In 19th International Conference and Workshops on Algorithms
and Computation (Vol. 15411, pp. 244–265). Chengdu, China: Springer Nature.
https://doi.org/10.1007/978-981-96-2845-2_16'
chicago: Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized
Token Jumping.” In 19th International Conference and Workshops on Algorithms
and Computation, 15411:244–65. Springer Nature, 2025. https://doi.org/10.1007/978-981-96-2845-2_16.
ieee: J. M. Křišťan and J. Svoboda, “Reconfiguration using generalized token jumping,”
in 19th International Conference and Workshops on Algorithms and Computation,
Chengdu, China, 2025, vol. 15411, pp. 244–265.
ista: 'Křišťan JM, Svoboda J. 2025. Reconfiguration using generalized token jumping.
19th International Conference and Workshops on Algorithms and Computation. WALCOM:
International Conference and Workshops on Algorithms and Computation, LNCS, vol.
15411, 244–265.'
mla: Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized
Token Jumping.” 19th International Conference and Workshops on Algorithms and
Computation, vol. 15411, Springer Nature, 2025, pp. 244–65, doi:10.1007/978-981-96-2845-2_16.
short: J.M. Křišťan, J. Svoboda, in:, 19th International Conference and Workshops
on Algorithms and Computation, Springer Nature, 2025, pp. 244–265.
conference:
end_date: 2025-03-02
location: Chengdu, China
name: 'WALCOM: International Conference and Workshops on Algorithms and Computation'
start_date: 2025-02-28
date_created: 2025-03-23T23:01:27Z
date_published: 2025-02-20T00:00:00Z
date_updated: 2025-09-30T11:14:33Z
day: '20'
department:
- _id: KrCh
doi: 10.1007/978-981-96-2845-2_16
ec_funded: 1
external_id:
arxiv:
- '2411.12582'
isi:
- '001537885900016'
intvolume: ' 15411'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2411.12582
month: '02'
oa: 1
oa_version: Preprint
page: 244-265
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 19th International Conference and Workshops on Algorithms and Computation
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9789819628445'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reconfiguration using generalized token jumping
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15411
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19600'
abstract:
- lang: eng
text: In this work, we explore route discovery in private payment channel networks.
We first determine what “ideal" privacy for a routing protocol means in this setting.
We observe that protocols achieving this strong privacy definition exist by leveraging
Multi-Party Computation but they are inherently inefficient as they must involve
the entire network. We then present protocols with weaker privacy guarantees but
much better efficiency (involving only a small fraction of the nodes). The core
idea is that both sender and receiver gossip a message which propagates through
the network, and the moment any node in the network receives both messages, a
path is found. In our first protocol the message is always sent to all neighbouring
nodes with a delay proportional to the fees of that edge. In our second protocol
the message is only sent to one neighbour chosen randomly with a probability proportional
to its degree. We additionally propose a more realistic notion of privacy in order
to measure the privacy leakage of our protocols in practice. Our realistic notion
of privacy challenges an adversary that join the network with a fixed budget to
create channels to guess the sender and receiver of a transaction upon receiving
messages from our protocols. Simulations of our protocols on the Lightning network
topology (for random transactions and uniform fees) show that 1) forming edges
with high degree nodes is a more effective attack strategy for the adversary,
2) there is a tradeoff between the number of nodes involved in our protocols (privacy)
and the optimality of the discovered path, and 3) our protocols involve a very
small fraction of the network on average.
acknowledgement: This work was supported in part by the ERC CoG 863818 (ForM-SMArt),
Austrian Science Fund (FWF) 10.55776/COE12, and MOE-T2EP20122-0014 (Data-Driven
Distributed Algorithms) grants.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Zeta
full_name: Avarikioti, Zeta
last_name: Avarikioti
- first_name: Mahsa
full_name: Bastankhah, Mahsa
last_name: Bastankhah
- first_name: Mohammad Ali
full_name: Maddah-Ali, Mohammad Ali
last_name: Maddah-Ali
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX.
Route discovery in private payment channel networks. In: Computer Security.
ESORICS 2024 International Workshops. Vol 15263. Springer Nature; 2025:207-223.
doi:10.1007/978-3-031-82349-7_15'
apa: 'Avarikioti, Z., Bastankhah, M., Maddah-Ali, M. A., Pietrzak, K. Z., Svoboda,
J., & Yeo, M. X. (2025). Route discovery in private payment channel networks.
In Computer Security. ESORICS 2024 International Workshops (Vol. 15263,
pp. 207–223). Bydgoszcz, Poland: Springer Nature. https://doi.org/10.1007/978-3-031-82349-7_15'
chicago: Avarikioti, Zeta, Mahsa Bastankhah, Mohammad Ali Maddah-Ali, Krzysztof
Z Pietrzak, Jakub Svoboda, and Michelle X Yeo. “Route Discovery in Private Payment
Channel Networks.” In Computer Security. ESORICS 2024 International Workshops,
15263:207–23. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-82349-7_15.
ieee: Z. Avarikioti, M. Bastankhah, M. A. Maddah-Ali, K. Z. Pietrzak, J. Svoboda,
and M. X. Yeo, “Route discovery in private payment channel networks,” in Computer
Security. ESORICS 2024 International Workshops, Bydgoszcz, Poland, 2025, vol.
15263, pp. 207–223.
ista: 'Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX.
2025. Route discovery in private payment channel networks. Computer Security.
ESORICS 2024 International Workshops. ESORICS: European Symposium on Research
in Computer Security, LNCS, vol. 15263, 207–223.'
mla: Avarikioti, Zeta, et al. “Route Discovery in Private Payment Channel Networks.”
Computer Security. ESORICS 2024 International Workshops, vol. 15263, Springer
Nature, 2025, pp. 207–23, doi:10.1007/978-3-031-82349-7_15.
short: Z. Avarikioti, M. Bastankhah, M.A. Maddah-Ali, K.Z. Pietrzak, J. Svoboda,
M.X. Yeo, in:, Computer Security. ESORICS 2024 International Workshops, Springer
Nature, 2025, pp. 207–223.
conference:
end_date: 2024-09-20
location: Bydgoszcz, Poland
name: 'ESORICS: European Symposium on Research in Computer Security'
start_date: 2024-09-16
date_created: 2025-04-20T22:01:28Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-11-05T07:52:35Z
day: '01'
department:
- _id: KrPi
- _id: KrCh
doi: 10.1007/978-3-031-82349-7_15
ec_funded: 1
intvolume: ' 15263'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1539
month: '04'
oa: 1
oa_version: Submitted Version
page: 207-223
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Computer Security. ESORICS 2024 International Workshops
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031823480'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Route discovery in private payment channel networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15263
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19669'
abstract:
- lang: eng
text: 'We consider a class of optimization problems defined by a system of linear
equations with min and max operators. This class of optimization problems has
been studied under restrictive conditions, such as, (C1) the halting or stability
condition; (C2) the non-negative coefficients condition; (C3) the sum upto 1 condition;
and (C4) the only min or only max operator condition. Several seminal results
in the literature focus on special cases. For example, turn-based stochastic games
correspond to conditions C2 and C3; and Markov decision process to conditions
C2, C3, and C4. However, the systematic computational complexity study of all
the cases has not been explored, which we address in this work. Some highlights
of our results are: with conditions C2 and C4, and with conditions C3 and C4,
the problem is NP-complete, whereas with condition C1 only, the problem is in
UP intersects coUP. Finally, we establish the computational complexity of the
decision problem of checking the respective conditions.'
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant and the Austrian Science Fund (FWF) 10.55776/COE12 grant.
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ruichen
full_name: Luo, Ruichen
id: b391db08-1ffe-11ee-8b67-d18ddcfb5a14
last_name: Luo
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. Linear equations with min
and max operators: Computational complexity. In: Proceedings of the 39th AAAI
Conference on Artificial Intelligence. Vol 39. Association for the Advancement
of Artificial Intelligence; 2025:11150-11157. doi:10.1609/aaai.v39i11.33212'
apa: 'Chatterjee, K., Luo, R., Saona Urmeneta, R. J., & Svoboda, J. (2025).
Linear equations with min and max operators: Computational complexity. In Proceedings
of the 39th AAAI Conference on Artificial Intelligence (Vol. 39, pp. 11150–11157).
Philadelphia, PA, United States: Association for the Advancement of Artificial
Intelligence. https://doi.org/10.1609/aaai.v39i11.33212'
chicago: 'Chatterjee, Krishnendu, Ruichen Luo, Raimundo J Saona Urmeneta, and Jakub
Svoboda. “Linear Equations with Min and Max Operators: Computational Complexity.”
In Proceedings of the 39th AAAI Conference on Artificial Intelligence,
39:11150–57. Association for the Advancement of Artificial Intelligence, 2025.
https://doi.org/10.1609/aaai.v39i11.33212.'
ieee: 'K. Chatterjee, R. Luo, R. J. Saona Urmeneta, and J. Svoboda, “Linear equations
with min and max operators: Computational complexity,” in Proceedings of the
39th AAAI Conference on Artificial Intelligence, Philadelphia, PA, United
States, 2025, vol. 39, no. 11, pp. 11150–11157.'
ista: 'Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. 2025. Linear equations
with min and max operators: Computational complexity. Proceedings of the 39th
AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence
vol. 39, 11150–11157.'
mla: 'Chatterjee, Krishnendu, et al. “Linear Equations with Min and Max Operators:
Computational Complexity.” Proceedings of the 39th AAAI Conference on Artificial
Intelligence, vol. 39, no. 11, Association for the Advancement of Artificial
Intelligence, 2025, pp. 11150–57, doi:10.1609/aaai.v39i11.33212.'
short: K. Chatterjee, R. Luo, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings
of the 39th AAAI Conference on Artificial Intelligence, Association for the Advancement
of Artificial Intelligence, 2025, pp. 11150–11157.
conference:
end_date: 2025-03-04
location: Philadelphia, PA, United States
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2025-02-25
corr_author: '1'
date_created: 2025-05-11T22:02:40Z
date_published: 2025-04-11T00:00:00Z
date_updated: 2025-05-12T09:42:09Z
day: '11'
department:
- _id: KrCh
doi: 10.1609/aaai.v39i11.33212
ec_funded: 1
external_id:
arxiv:
- '2412.12228'
intvolume: ' 39'
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.12228
month: '04'
oa: 1
oa_version: Preprint
page: 11150-11157
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 39th AAAI Conference on Artificial Intelligence
publication_identifier:
eissn:
- 2374-3468
issn:
- 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Linear equations with min and max operators: Computational complexity'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 39
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19740'
abstract:
- lang: eng
text: Two standard models for probabilistic systems are Markov chains (MCs) and
Markov decision processes (MDPs). Classic objectives for such probabilistic models
for control and planning problems are reachability and stochastic shortest path.
The widely studied algorithmic approach for these problems is the Value Iteration
(VI) algorithm which iteratively applies local updates called Bellman updates.
There are many practical approaches for VI in the literature but they all require
exponentially many Bellman updates for MCs in the worst case. A preprocessing
step is an algorithm that is discrete, graph-theoretical, and requires linear
space. An important open question is whether, after a polynomial-time preprocessing,
VI can be achieved with sub-exponentially many Bellman updates. In this work,
we present a new approach for VI based on guessing values. Our theoretical contributions
are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm
after which, along with guessing values, VI requires only subexponentially many
Bellman updates. Second, we present an improved analysis of the speed of convergence
of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our
new approach. Experimental results show that our approach provides a considerable
improvement over existing VI-based approaches on several benchmark examples from
the literature.
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant and Austrian Science Fund (FWF) 10.55776/COE12 grant.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mahdi
full_name: Jafariraviz, Mahdi
last_name: Jafariraviz
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. Value iteration
with guessing for Markov chains and Markov decision processes. In: 31st International
Conference on Tools and Algorithms for the Construction and Analysis of Systems.
Vol 15697. Springer Nature; 2025:217-236. doi:10.1007/978-3-031-90653-4_11'
apa: 'Chatterjee, K., Jafariraviz, M., Saona Urmeneta, R. J., & Svoboda, J.
(2025). Value iteration with guessing for Markov chains and Markov decision processes.
In 31st International Conference on Tools and Algorithms for the Construction
and Analysis of Systems (Vol. 15697, pp. 217–236). Hamilton, ON, Canada: Springer
Nature. https://doi.org/10.1007/978-3-031-90653-4_11'
chicago: Chatterjee, Krishnendu, Mahdi Jafariraviz, Raimundo J Saona Urmeneta, and
Jakub Svoboda. “Value Iteration with Guessing for Markov Chains and Markov Decision
Processes.” In 31st International Conference on Tools and Algorithms for the
Construction and Analysis of Systems, 15697:217–36. Springer Nature, 2025.
https://doi.org/10.1007/978-3-031-90653-4_11.
ieee: K. Chatterjee, M. Jafariraviz, R. J. Saona Urmeneta, and J. Svoboda, “Value
iteration with guessing for Markov chains and Markov decision processes,” in 31st
International Conference on Tools and Algorithms for the Construction and Analysis
of Systems, Hamilton, ON, Canada, 2025, vol. 15697, pp. 217–236.
ista: 'Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. 2025. Value iteration
with guessing for Markov chains and Markov decision processes. 31st International
Conference on Tools and Algorithms for the Construction and Analysis of Systems.
TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS,
vol. 15697, 217–236.'
mla: Chatterjee, Krishnendu, et al. “Value Iteration with Guessing for Markov Chains
and Markov Decision Processes.” 31st International Conference on Tools and
Algorithms for the Construction and Analysis of Systems, vol. 15697, Springer
Nature, 2025, pp. 217–36, doi:10.1007/978-3-031-90653-4_11.
short: K. Chatterjee, M. Jafariraviz, R.J. Saona Urmeneta, J. Svoboda, in:, 31st
International Conference on Tools and Algorithms for the Construction and Analysis
of Systems, Springer Nature, 2025, pp. 217–236.
conference:
end_date: 2025-05-08
location: Hamilton, ON, Canada
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2025-05-03
corr_author: '1'
date_created: 2025-05-25T22:17:06Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2025-06-02T07:35:06Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-031-90653-4_11
ec_funded: 1
external_id:
arxiv:
- '2505.06769'
file:
- access_level: open_access
checksum: 45da6efbcbed20aada16c48c8e55e2d6
content_type: application/pdf
creator: dernst
date_created: 2025-06-02T07:31:12Z
date_updated: 2025-06-02T07:31:12Z
file_id: '19767'
file_name: 2025_TACAS_Chatterjee.pdf
file_size: 557481
relation: main_file
success: 1
file_date_updated: 2025-06-02T07:31:12Z
has_accepted_license: '1'
intvolume: ' 15697'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 217-236
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 31st International Conference on Tools and Algorithms for the Construction
and Analysis of Systems
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031906527'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Value iteration with guessing for Markov chains and Markov decision 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: 15697
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20857'
abstract:
- lang: eng
text: 'Evolutionary games provide a flexible mathematical framework for many problems
in biology and social evolution. Prisoners’ dilemma, and in particular, the important
special case of donation games, represents social dilemmas where cooperation is
mutually beneficial, yet defection is preferred by selfish agents. In evolutionary
games on networks, the agents interact over a population structure. The existence
of population structures that promote cooperative behavior is a fascinating and
active research topic. Previous research establishes structures promoting cooperation
in the limit of weak selection where the benefit-to-cost ratio β exceeds 1.5.
The existence of such structures for medium and strong selection for 1 < ß < 2
and for weak selection for 1 < ß < 1.5 has been a long-standing open question.
First, we answer the open questions in the affirmative: For every selection strength
and every ß > 1, we construct networks promoting cooperation. Second, we present
a robustness result with respect to β and selection strength: Our structures promote
cooperation for a range of these parameter values rather than specific parameter
values. Finally, we supplement our theoretical results with simulation results
on small population structures that show the effectiveness of our construction
over well-studied population structures.'
acknowledgement: J.S. and K.C. were supported by the European Research Council CoG
863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Svoboda J, Chatterjee K. Promoters of cooperation in evolutionary games. Proceedings
of the National Academy of Sciences. 2025;122(51):e2524109122. doi:10.1073/pnas.2524109122
apa: Svoboda, J., & Chatterjee, K. (2025). Promoters of cooperation in evolutionary
games. Proceedings of the National Academy of Sciences. National Academy
of Sciences. https://doi.org/10.1073/pnas.2524109122
chicago: Svoboda, Jakub, and Krishnendu Chatterjee. “Promoters of Cooperation in
Evolutionary Games.” Proceedings of the National Academy of Sciences. National
Academy of Sciences, 2025. https://doi.org/10.1073/pnas.2524109122.
ieee: J. Svoboda and K. Chatterjee, “Promoters of cooperation in evolutionary games,”
Proceedings of the National Academy of Sciences, vol. 122, no. 51. National
Academy of Sciences, p. e2524109122, 2025.
ista: Svoboda J, Chatterjee K. 2025. Promoters of cooperation in evolutionary games.
Proceedings of the National Academy of Sciences. 122(51), e2524109122.
mla: Svoboda, Jakub, and Krishnendu Chatterjee. “Promoters of Cooperation in Evolutionary
Games.” Proceedings of the National Academy of Sciences, vol. 122, no.
51, National Academy of Sciences, 2025, p. e2524109122, doi:10.1073/pnas.2524109122.
short: J. Svoboda, K. Chatterjee, Proceedings of the National Academy of Sciences
122 (2025) e2524109122.
corr_author: '1'
date_created: 2025-12-28T23:01:26Z
date_published: 2025-12-15T00:00:00Z
date_updated: 2026-02-16T12:34:04Z
day: '15'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1073/pnas.2524109122
ec_funded: 1
external_id:
pmid:
- '41397136'
file:
- access_level: open_access
checksum: dd50b62a1efc28c0133fe9c11dbee53c
content_type: application/pdf
creator: dernst
date_created: 2025-12-29T09:36:50Z
date_updated: 2025-12-29T09:36:50Z
file_id: '20860'
file_name: 2025_PNAS_Svoboda.pdf
file_size: 2308124
relation: main_file
success: 1
file_date_updated: 2025-12-29T09:36:50Z
has_accepted_license: '1'
intvolume: ' 122'
issue: '51'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: e2524109122
pmid: 1
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the National Academy of Sciences
publication_identifier:
eissn:
- 1091-6490
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: Promoters of cooperation in evolutionary games
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 122
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '21412'
abstract:
- lang: eng
text: "Payment channel networks (PCNs) are a promising technology that alleviates
blockchain scalability by shifting the transaction load from the blockchain to
the PCN. Nevertheless, the network topology has to be carefully designed to maximise
the transaction throughput in PCNs. Additionally, users in PCNs also have to make
optimal decisions on which transactions to forward and which to reject to prolong
the lifetime of their channels. In this work, we consider an input sequence of
transactions over p parties. Each transaction consists of a transaction size,
source, and target, and can be either accepted or rejected (entailing a cost).
The goal is to design a PCN topology among the p cooperating parties, along with
the channel capacities, and then output a decision for each transaction in the
sequence to minimise the cost of creating and augmenting channels, as well as
the cost of rejecting transactions. Our main contribution is an \U0001D4AA(p)
approximation algorithm for the problem with p parties. We further show that with
some assumptions on the distribution of transactions, we can reduce the approximation
ratio to \U0001D4AA(√p). We complement our theoretical analysis with an empirical
study of our assumptions and approach in the context of the Lightning Network."
acknowledgement: "Chatterjee, Krishnendu: European Research Council CoG 863818 (ForM-SMArt)
and Austrian Science Fund 10.55776/COE12.\r\nKřišťan, Jan Matyáš: Czech Science
Foundation Grant no. 24-12046S.\r\nSchmid, Stefan: German Research Foundation (DFG)
project ReNO (SPP 2378) from 2023-2027.\r\nSvoboda, Jakub: European Research Council
CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.\r\nYeo, Michelle:
MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms)."
alternative_title:
- LIPIcs
article_number: '23'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Jan Matyáš
full_name: Křišťan, Jan Matyáš
last_name: Křišťan
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. Boosting payment channel
network liquidity with topology optimization and transaction selection. In: 39th
International Symposium on Distributed Computing. Vol 356. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.DISC.2025.23'
apa: 'Chatterjee, K., Křišťan, J. M., Schmid, S., Svoboda, J., & Yeo, M. X.
(2025). Boosting payment channel network liquidity with topology optimization
and transaction selection. In 39th International Symposium on Distributed Computing
(Vol. 356). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.DISC.2025.23'
chicago: Chatterjee, Krishnendu, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda,
and Michelle X Yeo. “Boosting Payment Channel Network Liquidity with Topology
Optimization and Transaction Selection.” In 39th International Symposium on
Distributed Computing, Vol. 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.DISC.2025.23.
ieee: K. Chatterjee, J. M. Křišťan, S. Schmid, J. Svoboda, and M. X. Yeo, “Boosting
payment channel network liquidity with topology optimization and transaction selection,”
in 39th International Symposium on Distributed Computing, Berlin, Germany,
2025, vol. 356.
ista: 'Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. 2025. Boosting payment
channel network liquidity with topology optimization and transaction selection.
39th International Symposium on Distributed Computing. DISC: Symposium on Distributed
Computing, LIPIcs, vol. 356, 23.'
mla: Chatterjee, Krishnendu, et al. “Boosting Payment Channel Network Liquidity
with Topology Optimization and Transaction Selection.” 39th International Symposium
on Distributed Computing, vol. 356, 23, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, doi:10.4230/LIPIcs.DISC.2025.23.
short: K. Chatterjee, J.M. Křišťan, S. Schmid, J. Svoboda, M.X. Yeo, in:, 39th International
Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025.
conference:
end_date: 2025-10-31
location: Berlin, Germany
name: 'DISC: Symposium on Distributed Computing'
start_date: 2025-10-27
date_created: 2026-03-08T23:01:46Z
date_published: 2025-10-22T00:00:00Z
date_updated: 2026-03-09T11:52:58Z
day: '22'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.DISC.2025.23
ec_funded: 1
external_id:
arxiv:
- '2508.14524'
file:
- access_level: open_access
checksum: 8e3d1594365df60163d9df22158a37b1
content_type: application/pdf
creator: dernst
date_created: 2026-03-09T11:51:59Z
date_updated: 2026-03-09T11:51:59Z
file_id: '21418'
file_name: 2025_DISC_Chatterjee.pdf
file_size: 1130069
relation: main_file
success: 1
file_date_updated: 2026-03-09T11:51:59Z
has_accepted_license: '1'
intvolume: ' 356'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1484.pdf
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 39th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959774024'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Boosting payment channel network liquidity with topology optimization and transaction
selection
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 356
year: '2025'
...
---
OA_place: publisher
_id: '20138'
abstract:
- lang: eng
text: "The evolution shapes the world around us.\r\nNot only in biology, where the
fittest individuals spread their genes but also in physics and social dynamics,
the evolutionary forces determine the development of a state of matter or public
opinions.\r\nMany models describe these dynamics.\r\nThis thesis examines the
role of the structure in the models of selection.\r\nThe population structure
is represented as a graph or a network, and each vertex is occupied by one individual.\r\nEvery
individual has a type and fitness that represents the reproductive potential and
depends on the type, occupied vertex, and the arrangement of the neighbors.\r\nThe
evolution is modeled in discrete steps; in one step, one individual is replaced
by a neighbor selected randomly with the influence of fitness.\r\n\r\n\r\n\r\nThe
role of the networks is widely examined in the literature.\r\nThe structures that
promote the spread of the desired type compared to the structureless case are
called amplifiers.\r\nThe existence of amplifiers in various settings is an intensively
studied topic, and in some settings, the amplifiers have been identified.\r\nMoreover,
there are other important questions about the number of steps until one type spreads
over the whole network (fixation time), the computational complexity, and the
questions about the robustness of these processes.\r\n\r\n\r\nThis thesis explores
the role of structure in evolution from many perspectives.\r\nFirst, it introduces
different models and various choices that can be made in the models of evolution.\r\nIt
highlights the role of the structure in the real world and how this is reflected
in these models.\r\nThen, it describes the previous results and open problems.\r\nSecond,
the thesis describes an amplifier for two variants of the Moran process: one with
a constant birth rate and the other with a constant death rate.\r\nThis is an
important contribution to the robustness of the amplification.\r\nThird, the thesis
determines the complexity of spatial games.\r\nThese are processes where the fitness
comes from a game, and the strength of selection is high.\r\nIt shows that determining
the fate of cooperation in these games is a PSPACE-complete problem.\r\nFourth,
the thesis describes the amplifier of cooperation for spatial games.\r\nThis is
the first amplifier in this setting.\r\nFifth, the thesis examines the coexistence
in the Moran process with environmental heterogeneity.\r\nIn this setting, the
fitness depends not only on the type of the individual but also on the occupied
vertex.\r\nThe chapter determines the relationship between the interactions of
vertices of different types and the coexistence time.\r\nSixth, the thesis examines
the social balance on networks and proposes a stochastic dynamic partially aware
of the state of the graph, which reaches a balanced position quickly.\r\nFinally,
the thesis presents conclusions and outlines the directions for future work.\r\n\r\n\r\n"
acknowledgement: "This work was supported by the European Research Council CoG 863818
(ForMSMArt) and Austrian Science Fund 10.55776/COE12.\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: Svoboda J. Structural properties of games on graphs. 2025. doi:10.15479/AT-ISTA-20138
apa: Svoboda, J. (2025). Structural properties of games on graphs. Institute
of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-20138
chicago: Svoboda, Jakub. “Structural Properties of Games on Graphs.” Institute of
Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-20138.
ieee: J. Svoboda, “Structural properties of games on graphs,” Institute of Science
and Technology Austria, 2025.
ista: Svoboda J. 2025. Structural properties of games on graphs. Institute of Science
and Technology Austria.
mla: Svoboda, Jakub. Structural Properties of Games on Graphs. Institute
of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-20138.
short: J. Svoboda, Structural Properties of Games on Graphs, Institute of Science
and Technology Austria, 2025.
corr_author: '1'
date_created: 2025-08-05T14:33:59Z
date_published: 2025-08-05T00:00:00Z
date_updated: 2026-04-07T11:49:12Z
day: '05'
ddc:
- '000'
- '519'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrCh
doi: 10.15479/AT-ISTA-20138
ec_funded: 1
file:
- access_level: open_access
checksum: c6c4df9777f4537940de7ab392ad57e2
content_type: application/pdf
creator: jsvoboda
date_created: 2025-08-14T09:54:43Z
date_updated: 2025-08-14T09:54:43Z
file_id: '20177'
file_name: 2025_Svoboda_Jakub_Thesis.pdf
file_size: 5927291
relation: main_file
success: 1
- access_level: closed
checksum: 485e9f9822821bc03666d245d80aaa08
content_type: application/zip
creator: jsvoboda
date_created: 2025-08-14T09:55:20Z
date_updated: 2025-08-21T11:48:39Z
file_id: '20178'
file_name: 2025_Svoboda_Jakub_Thesis.zip
file_size: 6731815
relation: source_file
file_date_updated: 2025-08-21T11:48:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '167'
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '12787'
relation: part_of_dissertation
status: public
- id: '12101'
relation: part_of_dissertation
status: public
- id: '12257'
relation: part_of_dissertation
status: public
- id: '15297'
relation: part_of_dissertation
status: public
- id: '18703'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
title: Structural properties of games on graphs
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2025'
...
---
OA_place: other
OA_type: green
_id: '18925'
abstract:
- lang: eng
text: Given the increasingly stringent requirements on the performance and efficiency
of communication networks, over the last years, great efforts have been made to
render networks more flexible and programmable. In particular, modern networks
support a flexible rerouting of flows, e.g., depending on the dynamically changing
traffic or network conditions. However, the underlying algorithmic problems are
still not well-understood today.In this paper, we revisit the k-Network Flow Update
problem that asks for a schedule to reroute k unsplittable flows from their current
paths to the given new paths, in a congestion-free manner in a capacitated network.
We show that the problem is already NP-hard for three acyclic flows on simple
directed graphs. Our main contribution is an efficient algorithm for sparse networks;
specifically the algorithm is fixed parameter tractable in the number of flows
and the treewidth of a graph that is the union of all flows. Our results also
settle the open complexity question in the literature.
acknowledgement: Research was supported by the Austrian Science Fund (FWF), project
I 5025-N (DELTA), 2020-2024. Esra Ceylan’s research was supported by FFG, FEMtech
Praktika für Studentinnen. Jakub Svoboda and Krishnendu Chatterjee were supported
by the European Research Council (ERC) CoG 863818 (ForM-SMArt).
article_processing_charge: No
author:
- first_name: Esra
full_name: Ceylan, Esra
id: cb1ca1d8-dcc0-11ef-baa5-9f1b3ef75933
last_name: Ceylan
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Ceylan E, Chatterjee K, Schmid S, Svoboda J. Congestion-free rerouting of
network flows: Hardness and an FPT algorithm. In: NOMS 2024-2024 IEEE Network
Operations and Management Symposium. IEEE; 2024. doi:10.1109/noms59830.2024.10575579'
apa: 'Ceylan, E., Chatterjee, K., Schmid, S., & Svoboda, J. (2024). Congestion-free
rerouting of network flows: Hardness and an FPT algorithm. In NOMS 2024-2024
IEEE Network Operations and Management Symposium. Seoul, Republic of Korea:
IEEE. https://doi.org/10.1109/noms59830.2024.10575579'
chicago: 'Ceylan, Esra, Krishnendu Chatterjee, Stefan Schmid, and Jakub Svoboda.
“Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” In
NOMS 2024-2024 IEEE Network Operations and Management Symposium. IEEE,
2024. https://doi.org/10.1109/noms59830.2024.10575579.'
ieee: 'E. Ceylan, K. Chatterjee, S. Schmid, and J. Svoboda, “Congestion-free rerouting
of network flows: Hardness and an FPT algorithm,” in NOMS 2024-2024 IEEE Network
Operations and Management Symposium, Seoul, Republic of Korea, 2024.'
ista: 'Ceylan E, Chatterjee K, Schmid S, Svoboda J. 2024. Congestion-free rerouting
of network flows: Hardness and an FPT algorithm. NOMS 2024-2024 IEEE Network Operations
and Management Symposium. NOMS: Network Operations and Management Symposiu .'
mla: 'Ceylan, Esra, et al. “Congestion-Free Rerouting of Network Flows: Hardness
and an FPT Algorithm.” NOMS 2024-2024 IEEE Network Operations and Management
Symposium, IEEE, 2024, doi:10.1109/noms59830.2024.10575579.'
short: E. Ceylan, K. Chatterjee, S. Schmid, J. Svoboda, in:, NOMS 2024-2024 IEEE
Network Operations and Management Symposium, IEEE, 2024.
conference:
end_date: 2024-05-10
location: Seoul, Republic of Korea
name: 'NOMS: Network Operations and Management Symposiu '
start_date: 2024-05-06
corr_author: '1'
date_created: 2025-01-27T15:06:45Z
date_published: 2024-05-01T00:00:00Z
date_updated: 2025-11-05T07:34:27Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/noms59830.2024.10575579
ec_funded: 1
external_id:
isi:
- '001270140300143'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://schmiste.github.io/noms24.pdf
month: '05'
oa: 1
oa_version: Submitted Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: bd622a5c-d553-11ed-ba76-bae280ba8aff
grant_number: '894907'
name: Graphical Games
publication: NOMS 2024-2024 IEEE Network Operations and Management Symposium
publication_identifier:
eissn:
- 2374-9709
isbn:
- '9798350327946'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Congestion-free rerouting of network flows: Hardness and an FPT algorithm'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...
---
OA_place: publisher
OA_type: green
_id: '18974'
abstract:
- lang: eng
text: Reinforcement Learning (RL) from temporal logical specifications is a fundamental
problem in sequential decision making. One of the basic and core such specification
is the reachability specification that requires a target set to be eventually
visited. Despite strong empirical results for RL from such specifications, the
theoretical guarantees are bleak, including the impossibility of Probably Approximately
Correct (PAC) guarantee for reachability specifications. Given the impossibility
result, in this work we consider the problem of RL from reachability specifications
along with the information of expected conditional distance (ECD). We present
(a) lower bound results which establish the necessity of ECD information for PAC
guarantees and (b) an algorithm that establishes PAC-guarantees given the ECD
information. To the best of our knowledge, this is the first RL from reachability
specifications that does not make any assumptions on the underlying environment
to learn policies.
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Suguman
full_name: Bansal, Suguman
last_name: Bansal
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Svoboda J, Bansal S, Chatterjee K. Reinforcement learning from reachability
specifications: PAC guarantees with expected conditional distance. In: 41st
International Conference on Machine Learning. Vol 235. ML Research Press;
2024:47331-47344.'
apa: 'Svoboda, J., Bansal, S., & Chatterjee, K. (2024). Reinforcement learning
from reachability specifications: PAC guarantees with expected conditional distance.
In 41st International Conference on Machine Learning (Vol. 235, pp. 47331–47344).
Vienna, Austria: ML Research Press.'
chicago: 'Svoboda, Jakub, Suguman Bansal, and Krishnendu Chatterjee. “Reinforcement
Learning from Reachability Specifications: PAC Guarantees with Expected Conditional
Distance.” In 41st International Conference on Machine Learning, 235:47331–44.
ML Research Press, 2024.'
ieee: 'J. Svoboda, S. Bansal, and K. Chatterjee, “Reinforcement learning from reachability
specifications: PAC guarantees with expected conditional distance,” in 41st
International Conference on Machine Learning, Vienna, Austria, 2024, vol.
235, pp. 47331–47344.'
ista: 'Svoboda J, Bansal S, Chatterjee K. 2024. Reinforcement learning from reachability
specifications: PAC guarantees with expected conditional distance. 41st International
Conference on Machine Learning. ICML: International Conference on Machine Learning,
PMLR, vol. 235, 47331–47344.'
mla: 'Svoboda, Jakub, et al. “Reinforcement Learning from Reachability Specifications:
PAC Guarantees with Expected Conditional Distance.” 41st International Conference
on Machine Learning, vol. 235, ML Research Press, 2024, pp. 47331–44.'
short: J. Svoboda, S. Bansal, K. Chatterjee, in:, 41st International Conference
on Machine Learning, ML Research Press, 2024, pp. 47331–47344.
conference:
end_date: 2024-07-27
location: Vienna, Austria
name: 'ICML: International Conference on Machine Learning'
start_date: 2024-07-21
corr_author: '1'
date_created: 2025-01-30T07:45:22Z
date_published: 2024-07-29T00:00:00Z
date_updated: 2025-01-30T07:46:16Z
day: '29'
department:
- _id: KrCh
intvolume: ' 235'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://openreview.net/forum?id=mXUDDL4r1Q
month: '07'
oa: 1
oa_version: Preprint
page: 47331-47344
publication: 41st International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Reinforcement learning from reachability specifications: PAC guarantees with
expected conditional distance'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 235
year: '2024'
...
---
_id: '14820'
abstract:
- lang: eng
text: "We consider a natural problem dealing with weighted packet selection across
a rechargeable link, which e.g., finds applications in cryptocurrency networks.
The capacity of a link (u, v) is determined by how many nodes u and v allocate
for this link. Specifically, the input is a finite ordered sequence of packets
that arrive in both directions along a link. Given (u, v) and a packet of weight
x going from u to v, node u can either accept or reject the packet. If u accepts
the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity
on \r\n increases by x. If a node rejects the packet, this will entail a cost
affinely linear in the weight of the packet. A link is “rechargeable” in the sense
that the total capacity of the link has to remain constant, but the allocation
of capacity at the ends of the link can depend arbitrarily on the nodes' decisions.
The goal is to minimise the sum of the capacity injected into the link and the
cost of rejecting packets. We show that the problem is NP-hard, but can be approximated
efficiently with a ratio of (1+E) . (1+3) for some arbitrary E>0."
acknowledgement: We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful
discussions about different variants of the problem. This work is supported by the
European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025,
the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant
470029389 (FlexNets), 2021-2024.
article_number: '114353'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links
in cryptocurrency networks: Complexity and approximation. Theoretical Computer
Science. 2024;989. doi:10.1016/j.tcs.2023.114353'
apa: 'Schmid, S., Svoboda, J., & Yeo, M. X. (2024). Weighted packet selection
for rechargeable links in cryptocurrency networks: Complexity and approximation.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.114353'
chicago: 'Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection
for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.”
Theoretical Computer Science. Elsevier, 2024. https://doi.org/10.1016/j.tcs.2023.114353.'
ieee: 'S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable
links in cryptocurrency networks: Complexity and approximation,” Theoretical
Computer Science, vol. 989. Elsevier, 2024.'
ista: 'Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable
links in cryptocurrency networks: Complexity and approximation. Theoretical Computer
Science. 989, 114353.'
mla: 'Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in
Cryptocurrency Networks: Complexity and Approximation.” Theoretical Computer
Science, vol. 989, 114353, Elsevier, 2024, doi:10.1016/j.tcs.2023.114353.'
short: S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).
corr_author: '1'
date_created: 2024-01-16T13:40:41Z
date_published: 2024-03-21T00:00:00Z
date_updated: 2025-12-02T14:02:37Z
day: '21'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1016/j.tcs.2023.114353
ec_funded: 1
external_id:
isi:
- '001168211400001'
file:
- access_level: open_access
checksum: efd5b7e738bf845312ba53889a3e13e4
content_type: application/pdf
creator: dernst
date_created: 2024-07-16T12:02:25Z
date_updated: 2024-07-16T12:02:25Z
file_id: '17263'
file_name: 2024_TheorComputerScience_Schmid.pdf
file_size: 603570
relation: main_file
success: 1
file_date_updated: 2024-07-16T12:02:25Z
has_accepted_license: '1'
intvolume: ' 989'
isi: 1
keyword:
- General Computer Science
- Theoretical Computer Science
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '19985'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Weighted packet selection for rechargeable links in cryptocurrency networks:
Complexity and approximation'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 989
year: '2024'
...
---
_id: '17098'
abstract:
- lang: eng
text: Turn-based discounted-sum games are two-player zero-sum games played on finite
directed graphs. The vertices of the graph are partitioned between player 1 and
player 2. Plays are infinite walks on the graph where the next vertex is decided
by a player that owns the current vertex. Each edge is assigned an integer weight
and the payoff of a play is the discounted-sum of the weights of the play. The
goal of player 1 is to maximize the discounted-sum payoff against the adversarial
player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems
that belong to this complexity class and the existence of a polynomial-time algorithm
is a major open question. Since breaking the general exponential barrier has been
a challenging problem, faster parameterized algorithms have been considered. If
the discount factor is expressed in unary, then discounted-sum games can be solved
in polynomial time. However, if the discount factor is arbitrary (or expressed
in binary), but the weights are in unary, none of the existing approaches yield
a sub-exponential bound. Our main result is a new analysis technique for a classical
algorithm (namely, the strategy iteration algorithm) that present a new runtime
bound which is [EQUATION] for game graphs with n vertices and absolute weights
of at most W. In particular, our result yields a deterministic sub-exponential
bound for games with weights that are constant or represented in unary.
acknowledgement: "This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant.\r\n"
article_number: '6'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
citation:
ama: 'Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. Deterministic sub-exponential
algorithm for discounted-sum games with unary weights. In: 39th Annual ACM/IEEE
Symposium on Logic in Computer Science. Association for Computing Machinery;
2024. doi:10.1145/3661814.3662080'
apa: 'Asadi, A., Chatterjee, K., Svoboda, J., & Saona Urmeneta, R. J. (2024).
Deterministic sub-exponential algorithm for discounted-sum games with unary weights.
In 39th Annual ACM/IEEE Symposium on Logic in Computer Science. Tallinn,
Estonia: Association for Computing Machinery. https://doi.org/10.1145/3661814.3662080'
chicago: Asadi, Ali, Krishnendu Chatterjee, Jakub Svoboda, and Raimundo J Saona
Urmeneta. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with
Unary Weights.” In 39th Annual ACM/IEEE Symposium on Logic in Computer Science.
Association for Computing Machinery, 2024. https://doi.org/10.1145/3661814.3662080.
ieee: A. Asadi, K. Chatterjee, J. Svoboda, and R. J. Saona Urmeneta, “Deterministic
sub-exponential algorithm for discounted-sum games with unary weights,” in 39th
Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn, Estonia,
2024.
ista: 'Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. 2024. Deterministic
sub-exponential algorithm for discounted-sum games with unary weights. 39th Annual
ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science,
6.'
mla: Asadi, Ali, et al. “Deterministic Sub-Exponential Algorithm for Discounted-Sum
Games with Unary Weights.” 39th Annual ACM/IEEE Symposium on Logic in Computer
Science, 6, Association for Computing Machinery, 2024, doi:10.1145/3661814.3662080.
short: A. Asadi, K. Chatterjee, J. Svoboda, R.J. Saona Urmeneta, in:, 39th Annual
ACM/IEEE Symposium on Logic in Computer Science, Association for Computing Machinery,
2024.
conference:
end_date: 2024-07-11
location: Tallinn, Estonia
name: 'LICS: Logic in Computer Science'
start_date: 2024-07-08
corr_author: '1'
date_created: 2024-06-03T07:43:15Z
date_published: 2024-07-08T00:00:00Z
date_updated: 2025-09-08T07:44:29Z
day: '08'
department:
- _id: KrCh
doi: 10.1145/3661814.3662080
ec_funded: 1
external_id:
arxiv:
- '2405.02479'
isi:
- '001275042100006'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2405.02479
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
eissn:
- 1043-6871
isbn:
- '9798400706608'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic sub-exponential algorithm for discounted-sum games with unary
weights
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '17099'
abstract:
- lang: eng
text: "We study two-player zero-sum concurrent stochastic games with finite state
and action space played for an infinite number of steps. In every step, the two
players simultaneously and independently choose an action. Given the current state
and the chosen actions, the next state is obtained according to a stochastic transition
function. An objective is a measurable function on plays (or infinite trajectories)
of the game, and the value for an objective is the maximal expectation that the
player can guarantee against the adversarial player. We consider: (a) stateful-discounted
objectives, which are similar to the classical discounted-sum objectives, but
states are associated with different discount factors rather than a single discount
factor; and (b) parity objectives, which are a canonical representation for ω-regular
objectives. For stateful-discounted objectives, given an ordering of the discount
factors, the limit value is the limit of the value of the stateful-discounted
objectives, as the discount factors approach zero according to the given order.\r\nThe
computational problem we consider is the approximation of the value within an
arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for
the limit value of statefuldiscounted objectives and in PSPACE for parity objectives.
The best-known algorithms for both the above problems are at least exponential
time, with an exponential dependence on the number of states and actions. Our
main results for the value approximation problem for the limit value of stateful-discounted
objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity;
and (b) we present algorithms that improve the dependency on the number of actions
in the exponent from linear to logarithmic. In particular, if the number of states
is constant, our algorithms run in polynomial time."
acknowledgement: "This research was partially supported by ERC CoG 863818 (ForM-SMArt),
Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la
Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)"
alternative_title:
- LIPIcs
article_number: '5'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic
games with stateful-discounted and parity objectives: Complexity and algorithms.
In: 44th IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.FSTTCS.2024.5'
apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Svoboda, J. (2024).
Concurrent stochastic games with stateful-discounted and parity objectives: Complexity
and algorithms. In 44th IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (Vol. 323). Gujarat, India: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5'
chicago: 'Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub
Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives:
Complexity and Algorithms.” In 44th IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, Vol. 323. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5.'
ieee: 'A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent
stochastic games with stateful-discounted and parity objectives: Complexity and
algorithms,” in 44th IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, Gujarat, India, 2024, vol. 323.'
ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic
games with stateful-discounted and parity objectives: Complexity and algorithms.
44th IARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer
Science, LIPIcs, vol. 323, 5.'
mla: 'Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and
Parity Objectives: Complexity and Algorithms.” 44th IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science, vol.
323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.FSTTCS.2024.5.'
short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS
Annual Conference on Foundations of Software Technology and Theoretical Computer
Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-12-18
location: Gujarat, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2024-12-16
corr_author: '1'
date_created: 2024-06-03T07:44:27Z
date_published: 2024-12-05T00:00:00Z
date_updated: 2025-12-02T13:40:52Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2024.5
ec_funded: 1
external_id:
arxiv:
- '2405.02486'
isi:
- '001537516500005'
file:
- access_level: open_access
checksum: 5b544ab4692b93300b404435c036ddd4
content_type: application/pdf
creator: dernst
date_created: 2025-01-08T09:49:31Z
date_updated: 2025-01-08T09:49:31Z
file_id: '18777'
file_name: 2024_LIPIcs_Asadi.pdf
file_size: 847960
relation: main_file
success: 1
file_date_updated: 2025-01-08T09:49:31Z
has_accepted_license: '1'
intvolume: ' 323'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 44th IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- '9783959773553'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Concurrent stochastic games with stateful-discounted and parity objectives:
Complexity and algorithms'
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: 323
year: '2024'
...
---
APC_amount: 3149,96 EUR
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '15297'
abstract:
- lang: eng
text: Populations evolve by accumulating advantageous mutations. Every population
has some spatial structure that can be modeled by an underlying network. The network
then influences the probability that new advantageous mutations fixate. Amplifiers
of selection are networks that increase the fixation probability of advantageous
mutants, as compared to the unstructured fully-connected network. Whether or not
a network is an amplifier depends on the choice of the random process that governs
the evolutionary dynamics. Two popular choices are Moran process with Birth-death
updating and Moran process with death-Birth updating. Interestingly, while some
networks are amplifiers under Birth-death updating and other networks are amplifiers
under death-Birth updating, so far no spatial structures have been found that
function as an amplifier under both types of updating simultaneously. In this
work, we identify networks that act as amplifiers of selection under both versions
of the Moran process. The amplifiers are robust, modular, and increase fixation
probability for any mutant fitness advantage in a range r ∈ (1, 1.2). To complement
this positive result, we also prove that for certain quantities closely related
to fixation probability, it is impossible to improve them simultaneously for both
versions of the Moran process. Together, our results highlight how the two versions
of the Moran process differ and what they have in common.
acknowledgement: "We thank Gavin Rees for helpful discussions. J.S., S.J., and K.C
were supported by\r\nEuropean Research Council (ERC) CoG 863818 (ForM-SMArt). J.T
was supported by Center for Foundations of Modern Computer Science (Charles University
project UNCE/SCI/004) and by the project PRIMUS/24/SCI/012 from Charles University. "
article_number: e1012008
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Soham Shrikant
full_name: Joshi, Soham Shrikant
id: f97aac0e-f57c-11ee-93d0-a5a82d8df168
last_name: Joshi
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Svoboda J, Joshi SS, Tkadlec J, Chatterjee K. Amplifiers of selection for the
Moran process with both Birth-death and death-Birth updating. PLoS Computational
Biology. 2024;20(3). doi:10.1371/journal.pcbi.1012008
apa: Svoboda, J., Joshi, S. S., Tkadlec, J., & Chatterjee, K. (2024). Amplifiers
of selection for the Moran process with both Birth-death and death-Birth updating.
PLoS Computational Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1012008
chicago: Svoboda, Jakub, Soham Shrikant Joshi, Josef Tkadlec, and Krishnendu Chatterjee.
“Amplifiers of Selection for the Moran Process with Both Birth-Death and Death-Birth
Updating.” PLoS Computational Biology. Public Library of Science, 2024.
https://doi.org/10.1371/journal.pcbi.1012008.
ieee: J. Svoboda, S. S. Joshi, J. Tkadlec, and K. Chatterjee, “Amplifiers of selection
for the Moran process with both Birth-death and death-Birth updating,” PLoS
Computational Biology, vol. 20, no. 3. Public Library of Science, 2024.
ista: Svoboda J, Joshi SS, Tkadlec J, Chatterjee K. 2024. Amplifiers of selection
for the Moran process with both Birth-death and death-Birth updating. PLoS Computational
Biology. 20(3), e1012008.
mla: Svoboda, Jakub, et al. “Amplifiers of Selection for the Moran Process with
Both Birth-Death and Death-Birth Updating.” PLoS Computational Biology,
vol. 20, no. 3, e1012008, Public Library of Science, 2024, doi:10.1371/journal.pcbi.1012008.
short: J. Svoboda, S.S. Joshi, J. Tkadlec, K. Chatterjee, PLoS Computational Biology
20 (2024).
corr_author: '1'
date_created: 2024-04-07T22:00:55Z
date_published: 2024-03-29T00:00:00Z
date_updated: 2026-04-07T11:49:11Z
day: '29'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1371/journal.pcbi.1012008
ec_funded: 1
external_id:
arxiv:
- '2401.14914'
isi:
- '001194482400002'
file:
- access_level: open_access
checksum: a511cf369d9172beb123fe73f291b5cc
content_type: application/pdf
creator: dernst
date_created: 2024-08-20T10:52:28Z
date_updated: 2024-08-20T10:52:28Z
file_id: '17450'
file_name: 2024_PloSComBio_Svoboda.pdf
file_size: 1425292
relation: main_file
success: 1
file_date_updated: 2024-08-20T10:52:28Z
has_accepted_license: '1'
intvolume: ' 20'
isi: 1
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: PLoS Computational Biology
publication_identifier:
eissn:
- 1553-7358
issn:
- 1553-734X
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
related_material:
record:
- id: '20138'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Amplifiers of selection for the Moran process with both Birth-death and death-Birth
updating
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 20
year: '2024'
...
---
APC_amount: 3143,76 EUR
OA_place: publisher
OA_type: hybrid
_id: '18703'
abstract:
- lang: eng
text: 'Spatial games provide a simple and elegant mathematical model to study the
evolution of cooperation in networks. In spatial games, individuals reside in
vertices, adopt simple strategies, and interact with neighbors to receive a payoff.
Depending on their own and neighbors’ payoffs, individuals can change their strategy.
The payoff is determined by the Prisoners’ Dilemma, a classical matrix game, where
players cooperate or defect. While cooperation is the desired behavior, defection
provides a higher payoff for a selfish individual. There are many theoretical
and empirical studies related to the role of the network in the evolution of cooperation.
However, the fundamental question of whether there exist networks that for low
initial cooperation rate ensure a high chance of fixation, i.e., cooperation spreads
across the whole population, has remained elusive for spatial games with strong
selection. In this work, we answer this fundamental question in the affirmative
by presenting network structures that ensure high fixation probability for cooperators
in the strong selection regime. Besides, our structures have many desirable properties:
(a) they ensure the spread of cooperation even for a low initial density of cooperation
and high temptation of defection, (b) they have constant degrees, and (c) the
number of steps, until cooperation spreads, is at most quadratic in the size of
the network.'
acknowledgement: J.S. and K.C. were supported by the European Research Council CoG
863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.
article_number: e2405605121
article_processing_charge: Yes
article_type: original
author:
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Svoboda J, Chatterjee K. Density amplifiers of cooperation for spatial games.
Proceedings of the National Academy of Sciences of the United States of America.
2024;121(50). doi:10.1073/pnas.2405605121
apa: Svoboda, J., & Chatterjee, K. (2024). Density amplifiers of cooperation
for spatial games. Proceedings of the National Academy of Sciences of the United
States of America. National Academy of Sciences. https://doi.org/10.1073/pnas.2405605121
chicago: Svoboda, Jakub, and Krishnendu Chatterjee. “Density Amplifiers of Cooperation
for Spatial Games.” Proceedings of the National Academy of Sciences of the
United States of America. National Academy of Sciences, 2024. https://doi.org/10.1073/pnas.2405605121.
ieee: J. Svoboda and K. Chatterjee, “Density amplifiers of cooperation for spatial
games,” Proceedings of the National Academy of Sciences of the United States
of America, vol. 121, no. 50. National Academy of Sciences, 2024.
ista: Svoboda J, Chatterjee K. 2024. Density amplifiers of cooperation for spatial
games. Proceedings of the National Academy of Sciences of the United States of
America. 121(50), e2405605121.
mla: Svoboda, Jakub, and Krishnendu Chatterjee. “Density Amplifiers of Cooperation
for Spatial Games.” Proceedings of the National Academy of Sciences of the
United States of America, vol. 121, no. 50, e2405605121, National Academy
of Sciences, 2024, doi:10.1073/pnas.2405605121.
short: J. Svoboda, K. Chatterjee, Proceedings of the National Academy of Sciences
of the United States of America 121 (2024).
corr_author: '1'
date_created: 2024-12-22T23:01:47Z
date_published: 2024-12-10T00:00:00Z
date_updated: 2026-04-07T11:49:11Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1073/pnas.2405605121
ec_funded: 1
external_id:
isi:
- '001379596100014'
pmid:
- '39642209'
file:
- access_level: open_access
checksum: 0115e9090b478e0644308c6dab58605b
content_type: application/pdf
creator: dernst
date_created: 2025-01-02T12:14:15Z
date_updated: 2025-01-02T12:14:15Z
file_id: '18721'
file_name: 2024_PNAS_Svoboda.pdf
file_size: 2491151
relation: main_file
success: 1
file_date_updated: 2025-01-02T12:14:15Z
has_accepted_license: '1'
intvolume: ' 121'
isi: 1
issue: '50'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the National Academy of Sciences of the United States
of America
publication_identifier:
eissn:
- 1091-6490
issn:
- 0027-8424
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
related_material:
record:
- id: '20138'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Density amplifiers of cooperation for spatial games
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 121
year: '2024'
...
---
_id: '14456'
abstract:
- lang: eng
text: In this paper, we present novel algorithms that efficiently compute a shortest
reconfiguration sequence between two given dominating sets in trees and interval
graphs under the TOKEN SLIDING model. In this problem, a graph is provided along
with its two dominating sets, which can be imagined as tokens placed on vertices.
The objective is to find a shortest sequence of dominating sets that transforms
one set into the other, with each set in the sequence resulting from sliding a
single token in the previous set. While identifying any sequence has been well
studied, our work presents the first polynomial algorithms for this optimization
variant in the context of dominating sets.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jan Matyáš
full_name: Křišťan, Jan Matyáš
last_name: Křišťan
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Křišťan JM, Svoboda J. Shortest dominating set reconfiguration under token
sliding. In: 24th International Symposium on Fundamentals of Computation Theory.
Vol 14292. Springer Nature; 2023:333-347. doi:10.1007/978-3-031-43587-4_24'
apa: 'Křišťan, J. M., & Svoboda, J. (2023). Shortest dominating set reconfiguration
under token sliding. In 24th International Symposium on Fundamentals of Computation
Theory (Vol. 14292, pp. 333–347). Trier, Germany: Springer Nature. https://doi.org/10.1007/978-3-031-43587-4_24'
chicago: Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration
under Token Sliding.” In 24th International Symposium on Fundamentals of Computation
Theory, 14292:333–47. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-43587-4_24.
ieee: J. M. Křišťan and J. Svoboda, “Shortest dominating set reconfiguration under
token sliding,” in 24th International Symposium on Fundamentals of Computation
Theory, Trier, Germany, 2023, vol. 14292, pp. 333–347.
ista: 'Křišťan JM, Svoboda J. 2023. Shortest dominating set reconfiguration under
token sliding. 24th International Symposium on Fundamentals of Computation Theory.
FCT: Fundamentals of Computation Theory, LNCS, vol. 14292, 333–347.'
mla: Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration
under Token Sliding.” 24th International Symposium on Fundamentals of Computation
Theory, vol. 14292, Springer Nature, 2023, pp. 333–47, doi:10.1007/978-3-031-43587-4_24.
short: J.M. Křišťan, J. Svoboda, in:, 24th International Symposium on Fundamentals
of Computation Theory, Springer Nature, 2023, pp. 333–347.
conference:
end_date: 2023-09-21
location: Trier, Germany
name: 'FCT: Fundamentals of Computation Theory'
start_date: 2023-09-18
date_created: 2023-10-29T23:01:16Z
date_published: 2023-09-21T00:00:00Z
date_updated: 2025-09-09T13:07:40Z
day: '21'
department:
- _id: KrCh
doi: 10.1007/978-3-031-43587-4_24
external_id:
arxiv:
- '2307.10847'
isi:
- '001162288800024'
intvolume: ' 14292'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2307.10847
month: '09'
oa: 1
oa_version: Preprint
page: 333-347
publication: 24th International Symposium on Fundamentals of Computation Theory
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031435867'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: erratum
url: https://doi.org/10.1007/978-3-031-43587-4_31
scopus_import: '1'
status: public
title: Shortest dominating set reconfiguration under token sliding
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14292
year: '2023'
...
---
OA_place: repository
OA_type: green
_id: '14736'
abstract:
- lang: eng
text: Payment channel networks (PCNs) are a promising technology to improve the
scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent
usage of certain routes may deplete channels in one direction, and hence prevent
further transactions. In order to reap the full potential of PCNs, recharging
and rebalancing mechanisms are required to provision channels, as well as an admission
control logic to decide which transactions to reject in case capacity is insufficient.
This paper presents a formal model of this optimisation problem. In particular,
we consider an online algorithms perspective, where transactions arrive over time
in an unpredictable manner. Our main contributions are competitive online algorithms
which come with provable guarantees over time. We empirically evaluate our algorithms
on randomly generated transactions to compare the average performance of our algorithms
to our theoretical bounds. We also show how this model and approach differs from
related problems in classic communication networks.
acknowledgement: Supported by the German Federal Ministry of Education and Research
(BMBF), grant 16KISK020K (6G-RIC), 2021–2025, and ERC CoG 863818 (ForM-SMArt).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Mahsa
full_name: Bastankhah, Mahsa
last_name: Bastankhah
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mohammad Ali
full_name: Maddah-Ali, Mohammad Ali
last_name: Maddah-Ali
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. R2:
Boosting liquidity in payment channel networks with online admission control.
In: 27th International Conference on Financial Cryptography and Data Security.
Vol 13950. Springer Nature; 2023:309-325. doi:10.1007/978-3-031-47754-6_18'
apa: 'Bastankhah, M., Chatterjee, K., Maddah-Ali, M. A., Schmid, S., Svoboda, J.,
& Yeo, M. X. (2023). R2: Boosting liquidity in payment channel networks with online
admission control. In 27th International Conference on Financial Cryptography
and Data Security (Vol. 13950, pp. 309–325). Bol, Brac, Croatia: Springer
Nature. https://doi.org/10.1007/978-3-031-47754-6_18'
chicago: 'Bastankhah, Mahsa, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali, Stefan
Schmid, Jakub Svoboda, and Michelle X Yeo. “R2: Boosting Liquidity in Payment
Channel Networks with Online Admission Control.” In 27th International Conference
on Financial Cryptography and Data Security, 13950:309–25. Springer Nature,
2023. https://doi.org/10.1007/978-3-031-47754-6_18.'
ieee: 'M. Bastankhah, K. Chatterjee, M. A. Maddah-Ali, S. Schmid, J. Svoboda, and
M. X. Yeo, “R2: Boosting liquidity in payment channel networks with online admission
control,” in 27th International Conference on Financial Cryptography and Data
Security, Bol, Brac, Croatia, 2023, vol. 13950, pp. 309–325.'
ista: 'Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. 2023.
R2: Boosting liquidity in payment channel networks with online admission control.
27th International Conference on Financial Cryptography and Data Security. FC:
Financial Cryptography and Data Security, LNCS, vol. 13950, 309–325.'
mla: 'Bastankhah, Mahsa, et al. “R2: Boosting Liquidity in Payment Channel Networks
with Online Admission Control.” 27th International Conference on Financial
Cryptography and Data Security, vol. 13950, Springer Nature, 2023, pp. 309–25,
doi:10.1007/978-3-031-47754-6_18.'
short: M. Bastankhah, K. Chatterjee, M.A. Maddah-Ali, S. Schmid, J. Svoboda, M.X.
Yeo, in:, 27th International Conference on Financial Cryptography and Data Security,
Springer Nature, 2023, pp. 309–325.
conference:
end_date: 2023-05-05
location: Bol, Brac, Croatia
name: 'FC: Financial Cryptography and Data Security'
start_date: 2023-05-01
date_created: 2024-01-08T09:30:22Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2025-11-05T07:37:31Z
day: '01'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1007/978-3-031-47754-6_18
ec_funded: 1
external_id:
isi:
- '001150222600018'
intvolume: ' 13950'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://openreview.net/forum?id=Dg0qdd9uha
month: '12'
oa: 1
oa_version: Submitted Version
page: 309-325
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 27th International Conference on Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031477546'
eissn:
- 1611-3349
isbn:
- '9783031477539'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'R2: Boosting liquidity in payment channel networks with online admission control'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13950
year: '2023'
...
---
_id: '12676'
abstract:
- lang: eng
text: Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum
games played on directed graphs with probabilistic transitions. The goal of player-max
is to maximize the probability to reach a target state against the adversarial
player-min. These games lie in NP ∩ coNP and are among the rare combinatorial
problems that belong to this complexity class for which the existence of polynomial-time
algorithm is a major open question. While randomized sub-exponential time algorithm
exists, all known deterministic algorithms require exponential time in the worst-case.
An important open question has been whether faster algorithms can be obtained
parametrized by the treewidth of the game graph. Even deterministic sub-exponential
time algorithm for constant treewidth turn-based stochastic games has remain elusive.
In this work our main result is a deterministic algorithm to solve turn-based
stochastic games that, given a game with n states, treewidth at most t, and the
bit-complexity of the probabilistic transition function log D, has running time
O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time
for games with constant or poly-logarithmic treewidth.
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm
for turn-based stochastic games with bounded treewidth. In: Proceedings of
the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial
and Applied Mathematics; 2023:4590-4605. doi:10.1137/1.9781611977554.ch173'
apa: 'Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., & Svoboda, J.
(2023). Faster algorithm for turn-based stochastic games with bounded treewidth.
In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
(pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611977554.ch173'
chicago: Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta,
and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded
Treewidth.” In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete
Algorithms, 4590–4605. Society for Industrial and Applied Mathematics, 2023.
https://doi.org/10.1137/1.9781611977554.ch173.
ieee: K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster
algorithm for turn-based stochastic games with bounded treewidth,” in Proceedings
of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florence, Italy,
2023, pp. 4590–4605.
ista: 'Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster
algorithm for turn-based stochastic games with bounded treewidth. Proceedings
of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium
on Discrete Algorithms, 4590–4605.'
mla: Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic
Games with Bounded Treewidth.” Proceedings of the 2023 Annual ACM-SIAM Symposium
on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023,
pp. 4590–605, doi:10.1137/1.9781611977554.ch173.
short: K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings
of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial
and Applied Mathematics, 2023, pp. 4590–4605.
conference:
end_date: 2023-01-25
location: Florence, Italy
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2023-01-22
corr_author: '1'
date_created: 2023-02-24T12:20:47Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2025-04-14T07:52:47Z
day: '01'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1137/1.9781611977554.ch173
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1137/1.9781611977554.ch173
month: '02'
oa: 1
oa_version: Published Version
page: 4590-4605
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '9781611977554'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
status: public
title: Faster algorithm for turn-based stochastic games with bounded treewidth
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
OA_type: closed access
_id: '19985'
abstract:
- lang: eng
text: We consider a natural problem dealing with weighted packet selection across
a rechargeable link, which e.g., finds applications in cryptocurrency networks.
The capacity of a link (u, v) is determined by how much nodes u and v allocate
for this link. Specifically, the input is a finite ordered sequence of packets
that arrive in both directions along a link. Given (u, v) and a packet of weight
x going from u to v, node u can either accept or reject the packet. If u accepts
the packet, the capacity on link (u, v) decreases by x. Correspondingly, v’s capacity
on (u, v) increases by x. If a node rejects the packet, this will entail a cost
affinely linear in the weight of the packet. A link is “rechargeable” in the sense
that the total capacity of the link has to remain constant, but the allocation
of capacity at the ends of the link can depend arbitrarily on the nodes’ decisions.
The goal is to minimise the sum of the capacity injected into the link and the
cost of rejecting packets. We show that the problem is NP-hard, but can be approximated
efficiently with a ratio of (1 + E) . (1 + square3) for some arbitrary E>0.
acknowledgement: We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful
discussions about different variants of the problem. This work is supported by the
European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025,
the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant
470029389 (FlexNets), 2021–2024.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Schmid S, Svoboda J, Yeo MX. Weighted acket selection for rechargeable links
in cryptocurrency networks: Complexity and approximation. In: 30th International
Colloquium on Structural Information and Communication Complexity. Vol 13892.
Springer Nature; 2023:576-594. doi:10.1007/978-3-031-32733-9_26'
apa: 'Schmid, S., Svoboda, J., & Yeo, M. X. (2023). Weighted acket selection
for rechargeable links in cryptocurrency networks: Complexity and approximation.
In 30th International Colloquium on Structural Information and Communication
Complexity (Vol. 13892, pp. 576–594). Alcalá de Henares, Spain: Springer Nature.
https://doi.org/10.1007/978-3-031-32733-9_26'
chicago: 'Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Acket Selection
for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.”
In 30th International Colloquium on Structural Information and Communication
Complexity, 13892:576–94. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-32733-9_26.'
ieee: 'S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted acket selection for rechargeable
links in cryptocurrency networks: Complexity and approximation,” in 30th International
Colloquium on Structural Information and Communication Complexity, Alcalá
de Henares, Spain, 2023, vol. 13892, pp. 576–594.'
ista: 'Schmid S, Svoboda J, Yeo MX. 2023. Weighted acket selection for rechargeable
links in cryptocurrency networks: Complexity and approximation. 30th International
Colloquium on Structural Information and Communication Complexity. SIROCCO: International
Colloquium on Structural Information and Communication Complexity, LNCS, vol.
13892, 576–594.'
mla: 'Schmid, Stefan, et al. “Weighted Acket Selection for Rechargeable Links in Cryptocurrency
Networks: Complexity and Approximation.” 30th International Colloquium on Structural
Information and Communication Complexity, vol. 13892, Springer Nature, 2023,
pp. 576–94, doi:10.1007/978-3-031-32733-9_26.'
short: S. Schmid, J. Svoboda, M.X. Yeo, in:, 30th International Colloquium on Structural
Information and Communication Complexity, Springer Nature, 2023, pp. 576–594.
conference:
end_date: 2023-06-09
location: Alcalá de Henares, Spain
name: 'SIROCCO: International Colloquium on Structural Information and Communication
Complexity'
start_date: 2023-06-06
corr_author: '1'
date_created: 2025-07-10T13:15:43Z
date_published: 2023-05-25T00:00:00Z
date_updated: 2025-12-02T14:02:38Z
day: '25'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1007/978-3-031-32733-9_26
ec_funded: 1
external_id:
isi:
- '001292782600026'
intvolume: ' 13892'
isi: 1
language:
- iso: eng
month: '05'
oa_version: None
page: 576-594
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 30th International Colloquium on Structural Information and Communication
Complexity
publication_identifier:
eisbn:
- '9783031327339'
eissn:
- 1611-3349
isbn:
- '9783031327322'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '14820'
relation: later_version
status: public
scopus_import: '1'
status: public
title: 'Weighted acket selection for rechargeable links in cryptocurrency networks:
Complexity and approximation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13892
year: '2023'
...