---
OA_place: publisher
OA_type: diamond
_id: '20299'
abstract:
- lang: eng
text: "Deterministic Markov Decision Processes (DMDPs) are a mathematical framework
for decision-making where the outcomes and future possible actions are deterministically
determined by the current action taken. DMDPs can be viewed as a finite directed
weighted graph, where in each step, the controller chooses an outgoing edge. An
objective is a measurable function on runs (or infinite trajectories) of the DMDP,
and the value for an objective is the maximal cumulative reward (or weight) that
the controller can guarantee. We consider the classical mean-payoff (aka limit-average)
objective, which is a basic and fundamental objective.\r\n\r\nHoward's policy
iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives.
Although Howard's algorithm performs well in practice, as experimental studies
suggested, the best known upper bound is exponential and the current known lower
bound is as follows: For the input size I, the algorithm requires (math formular)
iterations, where (math formular) hides the poly-logarithmic factors, i.e., the
current lower bound on iterations is sub-linear with respect to the input size.
Our main result is an improved lower bound for this fundamental algorithm where
we show that for the input size I, the algorithm requires (math formular) iterations."
acknowledgement: "This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant and Austrian Science Fund (FWF) 10.55776/COE12.\r\n"
alternative_title:
- PMLR
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: Jakob
full_name: De Raaij, Jakob
last_name: De Raaij
citation:
ama: 'Asadi A, Chatterjee K, De Raaij J. Lower bound on Howard policy iteration
for deterministic Markov Decision Processes. In: The 41st Conference on Uncertainty
in Artificial Intelligence. Vol 286. ML Research Press; 2025:223-232.'
apa: 'Asadi, A., Chatterjee, K., & De Raaij, J. (2025). Lower bound on Howard
policy iteration for deterministic Markov Decision Processes. In The 41st Conference
on Uncertainty in Artificial Intelligence (Vol. 286, pp. 223–232). Rio de
Janeiro, Brazil: ML Research Press.'
chicago: Asadi, Ali, Krishnendu Chatterjee, and Jakob De Raaij. “Lower Bound on
Howard Policy Iteration for Deterministic Markov Decision Processes.” In The
41st Conference on Uncertainty in Artificial Intelligence, 286:223–32. ML
Research Press, 2025.
ieee: A. Asadi, K. Chatterjee, and J. De Raaij, “Lower bound on Howard policy iteration
for deterministic Markov Decision Processes,” in The 41st Conference on Uncertainty
in Artificial Intelligence, Rio de Janeiro, Brazil, 2025, vol. 286, pp. 223–232.
ista: 'Asadi A, Chatterjee K, De Raaij J. 2025. Lower bound on Howard policy iteration
for deterministic Markov Decision Processes. The 41st Conference on Uncertainty
in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence,
PMLR, vol. 286, 223–232.'
mla: Asadi, Ali, et al. “Lower Bound on Howard Policy Iteration for Deterministic
Markov Decision Processes.” The 41st Conference on Uncertainty in Artificial
Intelligence, vol. 286, ML Research Press, 2025, pp. 223–32.
short: A. Asadi, K. Chatterjee, J. De Raaij, in:, The 41st Conference on Uncertainty
in Artificial Intelligence, ML Research Press, 2025, pp. 223–232.
conference:
end_date: 2025-07-25
location: Rio de Janeiro, Brazil
name: 'UAI: Conference on Uncertainty in Artificial Intelligence'
start_date: 2025-07-21
corr_author: '1'
date_created: 2025-09-07T22:01:34Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2026-09-16T07:01:05Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
ec_funded: 1
external_id:
arxiv:
- '2506.12254'
file:
- access_level: open_access
checksum: 4180c81bb6ed3b4f5c7a8e48d06520c6
content_type: application/pdf
creator: dernst
date_created: 2025-09-09T06:27:59Z
date_updated: 2025-09-09T06:27:59Z
file_id: '20313'
file_name: 2025_UAI_Asadi.pdf
file_size: 317097
relation: main_file
success: 1
file_date_updated: 2025-09-09T06:27:59Z
has_accepted_license: '1'
intvolume: ' 286'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 223-232
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: The 41st Conference on Uncertainty in Artificial Intelligence
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bound on Howard policy iteration for deterministic 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: 286
year: '2025'
...
---
OA_place: publisher
OA_type: diamond
_id: '20297'
abstract:
- lang: eng
text: "A standard model that arises in several applications in sequential decision-making
is partially observable Markov decision processes (POMDPs) where a decision-making
agent interacts with an uncertain environment. A basic objective in POMDPs is
the reachability objective, where given a target set of states, the goal is to
eventually arrive at one of them.\r\n\r\nThe limit-sure problem asks whether reachability
can be ensured with probability arbitrarily close to 1. In general, the limit-sure
reachability problem for POMDPs is undecidable. However, in many practical cases,
the most relevant question is the existence of policies with a small amount of
memory. In this work, we study the limit-sure reachability problem for POMDPs
with a fixed amount of memory. We establish that the computational complexity
of the problem is NP-complete."
acknowledgement: This research was partially supported by Austrian Science Fund (FWF)
10.55776/COE12, the support of the French Agence Nationale de la Recherche (ANR)
under reference ANR-21-CE40-0020 (CONVERGENCE project), and the ERC CoG 863818 (ForM-SMArt)
grant.
alternative_title:
- PMLR
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: Ali
full_name: Shafiee, Ali
id: 2783031a-7378-11f0-b2d0-f17f1db2ebad
last_name: Shafiee
citation:
ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. Limit-sure reachability
for small memory policies in POMDPs is NP-complete. In: The 41st Conference
on Uncertainty in Artificial Intelligence. Vol 286. ML Research Press; 2025:238-247.'
apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Shafiee, A. (2025).
Limit-sure reachability for small memory policies in POMDPs is NP-complete. In
The 41st Conference on Uncertainty in Artificial Intelligence (Vol. 286,
pp. 238–247). Rio de Janeiro, Brazil: ML Research Press.'
chicago: Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Ali Shafiee.
“Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.”
In The 41st Conference on Uncertainty in Artificial Intelligence, 286:238–47.
ML Research Press, 2025.
ieee: A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and A. Shafiee, “Limit-sure
reachability for small memory policies in POMDPs is NP-complete,” in The 41st
Conference on Uncertainty in Artificial Intelligence, Rio de Janeiro, Brazil,
2025, vol. 286, pp. 238–247.
ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. 2025. Limit-sure reachability
for small memory policies in POMDPs is NP-complete. The 41st Conference on Uncertainty
in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence,
PMLR, vol. 286, 238–247.'
mla: Asadi, Ali, et al. “Limit-Sure Reachability for Small Memory Policies in POMDPs
Is NP-Complete.” The 41st Conference on Uncertainty in Artificial Intelligence,
vol. 286, ML Research Press, 2025, pp. 238–47.
short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, A. Shafiee, in:, The 41st Conference
on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 238–247.
conference:
end_date: 2025-07-25
location: Rio de Janeiro, Brazil
name: 'UAI: Conference on Uncertainty in Artificial Intelligence'
start_date: 2025-07-21
corr_author: '1'
date_created: 2025-09-07T22:01:34Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2026-09-16T07:03:02Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
ec_funded: 1
external_id:
arxiv:
- '2412.00941'
file:
- access_level: open_access
checksum: 1a37ebe7ba73ab6985765bf0d17a0acc
content_type: application/pdf
creator: dernst
date_created: 2025-09-09T08:19:41Z
date_updated: 2025-09-09T08:19:41Z
file_id: '20315'
file_name: 2025_UAI_AsadiAli.pdf
file_size: 307458
relation: main_file
success: 1
file_date_updated: 2025-09-09T08:19:41Z
has_accepted_license: '1'
intvolume: ' 286'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 238-247
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: The 41st Conference on Uncertainty in Artificial Intelligence
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Limit-sure reachability for small memory policies in POMDPs is NP-complete
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: 286
year: '2025'
...
---
OA_place: publisher
OA_type: diamond
_id: '20296'
abstract:
- lang: eng
text: Learning-based systems are increasingly deployed across various domains, yet
the complexity of traditional neural networks poses significant challenges for
formal verification. Unlike conventional neural networks, learned Logic Gate Networks
(LGNs) replace multiplications with Boolean logic gates, yielding a sparse, netlist-like
architecture that is inherently more amenable to symbolic verification, while
still delivering promising performance. In this paper, we introduce a SAT encoding
for verifying global robustness and fairness in LGNs. We evaluate our method on
five benchmark datasets, including a newly constructed 5-class variant, and find
that LGNs are both verification-friendly and maintain strong predictive performance.
acknowledged_ssus:
- _id: ScienComp
acknowledgement: "This work is supported in part by the ERC grant under Grant No.
ERC-2020-AdG 101020093 and\r\nthe Austrian Science Fund (FWF) [10.55776/COE12].
This research was supported by the Scientific\r\nService Units (SSU) of ISTA through
resources provided by Scientific Computing (SciComp)."
alternative_title:
- PMLR
article_number: '26'
article_processing_charge: No
arxiv: 1
author:
- first_name: Fabian
full_name: Kresse, Fabian
id: faff3c84-23f6-11ef-9085-e5187b51c604
last_name: Kresse
- first_name: Zhengqi
full_name: Yu, Zhengqi
id: 20aa2ae8-f2f1-11ed-bbfa-8205053f1342
last_name: Yu
orcid: 0000-0002-4993-773X
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
citation:
ama: 'Kresse F, Yu E, Lampert C, Henzinger TA. Logic gate neural networks are good
for verification. In: 2nd International Conferenceon Neuro-Symbolic Systems.
Vol 288. ML Research Press; 2025.'
apa: 'Kresse, F., Yu, E., Lampert, C., & Henzinger, T. A. (2025). Logic gate
neural networks are good for verification. In 2nd International Conferenceon
Neuro-Symbolic Systems (Vol. 288). Philadephia, PA, United States: ML Research
Press.'
chicago: Kresse, Fabian, Emily Yu, Christoph Lampert, and Thomas A Henzinger. “Logic
Gate Neural Networks Are Good for Verification.” In 2nd International Conferenceon
Neuro-Symbolic Systems, Vol. 288. ML Research Press, 2025.
ieee: F. Kresse, E. Yu, C. Lampert, and T. A. Henzinger, “Logic gate neural networks
are good for verification,” in 2nd International Conferenceon Neuro-Symbolic
Systems, Philadephia, PA, United States, 2025, vol. 288.
ista: 'Kresse F, Yu E, Lampert C, Henzinger TA. 2025. Logic gate neural networks
are good for verification. 2nd International Conferenceon Neuro-Symbolic Systems.
NeuS: International Conferenceon Neuro-Symbolic Systems, PMLR, vol. 288, 26.'
mla: Kresse, Fabian, et al. “Logic Gate Neural Networks Are Good for Verification.”
2nd International Conferenceon Neuro-Symbolic Systems, vol. 288, 26, ML
Research Press, 2025.
short: F. Kresse, E. Yu, C. Lampert, T.A. Henzinger, in:, 2nd International Conferenceon
Neuro-Symbolic Systems, ML Research Press, 2025.
conference:
end_date: 2025-05-30
location: Philadephia, PA, United States
name: 'NeuS: International Conferenceon Neuro-Symbolic Systems'
start_date: 2025-05-28
corr_author: '1'
date_created: 2025-09-07T22:01:34Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2026-09-16T07:02:18Z
day: '01'
ddc:
- '000'
department:
- _id: ChLa
- _id: ToHe
ec_funded: 1
external_id:
arxiv:
- '2505.19932'
file:
- access_level: open_access
checksum: 90a32defed34787e771a5c1623b6b0d2
content_type: application/pdf
creator: dernst
date_created: 2025-09-09T08:10:13Z
date_updated: 2025-09-09T08:10:13Z
file_id: '20314'
file_name: 2025_NeuS_Kresse.pdf
file_size: 295466
relation: main_file
success: 1
file_date_updated: 2025-09-09T08:10:13Z
has_accepted_license: '1'
intvolume: ' 288'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
- _id: d8f03aaa-b035-11f1-8588-d5147fa879e0
grant_number: COE12
name: Bilateral Artificial Intelligence (Lampert)
publication: 2nd International Conferenceon Neuro-Symbolic Systems
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Logic gate neural networks are good for verification
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 288
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '19508'
abstract:
- lang: eng
text: We consider random two-player zero-sum dynamic games with perfect information
on a class of infinite directed graphs. Starting from a fixed vertex, the players
take turns to move a token along the edges of the graph. Every vertex is assigned
a payoff known in advance by both players. Every time the token visits a vertex,
Player 2 pays Player 1 the corresponding payoff. We consider a distribution over
such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic
directed graphs of bounded degree and sub-exponential expansion, we show that,
when the duration of the game tends to infinity, the value converges almost surely
to a constant at an exponential rate dominated in terms of the expansion. On the
other hand, for the infinite d-ary tree (that does not fall into the previous
class of graphs), we show convergence at a double-exponential rate.
acknowledgement: Open access funding provided by Institute of Science and Technology
(IST Austria). This work was supported by the French Agence Nationale de la Recherche
(ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002
(GrHyDy), by Fondecyt grant 1220174, by ANID Chile grant ACT210005, and by the ERC
CoG 863818 (ForM-SMArt) grant. This collaboration was mainly conducted during a
1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at
University of Chile in 2023, under the IRL program of CNRS. This work was supported
by Fondation CFM pour la Recherche. This paper has also been funded by the Agence
Nationale de la Recherche under grant ANR-17-EURE-0010 (Investissements d’Avenir
program).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Luc
full_name: Attia, Luc
last_name: Attia
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Dieter
full_name: Mitsche, Dieter
last_name: Mitsche
- 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: Bruno
full_name: Ziliotto, Bruno
last_name: Ziliotto
citation:
ama: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Random zero-sum
dynamic games on infinite directed graphs. Dynamic Games and Applications.
2025;15:1517-1535. doi:10.1007/s13235-025-00636-4
apa: Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., & Ziliotto,
B. (2025). Random zero-sum dynamic games on infinite directed graphs. Dynamic
Games and Applications. Springer Nature. https://doi.org/10.1007/s13235-025-00636-4
chicago: Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and
Bruno Ziliotto. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” Dynamic
Games and Applications. Springer Nature, 2025. https://doi.org/10.1007/s13235-025-00636-4.
ieee: L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Random
zero-sum dynamic games on infinite directed graphs,” Dynamic Games and Applications,
vol. 15. Springer Nature, pp. 1517–1535, 2025.
ista: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. 2025. Random
zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications.
15, 1517–1535.
mla: Attia, Luc, et al. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.”
Dynamic Games and Applications, vol. 15, Springer Nature, 2025, pp. 1517–35,
doi:10.1007/s13235-025-00636-4.
short: L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic
Games and Applications 15 (2025) 1517–1535.
corr_author: '1'
date_created: 2025-04-06T22:01:32Z
date_published: 2025-11-01T00:00:00Z
date_updated: 2026-09-16T07:00:33Z
day: '01'
ddc:
- '000'
department:
- _id: MaKw
- _id: KrCh
doi: 10.1007/s13235-025-00636-4
ec_funded: 1
external_id:
isi:
- '001449708900001'
file:
- access_level: open_access
checksum: b3a1b7eef40c9ac2acf3fef563081694
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T08:13:04Z
date_updated: 2025-12-30T08:13:04Z
file_id: '20891'
file_name: 2025_DynGamesAppl_Attia.pdf
file_size: 570994
relation: main_file
success: 1
file_date_updated: 2025-12-30T08:13:04Z
fulldoi: https://doi.org/10.1007/s13235-025-00636-4
has_accepted_license: '1'
intvolume: ' 15'
isi: 1
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1517-1535
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Dynamic Games and Applications
publication_identifier:
eissn:
- 2153-0793
issn:
- 2153-0785
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '20234'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Random zero-sum dynamic games on infinite directed graphs
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: 15
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20302'
abstract:
- lang: eng
text: "LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization,
with numerous applications in machine learning, large-scale data processing, and
federated learning. However, rigorously establishing their theoretical advantages
over simpler methods, such as minibatch SGD (MbSGD), has proven challenging, as
existing analyses often rely on strong assumptions, unrealistic premises, or overly
restrictive scenarios.\r\n\r\nIn this work, we revisit the convergence properties
of LocalSGD and SCAFFOLD under a variety of existing or weaker conditions, including
gradient similarity, Hessian similarity, weak convexity, and Lipschitz continuity
of the Hessian. Our analysis shows that (i) LocalSGD achieves faster convergence
compared to MbSGD for weakly convex functions without requiring stronger gradient
similarity assumptions; (ii) LocalSGD benefits significantly from higher-order
similarity and smoothness; and (iii) SCAFFOLD demonstrates faster convergence
than MbSGD for a broader class of non-quadratic functions. These theoretical insights
provide a clearer understanding of the conditions under which LocalSGD and SCAFFOLD
outperform MbSGD."
acknowledgement: "The authors thank for the helpful discussions with Eduard Gorbunov,
Kumar Kshitij Patel, Anton\r\nRodomanov, and Ali Zindari during the preparation
of this work. This work was partially done during the first author’s stays at CISPA
and at MBZUAI. The first author also acknowledges ERC CoG 863818 (ForM-SMArt) and
Austrian Science Fund (FWF) 10.55776/COE12."
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Ruichen
full_name: Luo, Ruichen
id: b391db08-1ffe-11ee-8b67-d18ddcfb5a14
last_name: Luo
- first_name: Sebastian U.
full_name: Stich, Sebastian U.
last_name: Stich
- first_name: Samuel
full_name: Horváth, Samuel
last_name: Horváth
- first_name: Martin
full_name: Takáč, Martin
last_name: Takáč
citation:
ama: 'Luo R, Stich SU, Horváth S, Takáč M. Revisiting LocalSGD and SCAFFOLD: Improved
rates and missing analysis. In: The 28th International Conference on Artificial
Intelligence and Statistics. Vol 258. ML Research Press; 2025:2539-2547.'
apa: 'Luo, R., Stich, S. U., Horváth, S., & Takáč, M. (2025). Revisiting LocalSGD
and SCAFFOLD: Improved rates and missing analysis. In The 28th International
Conference on Artificial Intelligence and Statistics (Vol. 258, pp. 2539–2547).
Mai Khao, Thailand: ML Research Press.'
chicago: 'Luo, Ruichen, Sebastian U. Stich, Samuel Horváth, and Martin Takáč. “Revisiting
LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis.” In The 28th International
Conference on Artificial Intelligence and Statistics, 258:2539–47. ML Research
Press, 2025.'
ieee: 'R. Luo, S. U. Stich, S. Horváth, and M. Takáč, “Revisiting LocalSGD and SCAFFOLD:
Improved rates and missing analysis,” in The 28th International Conference
on Artificial Intelligence and Statistics, Mai Khao, Thailand, 2025, vol.
258, pp. 2539–2547.'
ista: 'Luo R, Stich SU, Horváth S, Takáč M. 2025. Revisiting LocalSGD and SCAFFOLD:
Improved rates and missing analysis. The 28th International Conference on Artificial
Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and
Statistics, PMLR, vol. 258, 2539–2547.'
mla: 'Luo, Ruichen, et al. “Revisiting LocalSGD and SCAFFOLD: Improved Rates and
Missing Analysis.” The 28th International Conference on Artificial Intelligence
and Statistics, vol. 258, ML Research Press, 2025, pp. 2539–47.'
short: R. Luo, S.U. Stich, S. Horváth, M. Takáč, in:, The 28th International Conference
on Artificial Intelligence and Statistics, ML Research Press, 2025, pp. 2539–2547.
conference:
end_date: 2025-05-05
location: Mai Khao, Thailand
name: 'AISTATS: Conference on Artificial Intelligence and Statistics'
start_date: 2025-05-03
date_created: 2025-09-07T22:01:35Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2026-09-16T07:01:32Z
day: '01'
department:
- _id: KrCh
ec_funded: 1
external_id:
arxiv:
- '2501.04443'
intvolume: ' 258'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2501.04443
month: '05'
oa: 1
oa_version: Preprint
page: 2539-2547
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: The 28th International Conference on Artificial Intelligence and Statistics
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 258
year: '2025'
...
---
APC_amount: 3599,50 EUR
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '20646'
abstract:
- lang: eng
text: Describing general quantum many-body dynamics is a challenging task due to
the exponential growth of the Hilbert space with system size. The time-dependent
variational principle (TDVP) provides a powerful tool to tackle this task by projecting
quantum evolution onto a classical dynamical system within a variational manifold.
In classical systems, periodic orbits play a crucial role in understanding the
structure of the phase space and the long-term behavior of the system. However,
finding periodic orbits is generally difficult, and their existence and properties
in generic TDVP dynamics over matrix product states have remained largely unexplored.
In this work, we develop an algorithm to systematically identify and characterize
periodic orbits in TDVP dynamics. Applying our method to the periodically kicked
Ising model, we uncover both stable and unstable periodic orbits. We characterize
the Kolmogorov-Arnold-Moser tori in the vicinity of stable periodic orbits and
track the change of the periodic orbits as we modify the Hamiltonian parameters.
We observe that periodic orbits exist at any value of the coupling constant of
the kicked Ising model between prethermal and fully thermalizing regimes, but
their relevance to quantum dynamics and imprint on quantum eigenstates diminishes
as the system leaves the prethermal regime. Our results demonstrate that periodic
orbits provide valuable insights into the TDVP approximation of quantum many-body
evolution and establish a closer connection between quantum and classical chaos.
acknowledgement: We acknowledge useful discussions with C. Kollath, A. Green, and
D. Huse. E.P., M.L., and M.S. acknowledge support by the European Research Council
under the European Union’s Horizon 2020 research and innovation program (Grant Agreement
No. 850899). This research was funded in whole or in part by the Austrian Science
Fund (FWF) (Grant No. 10.55776/COE1). For open access purposes, the author has applied
a CC BY public copyright license to any author accepted manuscript version arising
from this submission. M.L. acknowledges support by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) under Germany’s Excellence Strategy—EXC-2111—390814868.
This research was supported in part by National Science Foundation (NSF) Grant No.
PHY-2309135 to the Kavli Institute for Theoretical Physics (KITP) and by the Erwin
Schrödinger International Institute for Mathematics and Physics (ESI).
article_number: '040333'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Elena
full_name: Petrova, Elena
id: 0ac84990-897b-11ed-a09c-f5abb56a4ede
last_name: Petrova
- first_name: Marko
full_name: Ljubotina, Marko
id: F75EE9BE-5C90-11EA-905D-16643DDC885E
last_name: Ljubotina
orcid: 0000-0003-0038-7068
- first_name: Gökhan
full_name: Yalniz, Gökhan
id: 66E74FA2-D8BF-11E9-8249-8DE2E5697425
last_name: Yalniz
orcid: 0000-0002-8490-9312
- first_name: Maksym
full_name: Serbyn, Maksym
id: 47809E7E-F248-11E8-B48F-1D18A9856A87
last_name: Serbyn
orcid: 0000-0002-2399-5827
citation:
ama: Petrova E, Ljubotina M, Yalniz G, Serbyn M. Finding periodic orbits in projected
quantum many-body dynamics. PRX Quantum. 2025;6(4). doi:10.1103/tldp-kvkd
apa: Petrova, E., Ljubotina, M., Yalniz, G., & Serbyn, M. (2025). Finding periodic
orbits in projected quantum many-body dynamics. PRX Quantum. American Physical
Society. https://doi.org/10.1103/tldp-kvkd
chicago: Petrova, Elena, Marko Ljubotina, Gökhan Yalniz, and Maksym Serbyn. “Finding
Periodic Orbits in Projected Quantum Many-Body Dynamics.” PRX Quantum.
American Physical Society, 2025. https://doi.org/10.1103/tldp-kvkd.
ieee: E. Petrova, M. Ljubotina, G. Yalniz, and M. Serbyn, “Finding periodic orbits
in projected quantum many-body dynamics,” PRX Quantum, vol. 6, no. 4. American
Physical Society, 2025.
ista: Petrova E, Ljubotina M, Yalniz G, Serbyn M. 2025. Finding periodic orbits
in projected quantum many-body dynamics. PRX Quantum. 6(4), 040333.
mla: Petrova, Elena, et al. “Finding Periodic Orbits in Projected Quantum Many-Body
Dynamics.” PRX Quantum, vol. 6, no. 4, 040333, American Physical Society,
2025, doi:10.1103/tldp-kvkd.
short: E. Petrova, M. Ljubotina, G. Yalniz, M. Serbyn, PRX Quantum 6 (2025).
corr_author: '1'
date_created: 2025-11-14T09:40:52Z
date_published: 2025-11-12T00:00:00Z
date_updated: 2026-09-16T07:04:35Z
day: '12'
ddc:
- '539'
department:
- _id: GradSch
- _id: BjHo
- _id: MaSe
doi: 10.1103/tldp-kvkd
ec_funded: 1
external_id:
arxiv:
- '2504.12472'
isi:
- '001616473700003'
file:
- access_level: open_access
checksum: 5d6d04ac518b4118405334e1ddc7a56d
content_type: application/pdf
creator: gyalniz
date_created: 2025-11-14T09:44:10Z
date_updated: 2025-11-14T09:44:10Z
file_id: '20647'
file_name: tldp-kvkd.pdf
file_size: 2504713
relation: main_file
success: 1
file_date_updated: 2025-11-14T09:44:10Z
fulldoi: https://doi.org/10.1103/tldp-kvkd
has_accepted_license: '1'
intvolume: ' 6'
isi: 1
issue: '4'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 23841C26-32DE-11EA-91FC-C7463DDC885E
call_identifier: H2020
grant_number: '850899'
name: 'Non-Ergodic Quantum Matter: Universality, Dynamics and Control'
- _id: 3AC91DDA-15DF-11EA-824D-93A3E7B544D1
call_identifier: FWF
name: FWF Open Access Fund
- _id: 92c64506-16d5-11f0-9cad-87ce313ee832
grant_number: COE01
name: Quantum Science Austria (Serbyn)
publication: PRX Quantum
publication_identifier:
eissn:
- 2691-3399
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
related_material:
link:
- description: News on ISTA website
relation: press_release
url: https://ista.ac.at/en/news/reaching-for-the-quantum-scars/
scopus_import: '1'
status: public
title: Finding periodic orbits in projected quantum many-body dynamics
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: 6
year: '2025'
...
---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '20709'
abstract:
- lang: eng
text: Non-Hermitian many-body localization (NH MBL) has emerged as a possible scenario
for stable localization in open systems, as suggested by spectral indicators identifying
a putative transition for finite system sizes. In this work, we shift the focus
to dynamical probes, specifically the steady-state spin current, to investigate
transport properties in a disordered, non-Hermitian XXZ spin chain. Through exact
diagonalization for small systems and tensor-network methods for larger chains,
we demonstrate that the steady-state current remains finite and decays exponentially
with disorder strength, showing no evidence of a transition up to disorder values
far beyond the previously claimed critical point. Our results reveal a stark discrepancy
between spectral indicators, which suggest localization, and transport behavior,
which indicates delocalization. This highlights the importance of dynamical observables
in characterizing NH MBL and suggests that traditional spectral measures may not
fully capture the physics of non-Hermitian systems. Additionally, we observe a
noncommutativity of limits in system size and time, further complicating the interpretation
of finite-size studies. These findings challenge the existence of NH MBL in the
studied model and underscore the need for alternative approaches to understanding
localization in non-Hermitian settings.
acknowledgement: "F.B. thanks Giuseppe de Tomasi and Oskar A. Prośniak for discussion.
P.B. acknowledges support by the Austrian Science Fund (FWF) (Grant Agreement No.
10.55776/ESP9057324). This research was funded in whole or in part by the Austrian
Science Fund (FWF) [10.55776/COE1]. The numerical simulations were performed using
the ITensor library [73] on the Vienna Scientific Cluster (VSC) and on the MPIPKS
HPC cluster. M.L. acknowledges support by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under Germany’s Excellence Strategy—EXC-2111—390814868.
F.R. acknowledges support by the European Union-Next Generation EU with the project
“Quantum Optics in Many-Body photonic Environments” (QOMBE) code SOE2024_0000084-CUP
B77G24000480006. Open\r\naccess publication funded by Max Planck Society."
article_number: L042014
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Pietro
full_name: Brighi, Pietro
id: 4115AF5C-F248-11E8-B48F-1D18A9856A87
last_name: Brighi
orcid: 0000-0002-7969-2729
- first_name: Marko
full_name: Ljubotina, Marko
id: F75EE9BE-5C90-11EA-905D-16643DDC885E
last_name: Ljubotina
orcid: 0000-0003-0038-7068
- first_name: Federico
full_name: Roccati, Federico
last_name: Roccati
- first_name: Federico
full_name: Balducci, Federico
last_name: Balducci
citation:
ama: Brighi P, Ljubotina M, Roccati F, Balducci F. Finite steady-state current defies
non-Hermitian many-body localization. Physical Review Research. 2025;7(4).
doi:10.1103/crwj-x7j8
apa: Brighi, P., Ljubotina, M., Roccati, F., & Balducci, F. (2025). Finite steady-state
current defies non-Hermitian many-body localization. Physical Review Research.
American Physical Society. https://doi.org/10.1103/crwj-x7j8
chicago: Brighi, Pietro, Marko Ljubotina, Federico Roccati, and Federico Balducci.
“Finite Steady-State Current Defies Non-Hermitian Many-Body Localization.” Physical
Review Research. American Physical Society, 2025. https://doi.org/10.1103/crwj-x7j8.
ieee: P. Brighi, M. Ljubotina, F. Roccati, and F. Balducci, “Finite steady-state
current defies non-Hermitian many-body localization,” Physical Review Research,
vol. 7, no. 4. American Physical Society, 2025.
ista: Brighi P, Ljubotina M, Roccati F, Balducci F. 2025. Finite steady-state current
defies non-Hermitian many-body localization. Physical Review Research. 7(4), L042014.
mla: Brighi, Pietro, et al. “Finite Steady-State Current Defies Non-Hermitian Many-Body
Localization.” Physical Review Research, vol. 7, no. 4, L042014, American
Physical Society, 2025, doi:10.1103/crwj-x7j8.
short: P. Brighi, M. Ljubotina, F. Roccati, F. Balducci, Physical Review Research
7 (2025).
date_created: 2025-11-30T23:02:08Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2026-09-16T07:06:16Z
day: '01'
ddc:
- '530'
department:
- _id: MaSe
doi: 10.1103/crwj-x7j8
external_id:
arxiv:
- '2504.02460'
file:
- access_level: open_access
checksum: c4e582ab64ab9f8fface70bf2fd31882
content_type: application/pdf
creator: dernst
date_created: 2025-12-01T08:00:19Z
date_updated: 2025-12-01T08:00:19Z
file_id: '20715'
file_name: 2025_PhysReviewResearch_Brighi.pdf
file_size: 483879
relation: main_file
success: 1
file_date_updated: 2025-12-01T08:00:19Z
fulldoi: https://doi.org/10.1103/crwj-x7j8
has_accepted_license: '1'
intvolume: ' 7'
issue: '4'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 92c64506-16d5-11f0-9cad-87ce313ee832
grant_number: COE01
name: Quantum Science Austria (Serbyn)
publication: Physical Review Research
publication_identifier:
eissn:
- 2643-1564
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finite steady-state current defies non-Hermitian many-body localization
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: 7
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20648'
abstract:
- lang: eng
text: Polynomial quantified entailments with existentially and universally quantified
variables arise in many problems of verification and program analysis. We present
PolyQEnt which is a tool for solving polynomial quantified entailments in which
variables on both sides of the implication are real valued or unbounded integers.
Our tool provides a unified framework for polynomial quantified entailment problems
that arise in several papers in the literature. Our experimental evaluation over
a wide range of benchmarks shows the applicability of the tool as well as its
benefits as opposed to simply using existing SMT solvers to solve such constraints.
acknowledgement: 'This work was supported by the following grants: ERC CoG 863818
(ForM-SMArt), Austrian Science Fund (FWF) 10.55776/COE12, ERC StG 101222524 (SPES),
the Ethereum Foundation Research Grant FY24-1793, and the Singapore Ministry of
Education (MOE) Academic Research Fund (AcRF) Tier 1 grant (Project ID:22-SISSMU-100).'
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: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Ehsan
full_name: Kafshdar Goharshadi, Ehsan
id: 103b4fa0-896a-11ed-bdf8-87b697bef40d
last_name: Kafshdar Goharshadi
orcid: 0000-0002-8595-0587
- first_name: Mehrdad
full_name: Karrabi, Mehrdad
id: 67638922-f394-11eb-9cf6-f20423e08757
last_name: Karrabi
orcid: 0009-0007-5253-9170
- first_name: Milad
full_name: Saadat, Milad
last_name: Saadat
- first_name: Maximilian
full_name: Seeliger, Maximilian
last_name: Seeliger
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Chatterjee K, Goharshady AK, Goharshady E, et al. PolyQEnt: A polynomial quantified
entailment solver. In: 23rd International Symposium on Automated Technology
for Verification and Analysis. Vol 16145. Springer Nature; 2025:411-424. doi:10.1007/978-3-032-08707-2_19'
apa: 'Chatterjee, K., Goharshady, A. K., Goharshady, E., Karrabi, M., Saadat, M.,
Seeliger, M., & Zikelic, D. (2025). PolyQEnt: A polynomial quantified entailment
solver. In 23rd International Symposium on Automated Technology for Verification
and Analysis (Vol. 16145, pp. 411–424). Bengaluru, India: Springer Nature.
https://doi.org/10.1007/978-3-032-08707-2_19'
chicago: 'Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Ehsan Goharshady, Mehrdad
Karrabi, Milad Saadat, Maximilian Seeliger, and Dorde Zikelic. “PolyQEnt: A Polynomial
Quantified Entailment Solver.” In 23rd International Symposium on Automated
Technology for Verification and Analysis, 16145:411–24. Springer Nature, 2025.
https://doi.org/10.1007/978-3-032-08707-2_19.'
ieee: 'K. Chatterjee et al., “PolyQEnt: A polynomial quantified entailment
solver,” in 23rd International Symposium on Automated Technology for Verification
and Analysis, Bengaluru, India, 2025, vol. 16145, pp. 411–424.'
ista: 'Chatterjee K, Goharshady AK, Goharshady E, Karrabi M, Saadat M, Seeliger
M, Zikelic D. 2025. PolyQEnt: A polynomial quantified entailment solver. 23rd
International Symposium on Automated Technology for Verification and Analysis.
ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 16145, 411–424.'
mla: 'Chatterjee, Krishnendu, et al. “PolyQEnt: A Polynomial Quantified Entailment
Solver.” 23rd International Symposium on Automated Technology for Verification
and Analysis, vol. 16145, Springer Nature, 2025, pp. 411–24, doi:10.1007/978-3-032-08707-2_19.'
short: K. Chatterjee, A.K. Goharshady, E. Goharshady, M. Karrabi, M. Saadat, M.
Seeliger, D. Zikelic, in:, 23rd International Symposium on Automated Technology
for Verification and Analysis, Springer Nature, 2025, pp. 411–424.
conference:
end_date: 2025-10-31
location: Bengaluru, India
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2025-10-27
corr_author: '1'
date_created: 2025-11-16T23:01:24Z
date_published: 2025-10-26T00:00:00Z
date_updated: 2026-09-16T07:03:56Z
day: '26'
department:
- _id: KrCh
doi: 10.1007/978-3-032-08707-2_19
ec_funded: 1
external_id:
arxiv:
- '2408.03796'
fulldoi: https://doi.org/10.1007/978-3-032-08707-2_19
intvolume: ' 16145'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2408.03796
month: '10'
oa: 1
oa_version: Preprint
page: 411-424
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 23rd International Symposium on Automated Technology for Verification
and Analysis
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032087065'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'PolyQEnt: A polynomial quantified entailment solver'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16145
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20690'
abstract:
- lang: eng
text: 'Cumulative prospect theory (CPT) is the first theory for decision-making
under uncertainty that combines full theoretical soundness and empirically realistic
features [1], [Page 2]. While CPT was originally considered in one-shot settings
for risk-aware decision-making, we consider CPT in sequential decision-making.
The most fundamental and well-studied models for sequential decision-making are
Markov chains (MCs), and their generalization Markov decision processes (MDPs).
The complexity theoretic study of MCs and MDPs with CPT is a fundamental problem
that has not been addressed in the literature.Our contributions are as follows:
First, we present an alternative viewpoint for the CPT-value of MCs and MDPs.
This allows us to establish a connection with multi-objective reachability analysis
and conclude the strategy complexity result that memoryless randomized strategies
are necessary and sufficient for optimality. Second, based on this connection,
we provide an algorithm for computing the CPT-value in MDPs with infinite-horizon
objectives. We show that the problem is in EXPTIME and fixed-parameter tractable.
Moreover, we provide a polynomial-time algorithm for the special case of MCs.'
acknowledgement: "This project has received funding from the Fonds de la Recherche
Scientifique - FNRS under grant No. T.0027.21, the Belgian National Lottery; the
ERC CoG 863818 (ForM-SMArt), the Austrian Science Fund (FWF) 10.55776/COE12; the
DFG project 427755713, GOPro, and the DFG research training group GRK 2428 Continuous
Verification of Cyber-Physical Systems\r\n(ConVeY); the EU’s Horizon 2020 research
and innovation programmes under the Marie Sklodowska-Curie grant agreement No. 101034413
(IST-BRIDGE) and the ERC Starting Grant DEUCE (101077178)."
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas
full_name: Brihaye, Thomas
last_name: Brihaye
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Stefanie
full_name: Mohr, Stefanie
last_name: Mohr
- first_name: Maximilian
full_name: Weininger, Maximilian
id: 02ab0197-cc70-11ed-ab61-918e71f56881
last_name: Weininger
orcid: 0000-0002-0163-2152
citation:
ama: 'Brihaye T, Chatterjee K, Mohr S, Weininger M. Risk-aware Markov decision processes
using cumulative prospect theory. In: 2025 40th Annual ACM/IEEE Symposium on
Logic in Computer Science. IEEE; 2025:458-471. doi:10.1109/lics65433.2025.00041'
apa: 'Brihaye, T., Chatterjee, K., Mohr, S., & Weininger, M. (2025). Risk-aware
Markov decision processes using cumulative prospect theory. In 2025 40th Annual
ACM/IEEE Symposium on Logic in Computer Science (pp. 458–471). Singapore,
Singapore: IEEE. https://doi.org/10.1109/lics65433.2025.00041'
chicago: Brihaye, Thomas, Krishnendu Chatterjee, Stefanie Mohr, and Maximilian Weininger.
“Risk-Aware Markov Decision Processes Using Cumulative Prospect Theory.” In 2025
40th Annual ACM/IEEE Symposium on Logic in Computer Science, 458–71. IEEE,
2025. https://doi.org/10.1109/lics65433.2025.00041.
ieee: T. Brihaye, K. Chatterjee, S. Mohr, and M. Weininger, “Risk-aware Markov decision
processes using cumulative prospect theory,” in 2025 40th Annual ACM/IEEE Symposium
on Logic in Computer Science, Singapore, Singapore, 2025, pp. 458–471.
ista: 'Brihaye T, Chatterjee K, Mohr S, Weininger M. 2025. Risk-aware Markov decision
processes using cumulative prospect theory. 2025 40th Annual ACM/IEEE Symposium
on Logic in Computer Science. LICS: Logic in Computer Science, 458–471.'
mla: Brihaye, Thomas, et al. “Risk-Aware Markov Decision Processes Using Cumulative
Prospect Theory.” 2025 40th Annual ACM/IEEE Symposium on Logic in Computer
Science, IEEE, 2025, pp. 458–71, doi:10.1109/lics65433.2025.00041.
short: T. Brihaye, K. Chatterjee, S. Mohr, M. Weininger, in:, 2025 40th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2025, pp. 458–471.
conference:
end_date: 2025-06-26
location: Singapore, Singapore
name: 'LICS: Logic in Computer Science'
start_date: 2025-06-23
corr_author: '1'
date_created: 2025-11-24T14:43:47Z
date_published: 2025-10-09T00:00:00Z
date_updated: 2026-09-16T07:05:13Z
day: '09'
department:
- _id: KrCh
doi: 10.1109/lics65433.2025.00041
ec_funded: 1
external_id:
arxiv:
- '2505.09514'
fulldoi: https://doi.org/10.1109/lics65433.2025.00041
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.09514
month: '10'
oa: 1
oa_version: Preprint
page: 458-471
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
eisbn:
- '9798331579005'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Risk-aware Markov decision processes using cumulative prospect theory
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20689'
abstract:
- lang: eng
text: This paper studies the expected value of multiplicative rewards, where rewards
obtained in each step are multiplied (instead of the usual addition), in Markov
chains (MCs) and Markov decision processes (MDPs). One of the key differences
to additive rewards is that the expected value may diverge to ∞ not only due to
recurrent, but also due to transient states.For MCs, computing the value is shown
to be possible in polynomial time given an oracle for the comparison of succinctly
represented integers (CSRI), which is only known to be solvable in polynomial
time subject to number-theoretic conjectures. Interestingly, distinguishing whether
the value is ∞ or 0 is at least as hard as CSRI, while determining if it is one
of these two can be done in polynomial time. In MDPs, the optimal value can be
computed in polynomial space. Further refined complexity results and results on
the complexity of optimal schedulers are presented. The techniques developed for
MDPs additionally allow to solve the multiplicative variant of the stochastic
shortest path problem. Finally, for MCs and MDPs where an absorbing state is reached
almost surely, all considered problems are solvable in polynomial time.
acknowledgement: "This work was partly funded by the ERC CoG 863818 (ForM-SMArt),
the Austrian Science Fund (FWF) 10.55776/COE12, the DFG Grant 389792660 as part
of TRR 248 (Foundations of Perspicuous Software Systems), the Cluster of Excellence
EXC 2050/1 (CeTI, project ID\r\n390696704, as part of Germany’s Excellence Strategy),
and by the BMBF (Federal Ministry of Education and Research) in DAAD project 57616814
(SECAI, School of Embedded and\r\nComposite AI) as part of the program Konrad Zuse
Schools of Excellence in Artificial Intelligence."
article_processing_charge: No
arxiv: 1
author:
- first_name: Christel
full_name: Baier, Christel
last_name: Baier
- 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: Jakob
full_name: Piribauer, Jakob
last_name: Piribauer
citation:
ama: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Multiplicative rewards
in Markovian models. In: 2025 40th Annual ACM/IEEE Symposium on Logic in Computer
Science. IEEE; 2025:499-512. doi:10.1109/lics65433.2025.00044'
apa: 'Baier, C., Chatterjee, K., Meggendorfer, T., & Piribauer, J. (2025). Multiplicative
rewards in Markovian models. In 2025 40th Annual ACM/IEEE Symposium on Logic
in Computer Science (pp. 499–512). Singapore, Singapore: IEEE. https://doi.org/10.1109/lics65433.2025.00044'
chicago: Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob
Piribauer. “Multiplicative Rewards in Markovian Models.” In 2025 40th Annual
ACM/IEEE Symposium on Logic in Computer Science, 499–512. IEEE, 2025. https://doi.org/10.1109/lics65433.2025.00044.
ieee: C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Multiplicative
rewards in Markovian models,” in 2025 40th Annual ACM/IEEE Symposium on Logic
in Computer Science, Singapore, Singapore, 2025, pp. 499–512.
ista: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2025. Multiplicative
rewards in Markovian models. 2025 40th Annual ACM/IEEE Symposium on Logic in Computer
Science. LICS: Logic in Computer Science, 499–512.'
mla: Baier, Christel, et al. “Multiplicative Rewards in Markovian Models.” 2025
40th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2025, pp.
499–512, doi:10.1109/lics65433.2025.00044.
short: C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 2025 40th Annual
ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2025, pp. 499–512.
conference:
end_date: 2025-06-26
location: Singapore, Singapore
name: 'LICS: Logic in Computer Science'
start_date: 2025-06-23
corr_author: '1'
date_created: 2025-11-24T14:24:00Z
date_published: 2025-10-09T00:00:00Z
date_updated: 2026-09-16T07:05:41Z
day: '09'
department:
- _id: KrCh
doi: 10.1109/lics65433.2025.00044
ec_funded: 1
external_id:
arxiv:
- '2504.18277'
fulldoi: https://doi.org/10.1109/lics65433.2025.00044
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2504.18277
month: '10'
oa: 1
oa_version: Preprint
page: 499-512
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
eisbn:
- '9798331579005'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multiplicative rewards in Markovian models
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20817'
abstract:
- lang: eng
text: We present Mechanistic PDE Networks -- a model for discovery of governing
partial differential equations from data. Mechanistic PDE Networks represent spatiotemporal
data as space-time dependent linear partial differential equations in neural network
hidden representations. The represented PDEs are then solved and decoded for specific
tasks. The learned PDE representations naturally express the spatiotemporal dynamics
in data in neural network hidden space, enabling increased modeling power. Solving
the PDE representations in a compute and memory-efficient way, however, is a significant
challenge. We develop a native, GPU-capable, parallel, sparse and differentiable
multigrid solver specialized for linear partial differential equations that acts
as a module in Mechanistic PDE Networks. Leveraging the PDE solver we propose
a discovery architecture that can discovers nonlinear PDEs in complex settings,
while being robust to noise. We validate PDE discovery on a number of PDEs including
reaction-diffusion and Navier-Stokes equations.
acknowledgement: "AP. This project has received funding from the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
Grant Agreement No. 101034413.\r\nFL. This research was funded in whole or in part
by the Austrian Science Fund (FWF) 10.55776/COE12. For open access purposes, the
author has applied a CC BY public\r\ncopyright license to any author accepted manuscript
version arising from this submission."
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Adeel A
full_name: Pervez, Adeel A
id: fca6d90c-d47f-11ee-bc87-93ff51604981
last_name: Pervez
- first_name: Efstratios
full_name: Gavves, Efstratios
last_name: Gavves
- first_name: Francesco
full_name: Locatello, Francesco
id: 26cfd52f-2483-11ee-8040-88983bcc06d4
last_name: Locatello
orcid: 0000-0002-4850-0683
citation:
ama: 'Pervez AA, Gavves E, Locatello F. Mechanistic PDE networks for discovery of
governing equations. In: 42nd International Conference on Machine Learning.
Vol 267. ML Research Press; 2025:48962-48973.'
apa: 'Pervez, A. A., Gavves, E., & Locatello, F. (2025). Mechanistic PDE networks
for discovery of governing equations. In 42nd International Conference on Machine
Learning (Vol. 267, pp. 48962–48973). Vancouver, Canada: ML Research Press.'
chicago: Pervez, Adeel A, Efstratios Gavves, and Francesco Locatello. “Mechanistic
PDE Networks for Discovery of Governing Equations.” In 42nd International Conference
on Machine Learning, 267:48962–73. ML Research Press, 2025.
ieee: A. A. Pervez, E. Gavves, and F. Locatello, “Mechanistic PDE networks for discovery
of governing equations,” in 42nd International Conference on Machine Learning,
Vancouver, Canada, 2025, vol. 267, pp. 48962–48973.
ista: 'Pervez AA, Gavves E, Locatello F. 2025. Mechanistic PDE networks for discovery
of governing equations. 42nd International Conference on Machine Learning. ICML:
International Conference on Machine Learning, PMLR, vol. 267, 48962–48973.'
mla: Pervez, Adeel A., et al. “Mechanistic PDE Networks for Discovery of Governing
Equations.” 42nd International Conference on Machine Learning, vol. 267,
ML Research Press, 2025, pp. 48962–73.
short: A.A. Pervez, E. Gavves, F. Locatello, in:, 42nd International Conference
on Machine Learning, ML Research Press, 2025, pp. 48962–48973.
conference:
end_date: 2025-07-19
location: Vancouver, Canada
name: 'ICML: International Conference on Machine Learning'
start_date: 2025-07-13
corr_author: '1'
date_created: 2025-12-14T23:02:04Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2026-09-16T07:17:18Z
day: '01'
ddc:
- '000'
department:
- _id: FrLo
ec_funded: 1
external_id:
arxiv:
- '2502.18377'
file:
- access_level: open_access
checksum: 933cb673fb41416f537278fb990df6c3
content_type: application/pdf
creator: dernst
date_created: 2025-12-16T12:21:49Z
date_updated: 2025-12-16T12:21:49Z
file_id: '20827'
file_name: 2025_ICML_Pervez.pdf
file_size: 993381
relation: main_file
success: 1
file_date_updated: 2025-12-16T12:21:49Z
has_accepted_license: '1'
intvolume: ' 267'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 48962-48973
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: a392d8f0-b034-11f1-b88e-d3025c6734f6
grant_number: COE12
name: Bilateral Artificial Intelligence (Locatello)
publication: 42nd International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/ alpz/mech-nn-discovery-pde
scopus_import: '1'
status: public
title: Mechanistic PDE networks for discovery of governing equations
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: 267
year: '2025'
...
---
APC_amount: 3003,56 EUR
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-09-16T07:20:45Z
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
fulldoi: https://doi.org/10.1073/pnas.2524109122
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'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
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: '21320'
abstract:
- lang: eng
text: "Prophet inequalities are a central object of study in optimal stopping theory.
In the iid model, a gambler sees values in an online fashion, sampled independently
from a given distribution. Upon observing each value, the gambler either accepts
it as a reward, or irrevocably rejects it and proceeds to observe the next value.
The goal of the gambler, who cannot see the future, is to maximise the expected
value of the reward while competing against the expectation of a prophet (the
offline maximum). In other words, one seeks to maximise the gambler-to-prophet
ratio of the expectations. \r\nThis model has been studied with infinite, finite
and unknown number of values. When the gambler faces a random number of values,
the model is said to have a random horizon. We consider the model in which the
gambler is given a priori knowledge of the horizon’s distribution. Alijani et
al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when
the random horizon has an increasing hazard rate and is independent of the values.
We prove that with a single threshold, a ratio of 1/2 is actually achievable for
several larger classes of horizon distributions, with the largest being known
as the \U0001D4A2 class in reliability theory. Moreover, we show that this does
not extend to its dual, the ̅\U0001D4A2 class (which includes the decreasing
hazard rate class), while it can be extended to low-variance horizons. Finally,
we construct the first example of a family of horizons, for which multiple thresholds
are necessary to achieve a nonzero ratio. We establish that the Secretary Problem
optimal stopping rule provides one such algorithm, paving the way towards the
study of the model beyond single-threshold algorithms."
acknowledgement: 'We would like to thank José Correa for his precious advice, Bruno
Ziliotto and Vasilis Livanos for early conversations. Giambartolomei, Giordano:
EPSRC grants EP/W005573/1 and EP/X021696/1. Mallmann-Trenn, Frederik: EPSRC grant
EP/W005573/1. Saona, Raimundo: ERC grant CoG 863818 (ForM-SMArt), ANID Chile grant
ACT210005, French Agence Nationale de la Recherche (ANR) grant ANR-21-CE40-0020
(CONVERGENCE), and Austrian Science Fund (FWF) grant 10.55776/COE12.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Giordano
full_name: Giambartolomei, Giordano
last_name: Giambartolomei
- first_name: Frederik
full_name: Mallmann-Trenn, Frederik
last_name: Mallmann-Trenn
- 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: 'Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. IID prophet inequality
with random horizon: Going beyond increasing hazard rates. In: 52nd International
Colloquium on Automata, Languages, and Programming. Vol 334. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ICALP.2025.87'
apa: 'Giambartolomei, G., Mallmann-Trenn, F., & Saona Urmeneta, R. J. (2025).
IID prophet inequality with random horizon: Going beyond increasing hazard rates.
In 52nd International Colloquium on Automata, Languages, and Programming
(Vol. 334). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ICALP.2025.87'
chicago: 'Giambartolomei, Giordano, Frederik Mallmann-Trenn, and Raimundo J Saona
Urmeneta. “IID Prophet Inequality with Random Horizon: Going beyond Increasing
Hazard Rates.” In 52nd International Colloquium on Automata, Languages, and
Programming, Vol. 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.87.'
ieee: 'G. Giambartolomei, F. Mallmann-Trenn, and R. J. Saona Urmeneta, “IID prophet
inequality with random horizon: Going beyond increasing hazard rates,” in 52nd
International Colloquium on Automata, Languages, and Programming, Aarhus,
Denmark, 2025, vol. 334.'
ista: 'Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. 2025. IID prophet
inequality with random horizon: Going beyond increasing hazard rates. 52nd International
Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages
and Programming, LIPIcs, vol. 334.'
mla: 'Giambartolomei, Giordano, et al. “IID Prophet Inequality with Random Horizon:
Going beyond Increasing Hazard Rates.” 52nd International Colloquium on Automata,
Languages, and Programming, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2025, doi:10.4230/LIPIcs.ICALP.2025.87.'
short: G. Giambartolomei, F. Mallmann-Trenn, R.J. Saona Urmeneta, in:, 52nd International
Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025.
conference:
end_date: 2025-07-11
location: Aarhus, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2025-07-08
date_created: 2026-02-18T10:44:14Z
date_published: 2025-06-30T00:00:00Z
date_updated: 2026-09-16T07:25:05Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2025.87
ec_funded: 1
external_id:
arxiv:
- '2407.11752'
file:
- access_level: open_access
checksum: 960110956c26a5cefadde8e47888bfbe
content_type: application/pdf
creator: dernst
date_created: 2026-02-19T07:41:55Z
date_updated: 2026-02-19T07:41:55Z
file_id: '21331'
file_name: 2025_ICALP_Giambartolomei.pdf
file_size: 876167
relation: main_file
success: 1
file_date_updated: 2026-02-19T07:41:55Z
fulldoi: https://doi.org/10.4230/LIPIcs.ICALP.2025.87
has_accepted_license: '1'
intvolume: ' 334'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 52nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959773720'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: 'IID prophet inequality with random horizon: Going beyond increasing hazard
rates'
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: 334
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '21326'
abstract:
- lang: eng
text: 'Neural Collapse is a phenomenon where the last-layer representations of a
well-trained neural network converge to a highly structured geometry. In this
paper, we focus on its first (and most basic) property, known as NC1: the within-class
variability vanishes. While prior theoretical studies establish the occurrence
of NC1 via the data-agnostic unconstrained features model, our work adopts a data-specific
perspective, analyzing NC1 in a three-layer neural network, with the first two
layers operating in the mean-field regime and followed by a linear layer. In particular,
we establish a fundamental connection between NC1 and the loss landscape: we prove
that points with small empirical loss and gradient norm (thus, close to being
stationary) approximately satisfy NC1, and the closeness to NC1 is controlled
by the residual loss and gradient norm. We then show that (i) gradient flow on
the mean squared error converges to NC1 solutions with small empirical loss, and
(ii) for well-separated data distributions, both NC1 and vanishing test loss are
achieved simultaneously. This aligns with the empirical observation that NC1 emerges
during training while models attain near-zero test error. Overall, our results
demonstrate that NC1 arises from gradient training due to the properties of the
loss landscape, and they show the co-occurrence of NC1 and small test error for
certain data distributions.'
acknowledgement: "This research was funded in whole or in part by the Austrian Science
Fund (FWF) 10.55776/COE12. For the purpose of open access, the authors have applied
a CC BY public\r\ncopyright license to any Author Accepted Manuscript version arising
from this submission. The authors would like to thank Peter Sukenık for general
helpful discussions and for pointing out that all the stationary points are approximately
proportional in the case without entropic regularization. "
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Diyuan
full_name: Wu, Diyuan
id: 1a5914c2-896a-11ed-bdf8-fb80621a0635
last_name: Wu
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Wu D, Mondelli M. Neural collapse beyond the unconstrained features model:
Landscape, dynamics, and generalization in the mean-field regime. In: Proceedings
of the 42nd International Conference on Machine Learning. Vol 267. ML Research
Press; 2025:67499-67536.'
apa: 'Wu, D., & Mondelli, M. (2025). Neural collapse beyond the unconstrained
features model: Landscape, dynamics, and generalization in the mean-field regime.
In Proceedings of the 42nd International Conference on Machine Learning
(Vol. 267, pp. 67499–67536). Vancouver, Canada: ML Research Press.'
chicago: 'Wu, Diyuan, and Marco Mondelli. “Neural Collapse beyond the Unconstrained
Features Model: Landscape, Dynamics, and Generalization in the Mean-Field Regime.”
In Proceedings of the 42nd International Conference on Machine Learning,
267:67499–536. ML Research Press, 2025.'
ieee: 'D. Wu and M. Mondelli, “Neural collapse beyond the unconstrained features
model: Landscape, dynamics, and generalization in the mean-field regime,” in Proceedings
of the 42nd International Conference on Machine Learning, Vancouver, Canada,
2025, vol. 267, pp. 67499–67536.'
ista: 'Wu D, Mondelli M. 2025. Neural collapse beyond the unconstrained features
model: Landscape, dynamics, and generalization in the mean-field regime. Proceedings
of the 42nd International Conference on Machine Learning. ICML: International
Conference on Machine Learning, PMLR, vol. 267, 67499–67536.'
mla: 'Wu, Diyuan, and Marco Mondelli. “Neural Collapse beyond the Unconstrained
Features Model: Landscape, Dynamics, and Generalization in the Mean-Field Regime.”
Proceedings of the 42nd International Conference on Machine Learning, vol.
267, ML Research Press, 2025, pp. 67499–536.'
short: D. Wu, M. Mondelli, in:, Proceedings of the 42nd International Conference
on Machine Learning, ML Research Press, 2025, pp. 67499–67536.
conference:
end_date: 2025-07-19
location: Vancouver, Canada
name: 'ICML: International Conference on Machine Learning'
start_date: 2025-07-13
corr_author: '1'
date_created: 2026-02-18T12:02:45Z
date_published: 2025-07-30T00:00:00Z
date_updated: 2026-09-16T07:25:42Z
day: '30'
ddc:
- '000'
department:
- _id: MaMo
external_id:
arxiv:
- '2501.19104'
file:
- access_level: open_access
checksum: c5ce8b1c83e33dc3a11122f4910deb67
content_type: application/pdf
creator: dernst
date_created: 2026-02-19T08:28:22Z
date_updated: 2026-02-19T08:28:22Z
file_id: '21337'
file_name: 2025_ICML_Wu.pdf
file_size: 3994385
relation: main_file
success: 1
file_date_updated: 2026-02-19T08:28:22Z
has_accepted_license: '1'
intvolume: ' 267'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 67499-67536
project:
- _id: 74caaef7-b034-11f1-8f2d-e0e993bb422e
grant_number: COE12
name: Bilateral Artificial Intelligence (Mondelli)
publication: Proceedings of the 42nd International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: 'Neural collapse beyond the unconstrained features model: Landscape, dynamics,
and generalization in the mean-field regime'
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: 267
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '21268'
abstract:
- lang: eng
text: "We consider multiple-environment Markov decision processes (MEMDP), which
consist of a finite set of MDPs over the same state space, representing different
scenarios of transition structure and probability. The value of a strategy is
the probability to satisfy the objective, here a parity objective, in the worst-case
scenario, and the value of an MEMDP is the supremum of the values achievable by
a strategy.\r\nWe show that deciding whether the value is 1 is a PSPACE-complete
problem, and even in P when the number of environments is fixed, along with new
insights to the almost-sure winning problem, which is to decide if there exists
a strategy with value 1. Pure strategies are sufficient for theses problems, whereas
randomization is necessary in general when the value is smaller than 1. We present
an algorithm to approximate the value, running in double exponential space. Our
results are in contrast to the related model of partially-observable MDPs where
all these problems are known to be undecidable."
acknowledgement: "Krishnendu Chatterjee: ERC CoG 863818 (ForM-SMArt) and Austrian
Science Fund\r\n(FWF) 10.55776/COE12. Jean-François Raskin: PDR Weave project FORM-LEARN-POMDP
funded by FNRS and DFG, and the support of the Fondation ULB. Ocan Sankur: ANR BisoUS
(ANR-22-CE48-0012) and ANR EpiRL (ANR-22-CE23-0029)."
alternative_title:
- LIPIcs
article_number: '150'
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Jean-Francois
full_name: Raskin, Jean-Francois
last_name: Raskin
- first_name: Ocan
full_name: Sankur, Ocan
last_name: Sankur
citation:
ama: 'Chatterjee K, Doyen L, Raskin J-F, Sankur O. The value problem for multiple-environment
MDPs with parity objective. In: 52nd International Colloquium on Automata,
Languages, and Programming. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2025. doi:10.4230/LIPIcs.ICALP.2025.150'
apa: 'Chatterjee, K., Doyen, L., Raskin, J.-F., & Sankur, O. (2025). The value
problem for multiple-environment MDPs with parity objective. In 52nd International
Colloquium on Automata, Languages, and Programming. Aarhus, Denmark: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2025.150'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Jean-Francois Raskin, and Ocan Sankur.
“The Value Problem for Multiple-Environment MDPs with Parity Objective.” In 52nd
International Colloquium on Automata, Languages, and Programming. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.150.
ieee: K. Chatterjee, L. Doyen, J.-F. Raskin, and O. Sankur, “The value problem for
multiple-environment MDPs with parity objective,” in 52nd International Colloquium
on Automata, Languages, and Programming, Aarhus, Denmark, 2025.
ista: 'Chatterjee K, Doyen L, Raskin J-F, Sankur O. 2025. The value problem for
multiple-environment MDPs with parity objective. 52nd International Colloquium
on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming,
LIPIcs, , 150.'
mla: Chatterjee, Krishnendu, et al. “The Value Problem for Multiple-Environment
MDPs with Parity Objective.” 52nd International Colloquium on Automata, Languages,
and Programming, 150, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025,
doi:10.4230/LIPIcs.ICALP.2025.150.
short: K. Chatterjee, L. Doyen, J.-F. Raskin, O. Sankur, in:, 52nd International
Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025.
conference:
end_date: 2025-07-11
location: Aarhus, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2025-07-08
corr_author: '1'
date_created: 2026-02-17T07:49:17Z
date_published: 2025-07-30T00:00:00Z
date_updated: 2026-09-16T07:23:50Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2025.150
ec_funded: 1
external_id:
arxiv:
- '2504.15960'
file:
- access_level: open_access
checksum: 4477a7fd4fbf0ba6c8e9b15683b5a6b8
content_type: application/pdf
creator: dernst
date_created: 2026-02-18T07:50:56Z
date_updated: 2026-02-18T07:50:56Z
file_id: '21313'
file_name: 2025_LIPIcs_Chatterjee.pdf
file_size: 1075724
relation: main_file
success: 1
file_date_updated: 2026-02-18T07:50:56Z
fulldoi: https://doi.org/10.4230/LIPIcs.ICALP.2025.150
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 52nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959773720'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The value problem for multiple-environment MDPs with parity objective
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'
...
---
OA_place: publisher
OA_type: gold
_id: '21412'
abstract:
- lang: eng
text: "Payment channel networks (PCNs) are a promising technology that alleviates
blockchain scalability by shifting the transaction load from the blockchain to
the PCN. Nevertheless, the network topology has to be carefully designed to maximise
the transaction throughput in PCNs. Additionally, users in PCNs also have to make
optimal decisions on which transactions to forward and which to reject to prolong
the lifetime of their channels. In this work, we consider an input sequence of
transactions over p parties. Each transaction consists of a transaction size,
source, and target, and can be either accepted or rejected (entailing a cost).
The goal is to design a PCN topology among the p cooperating parties, along with
the channel capacities, and then output a decision for each transaction in the
sequence to minimise the cost of creating and augmenting channels, as well as
the cost of rejecting transactions. Our main contribution is an \U0001D4AA(p)
approximation algorithm for the problem with p parties. We further show that with
some assumptions on the distribution of transactions, we can reduce the approximation
ratio to \U0001D4AA(√p). We complement our theoretical analysis with an empirical
study of our assumptions and approach in the context of the Lightning Network."
acknowledgement: "Chatterjee, Krishnendu: European Research Council CoG 863818 (ForM-SMArt)
and Austrian Science Fund 10.55776/COE12.\r\nKřišťan, Jan Matyáš: Czech Science
Foundation Grant no. 24-12046S.\r\nSchmid, Stefan: German Research Foundation (DFG)
project ReNO (SPP 2378) from 2023-2027.\r\nSvoboda, Jakub: European Research Council
CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.\r\nYeo, Michelle:
MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms)."
alternative_title:
- LIPIcs
article_number: '23'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Jan Matyáš
full_name: Křišťan, Jan Matyáš
last_name: Křišťan
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. Boosting payment channel
network liquidity with topology optimization and transaction selection. In: 39th
International Symposium on Distributed Computing. Vol 356. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.DISC.2025.23'
apa: 'Chatterjee, K., Křišťan, J. M., Schmid, S., Svoboda, J., & Yeo, M. X.
(2025). Boosting payment channel network liquidity with topology optimization
and transaction selection. In 39th International Symposium on Distributed Computing
(Vol. 356). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.DISC.2025.23'
chicago: Chatterjee, Krishnendu, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda,
and Michelle X Yeo. “Boosting Payment Channel Network Liquidity with Topology
Optimization and Transaction Selection.” In 39th International Symposium on
Distributed Computing, Vol. 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.DISC.2025.23.
ieee: K. Chatterjee, J. M. Křišťan, S. Schmid, J. Svoboda, and M. X. Yeo, “Boosting
payment channel network liquidity with topology optimization and transaction selection,”
in 39th International Symposium on Distributed Computing, Berlin, Germany,
2025, vol. 356.
ista: 'Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. 2025. Boosting payment
channel network liquidity with topology optimization and transaction selection.
39th International Symposium on Distributed Computing. DISC: Symposium on Distributed
Computing, LIPIcs, vol. 356, 23.'
mla: Chatterjee, Krishnendu, et al. “Boosting Payment Channel Network Liquidity
with Topology Optimization and Transaction Selection.” 39th International Symposium
on Distributed Computing, vol. 356, 23, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, doi:10.4230/LIPIcs.DISC.2025.23.
short: K. Chatterjee, J.M. Křišťan, S. Schmid, J. Svoboda, M.X. Yeo, in:, 39th International
Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025.
conference:
end_date: 2025-10-31
location: Berlin, Germany
name: 'DISC: Symposium on Distributed Computing'
start_date: 2025-10-27
cryptoeprintid: 1
date_created: 2026-03-08T23:01:46Z
date_published: 2025-10-22T00:00:00Z
date_updated: 2026-09-16T07:27:09Z
day: '22'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.DISC.2025.23
ec_funded: 1
external_id:
arxiv:
- '2508.14524'
cryptoeprintid:
- 2025/1484
file:
- access_level: open_access
checksum: 8e3d1594365df60163d9df22158a37b1
content_type: application/pdf
creator: dernst
date_created: 2026-03-09T11:51:59Z
date_updated: 2026-03-09T11:51:59Z
file_id: '21418'
file_name: 2025_DISC_Chatterjee.pdf
file_size: 1130069
relation: main_file
success: 1
file_date_updated: 2026-03-09T11:51:59Z
fulldoi: https://doi.org/10.4230/LIPIcs.DISC.2025.23
has_accepted_license: '1'
intvolume: ' 356'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 39th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959774024'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Boosting payment channel network liquidity with topology optimization and transaction
selection
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 356
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20819'
abstract:
- lang: eng
text: "Clustering is a cornerstone of data analysis that is particularly suited
to identifying coherent subgroups or substructures in unlabeled data, as are generated
continuously in large amounts these days. However, in many cases traditional clustering
methods are not applicable, because data are increasingly being produced and stored
in a distributed way, e.g. on edge devices, and privacy concerns prevent it from
being transferred to a central server. To address this challenge, we present FedDP-KMeans,
a new algorithm for \r\n-means clustering that is fully-federated as well as differentially
private. Our approach leverages (potentially small and out-of-distribution) server-side
data to overcome the primary challenge of differentially private clustering methods:
the need for a good initialization. Combining our initialization with a simple
federated DP-Lloyds algorithm we obtain an algorithm that achieves excellent results
on synthetic and real-world benchmark tasks. We also provide a theoretical analysis
of our method that provides bounds on the convergence speed and cluster identification
success."
acknowledged_ssus:
- _id: ScienComp
acknowledgement: "This research was funded in part by the Austrian Science Fund (FWF)
[10.55776/COE12] and supported by the Scientific Service Units (SSU) of ISTA through
resources provided by Scientific Computing (SciComp).\r\n"
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Jonathan A
full_name: Scott, Jonathan A
id: e499926b-f6e0-11ea-865d-9c63db0031e8
last_name: Scott
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
- first_name: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
citation:
ama: 'Scott JA, Lampert C, Saulpic D. Differentially private federated k-means clustering
with server-side data. In: 42nd International Conference on Machine Learning.
Vol 267. ML Research Press; 2025:53757-53790.'
apa: 'Scott, J. A., Lampert, C., & Saulpic, D. (2025). Differentially private
federated k-means clustering with server-side data. In 42nd International Conference
on Machine Learning (Vol. 267, pp. 53757–53790). Vancouver, Canada: ML Research
Press.'
chicago: Scott, Jonathan A, Christoph Lampert, and David Saulpic. “Differentially
Private Federated K-Means Clustering with Server-Side Data.” In 42nd International
Conference on Machine Learning, 267:53757–90. ML Research Press, 2025.
ieee: J. A. Scott, C. Lampert, and D. Saulpic, “Differentially private federated
k-means clustering with server-side data,” in 42nd International Conference
on Machine Learning, Vancouver, Canada, 2025, vol. 267, pp. 53757–53790.
ista: 'Scott JA, Lampert C, Saulpic D. 2025. Differentially private federated k-means
clustering with server-side data. 42nd International Conference on Machine Learning.
ICML: International Conference on Machine Learning, PMLR, vol. 267, 53757–53790.'
mla: Scott, Jonathan A., et al. “Differentially Private Federated K-Means Clustering
with Server-Side Data.” 42nd International Conference on Machine Learning,
vol. 267, ML Research Press, 2025, pp. 53757–90.
short: J.A. Scott, C. Lampert, D. Saulpic, in:, 42nd International Conference on
Machine Learning, ML Research Press, 2025, pp. 53757–53790.
conference:
end_date: 2025-07-19
location: Vancouver, Canada
name: 'ICML: International Conference on Machine Learning'
start_date: 2025-07-13
corr_author: '1'
date_created: 2025-12-14T23:02:05Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2026-09-16T07:26:12Z
day: '01'
ddc:
- '000'
department:
- _id: ChLa
- _id: MoHe
external_id:
arxiv:
- '2506.05408'
file:
- access_level: open_access
checksum: 815b32b463023ca21e569c2158745c15
content_type: application/pdf
creator: dernst
date_created: 2025-12-16T12:38:29Z
date_updated: 2025-12-16T12:38:29Z
file_id: '20829'
file_name: 2025_ICML_Scott.pdf
file_size: 746612
relation: main_file
success: 1
file_date_updated: 2025-12-16T12:38:29Z
has_accepted_license: '1'
intvolume: ' 267'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 53757-53790
project:
- _id: d8f03aaa-b035-11f1-8588-d5147fa879e0
grant_number: COE12
name: Bilateral Artificial Intelligence (Lampert)
publication: 42nd International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '21198'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Differentially private federated k-means clustering with server-side data
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: 267
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21207'
abstract:
- lang: eng
text: Personalized federated learning has emerged as a popular approach to training
on devices holding statistically heterogeneous data, known as clients. However,
most existing approaches require a client to have labeled data for training or
finetuning in order to obtain their own personalized model. In this paper we address
this by proposing FLowDUP, a novel method that is able to generate a personalized
model using only a forward pass with unlabeled data. The generated model parameters
reside in a low-dimensional subspace, enabling efficient communication and computation.
FLowDUP's learning objective is theoretically motivated by our new transductive
multi-task PAC-Bayesian generalization bound, that provides performance guarantees
for unlabeled clients. The objective is structured in such a way that it allows
both clients with labeled data and clients with only unlabeled data to contribute
to the training process. To supplement our theoretical results we carry out a
thorough experimental evaluation of FLowDUP, demonstrating strong empirical performance
on a range of datasets with differing sorts of statistically heterogeneous clients.
Through numerous ablation studies, we test the efficacy of the individual components
of the method.
article_number: '2505.15579'
article_processing_charge: No
author:
- first_name: Hossein
full_name: Zakerinia, Hossein
id: 653bd8b6-f394-11eb-9cf6-c0bbf6cd78d4
last_name: Zakerinia
orcid: 0009-0007-3977-6462
- first_name: Jonathan A
full_name: Scott, Jonathan A
id: e499926b-f6e0-11ea-865d-9c63db0031e8
last_name: Scott
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Zakerinia H, Scott JA, Lampert C. Federated learning with unlabeled clients:
Personalization can happen in low dimensions. arXiv. doi:10.48550/ARXIV.2505.15579'
apa: 'Zakerinia, H., Scott, J. A., & Lampert, C. (n.d.). Federated learning
with unlabeled clients: Personalization can happen in low dimensions. arXiv.
https://doi.org/10.48550/ARXIV.2505.15579'
chicago: 'Zakerinia, Hossein, Jonathan A Scott, and Christoph Lampert. “Federated
Learning with Unlabeled Clients: Personalization Can Happen in Low Dimensions.”
ArXiv, n.d. https://doi.org/10.48550/ARXIV.2505.15579.'
ieee: 'H. Zakerinia, J. A. Scott, and C. Lampert, “Federated learning with unlabeled
clients: Personalization can happen in low dimensions,” arXiv. .'
ista: 'Zakerinia H, Scott JA, Lampert C. Federated learning with unlabeled clients:
Personalization can happen in low dimensions. arXiv, 2505.15579.'
mla: 'Zakerinia, Hossein, et al. “Federated Learning with Unlabeled Clients: Personalization
Can Happen in Low Dimensions.” ArXiv, 2505.15579, doi:10.48550/ARXIV.2505.15579.'
short: H. Zakerinia, J.A. Scott, C. Lampert, ArXiv (n.d.).
corr_author: '1'
das_tickbox: '1'
date_created: 2026-02-10T08:20:59Z
date_published: 2025-05-21T00:00:00Z
date_updated: 2026-09-16T07:26:12Z
day: '21'
department:
- _id: ChLa
doi: 10.48550/ARXIV.2505.15579
fulldoi: https://doi.org/10.48550/ARXIV.2505.15579
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.15579
month: '05'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: draft
related_material:
record:
- id: '21198'
relation: dissertation_contains
status: public
status: public
title: 'Federated learning with unlabeled clients: Personalization can happen in low
dimensions'
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: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: free access
_id: '22828'
abstract:
- lang: eng
text: 'We propose Joint Moment Estimation (JME), a method for continually and privately
estimating both the first and second moments of a data stream with reduced noise
compared to naive approaches. JME supports the matrix mechanism and exploits a
joint sensitivity analysis to identify a privacy regime in which the second-moment
estimation incurs no additional privacy cost, thereby improving accuracy while
maintaining privacy. We demonstrate JME’s effectiveness in two applications: estimating
the running mean and covariance matrix for Gaussian density estimation and model
training with DP-Adam.'
acknowledgement: "We thank Monika Henzinger for her valuable feedback and insightful
discussions on earlier versions\r\nof this draft. We are also grateful to Mher Safaryan
for his contributions to discussions on DP-Adam.\r\nAdditionally, we thank Ryan
McKenna for suggesting Joint Clipping as a baseline.\r\nJalaj Upadhyay’s research
was funded by the Rutgers Decanal Grant no. 302918, NSF CNS 2433628,\r\nGoogle Research
Scholar Award, and Google Seed Fund Grant. A part of this work was done while\r\nvisiting
the Institute of Science and Technology Austria (ISTA).\r\nNikita Kalinin’s research
was funded in part by the Austrian Science Fund (FWF) [10.55776/COE12]"
alternative_title:
- Advances in Neural Information Processing Systems
article_processing_charge: No
author:
- first_name: Nikita
full_name: Kalinin, Nikita
id: 4b14526e-14d2-11ed-ba64-c14c9553d137
last_name: Kalinin
- first_name: Jalaj
full_name: Upadhyay, Jalaj
last_name: Upadhyay
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Kalinin N, Upadhyay J, Lampert C. Continual release moment estimation with
differential privacy. In: Advances in Neural Information Processing Systems.
Vol 38. Neural Information Processing Systems Foundation; 2025:64002-64047. doi:10.52202/085713-1924'
apa: 'Kalinin, N., Upadhyay, J., & Lampert, C. (2025). Continual release moment
estimation with differential privacy. In Advances in Neural Information Processing
Systems (Vol. 38, pp. 64002–64047). San Diego, CA, United States: Neural Information
Processing Systems Foundation. https://doi.org/10.52202/085713-1924'
chicago: Kalinin, Nikita, Jalaj Upadhyay, and Christoph Lampert. “Continual Release
Moment Estimation with Differential Privacy.” In Advances in Neural Information
Processing Systems, 38:64002–47. Neural Information Processing Systems Foundation,
2025. https://doi.org/10.52202/085713-1924.
ieee: N. Kalinin, J. Upadhyay, and C. Lampert, “Continual release moment estimation
with differential privacy,” in Advances in Neural Information Processing Systems,
San Diego, CA, United States, 2025, vol. 38, pp. 64002–64047.
ista: 'Kalinin N, Upadhyay J, Lampert C. 2025. Continual release moment estimation
with differential privacy. Advances in Neural Information Processing Systems.
NeurIPS: Neural Information Processing Systems, Advances in Neural Information
Processing Systems, vol. 38, 64002–64047.'
mla: Kalinin, Nikita, et al. “Continual Release Moment Estimation with Differential
Privacy.” Advances in Neural Information Processing Systems, vol. 38, Neural
Information Processing Systems Foundation, 2025, pp. 64002–47, doi:10.52202/085713-1924.
short: N. Kalinin, J. Upadhyay, C. Lampert, in:, Advances in Neural Information
Processing Systems, Neural Information Processing Systems Foundation, 2025, pp.
64002–64047.
conference:
location: San Diego, CA, United States
name: 'NeurIPS: Neural Information Processing Systems'
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-06T22:02:00Z
date_published: 2025-12-02T00:00:00Z
date_updated: 2026-09-16T07:40:56Z
day: '02'
department:
- _id: GradSch
- _id: ChLa
doi: 10.52202/085713-1924
fulldoi: https://doi.org/10.52202/085713-1924
intvolume: ' 38'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.52202/085713-1924
month: '12'
oa: 1
oa_version: Published Version
page: 64002-64047
project:
- _id: d8f03aaa-b035-11f1-8588-d5147fa879e0
grant_number: COE12
name: Bilateral Artificial Intelligence (Lampert)
publication: Advances in Neural Information Processing Systems
publication_identifier:
isbn:
- '9798331338275'
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Continual release moment estimation with differential privacy
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 38
year: '2025'
...
---
OA_place: publisher
OA_type: diamond
_id: '19841'
abstract:
- lang: eng
text: "Context. The blue supergiant (BSG) domain contains a large variety of stars
whose past and future evolutionary paths are still highly uncertain. Since binary
interaction plays a crucial role in the fate of massive stars, investigating the
multiplicity among BSGs helps shed light on the fate of such objects.\r\nAims.
We aim to estimate the binary fraction of a large sample of BSGs in the Small
Magellanic Cloud (SMC) within the Binarity at LOw Metallicity (BLOeM) survey.
In total, we selected 262 targets with spectral types B0-B3 and luminosity classes
I-II.\r\n\r\nMethods. This work is based on spectroscopic data collected by the
FLAMES instrument, mounted on the Very Large Telescope, which gathered nine epochs
over three months. Our spectroscopic analysis for each target includes the individual
and peak-to-peak radial velocity measurements, an investigation of the line profile
variability, and a periodogram analysis to search for possible short- and long-period
binaries.\r\n\r\nResults. By applying a 20 km s−1 threshold on the peak-to-peak
radial velocities above which we would consider the star to be binary, the resulting
observed spectroscopic binary fraction for our BSG sample is 23 ± 3%. An independent
analysis of line profile variability reveals 11 (plus 5 candidates) double-lined
spectroscopic binaries and 32 (plus 41 candidates) single-lined spectroscopic
binaries. Based on these results, we estimated the overall observed binary fraction
in this sample to be 34 ± 3%, which is close to the computed intrinsic binary
fraction of 40 ± 4%. In addition, we derived reliable orbital periods for 41 spectroscopic
binaries and potential binary candidates, among which there are 17 eclipsing binaries,
including 20 SB1 and SB2 systems with periods of less than 10 days. We reported
a significant drop in the binary fraction of BSGs with spectral types later than
B2 and effective temperatures less than 18 kK, which could indicate the end of
the main sequence phase in this temperature regime. We found no metallicity dependence
in the binary fraction of BSGs, compared to existing spectroscopic surveys of
the Galaxy and Large Magellanic Cloud."
acknowledgement: 'We thank the anonymous referee for helpful comments that have improved
the manuscript. This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement 101164755/METAL) and was supported by the Israel Science Foundation
(ISF) under grant number 2434/24. NB acknowledges support from the Belgian federal
government grant for Ukrainian postdoctoral researchers (contract UF/2022/10). TS
acknowledges support by the Israel Science Foundation (ISF) under grant number 0603225041.
DP acknowledges financial support from the Deutsches Zentrum für Luft und Raumfahrt
(DLR) grant FKZ 50OR2005 and the FWO junior postdoctoral fellowship No. 1256225N.
DMB gratefully acknowledges UK Research and Innovation (UKRI) in the form of a Frontier
Research grant under the UK government’s ERC Horizon Europe funding guarantee (SYMPHONY;
PI Bowman; grant number: EP/Y031059/1), and a Royal Society University Research
Fellowship (PI Bowman; grant number: URF\R1\231631). KS is funded by the National
Science Center (NCN), Poland, under grant number OPUS 2021/41/B/ST9/00757. IM acknowledges
support from the Australian Research Council (ARC) Centre of Excellence for Gravitational
Wave Discovery (OzGav), through project number CE230100016. JIV acknowledges support
from the European Research Council through ERC Advanced Grant No. 101054731. SS-D,
and GH acknowledge support from the Spanish Ministry of Science and Innovation and
Universities (MICIU) through the Spanish State Research Agency (AEI) through grants
PID2021-122397NB-C21, and the Severo Ochoa Program 2020-2023 (CEX2019-000920-S).'
article_number: A40
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: N.
full_name: Britavskiy, N.
last_name: Britavskiy
- first_name: L.
full_name: Mahy, L.
last_name: Mahy
- first_name: D. J.
full_name: Lennon, D. J.
last_name: Lennon
- first_name: L. R.
full_name: Patrick, L. R.
last_name: Patrick
- first_name: H.
full_name: Sana, H.
last_name: Sana
- first_name: J. I.
full_name: Villaseñor, J. I.
last_name: Villaseñor
- first_name: T.
full_name: Shenar, T.
last_name: Shenar
- first_name: J.
full_name: Bodensteiner, J.
last_name: Bodensteiner
- first_name: M.
full_name: Bernini-Peron, M.
last_name: Bernini-Peron
- first_name: S. R.
full_name: Berlanas, S. R.
last_name: Berlanas
- first_name: D. M.
full_name: Bowman, D. M.
last_name: Bowman
- first_name: P. A.
full_name: Crowther, P. A.
last_name: Crowther
- first_name: S. E.
full_name: De Mink, S. E.
last_name: De Mink
- first_name: C. J.
full_name: Evans, C. J.
last_name: Evans
- first_name: Ylva Louise Linsdotter
full_name: Götberg, Ylva Louise Linsdotter
id: d0648d0c-0f64-11ee-a2e0-dd0faa2e4f7d
last_name: Götberg
orcid: 0000-0002-6960-6911
- first_name: G.
full_name: Holgado, G.
last_name: Holgado
- first_name: C.
full_name: Johnston, C.
last_name: Johnston
- first_name: Z.
full_name: Keszthelyi, Z.
last_name: Keszthelyi
- first_name: J.
full_name: Klencki, J.
last_name: Klencki
- first_name: N.
full_name: Langer, N.
last_name: Langer
- first_name: I.
full_name: Mandel, I.
last_name: Mandel
- first_name: A.
full_name: Menon, A.
last_name: Menon
- first_name: M.
full_name: Moe, M.
last_name: Moe
- first_name: L. M.
full_name: Oskinova, L. M.
last_name: Oskinova
- first_name: D.
full_name: Pauli, D.
last_name: Pauli
- first_name: M.
full_name: Pawlak, M.
last_name: Pawlak
- first_name: V.
full_name: Ramachandran, V.
last_name: Ramachandran
- first_name: M.
full_name: Renzo, M.
last_name: Renzo
- first_name: A. A.C.
full_name: Sander, A. A.C.
last_name: Sander
- first_name: F. R.N.
full_name: Schneider, F. R.N.
last_name: Schneider
- first_name: A.
full_name: Schootemeijer, A.
last_name: Schootemeijer
- first_name: K.
full_name: Sen, K.
last_name: Sen
- first_name: S.
full_name: Simón-Díaz, S.
last_name: Simón-Díaz
- first_name: J. T.
full_name: Van Loon, J. T.
last_name: Van Loon
- first_name: J. S.
full_name: Vink, J. S.
last_name: Vink
citation:
ama: 'Britavskiy N, Mahy L, Lennon DJ, et al. Binarity at LOw Metallicity (BLOeM):
Multiplicity of early B-type supergiants in the Small Magellanic Cloud. Astronomy
& Astrophysics. 2025;698. doi:10.1051/0004-6361/202452963'
apa: 'Britavskiy, N., Mahy, L., Lennon, D. J., Patrick, L. R., Sana, H., Villaseñor,
J. I., … Vink, J. S. (2025). Binarity at LOw Metallicity (BLOeM): Multiplicity
of early B-type supergiants in the Small Magellanic Cloud. Astronomy &
Astrophysics. EDP Sciences. https://doi.org/10.1051/0004-6361/202452963'
chicago: 'Britavskiy, N., L. Mahy, D. J. Lennon, L. R. Patrick, H. Sana, J. I. Villaseñor,
T. Shenar, et al. “Binarity at LOw Metallicity (BLOeM): Multiplicity of Early
B-Type Supergiants in the Small Magellanic Cloud.” Astronomy & Astrophysics.
EDP Sciences, 2025. https://doi.org/10.1051/0004-6361/202452963.'
ieee: 'N. Britavskiy et al., “Binarity at LOw Metallicity (BLOeM): Multiplicity
of early B-type supergiants in the Small Magellanic Cloud,” Astronomy &
Astrophysics, vol. 698. EDP Sciences, 2025.'
ista: 'Britavskiy N, Mahy L, Lennon DJ, Patrick LR, Sana H, Villaseñor JI, Shenar
T, Bodensteiner J, Bernini-Peron M, Berlanas SR, Bowman DM, Crowther PA, De Mink
SE, Evans CJ, Götberg YLL, Holgado G, Johnston C, Keszthelyi Z, Klencki J, Langer
N, Mandel I, Menon A, Moe M, Oskinova LM, Pauli D, Pawlak M, Ramachandran V, Renzo
M, Sander AAC, Schneider FRN, Schootemeijer A, Sen K, Simón-Díaz S, Van Loon JT,
Vink JS. 2025. Binarity at LOw Metallicity (BLOeM): Multiplicity of early B-type
supergiants in the Small Magellanic Cloud. Astronomy & Astrophysics. 698,
A40.'
mla: 'Britavskiy, N., et al. “Binarity at LOw Metallicity (BLOeM): Multiplicity
of Early B-Type Supergiants in the Small Magellanic Cloud.” Astronomy &
Astrophysics, vol. 698, A40, EDP Sciences, 2025, doi:10.1051/0004-6361/202452963.'
short: N. Britavskiy, L. Mahy, D.J. Lennon, L.R. Patrick, H. Sana, J.I. Villaseñor,
T. Shenar, J. Bodensteiner, M. Bernini-Peron, S.R. Berlanas, D.M. Bowman, P.A.
Crowther, S.E. De Mink, C.J. Evans, Y.L.L. Götberg, G. Holgado, C. Johnston, Z.
Keszthelyi, J. Klencki, N. Langer, I. Mandel, A. Menon, M. Moe, L.M. Oskinova,
D. Pauli, M. Pawlak, V. Ramachandran, M. Renzo, A.A.C. Sander, F.R.N. Schneider,
A. Schootemeijer, K. Sen, S. Simón-Díaz, J.T. Van Loon, J.S. Vink, Astronomy &
Astrophysics 698 (2025).
das_tickbox: '1'
date_created: 2025-06-15T22:01:29Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2026-09-16T09:10:41Z
day: '01'
ddc:
- '520'
department:
- _id: YlGo
doi: 10.1051/0004-6361/202452963
external_id:
arxiv:
- '2502.12239'
isi:
- '001497903100019'
file:
- access_level: open_access
checksum: 53a9f290cb1f468895e0d4446e0020f0
content_type: application/pdf
creator: dernst
date_created: 2025-06-25T08:38:02Z
date_updated: 2025-06-25T08:38:02Z
file_id: '19901'
file_name: 2025_AstronomyAstrophysics_Britavskiy.pdf
file_size: 7106568
relation: main_file
success: 1
file_date_updated: 2025-06-25T08:38:02Z
fulldoi: https://doi.org/10.1051/0004-6361/202452963
has_accepted_license: '1'
intvolume: ' 698'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: Astronomy & Astrophysics
publication_identifier:
eissn:
- 1432-0746
issn:
- 0004-6361
publication_status: published
publisher: EDP Sciences
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Binarity at LOw Metallicity (BLOeM): Multiplicity of early B-type supergiants
in the Small Magellanic Cloud'
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: 698
year: '2025'
...