---
_id: '15007'
abstract:
- lang: eng
text: Traditional blockchains grant the miner of a block full control not only over
which transactions but also their order. This constitutes a major flaw discovered
with the introduction of decentralized finance and allows miners to perform MEV
attacks. In this paper, we address the issue of sandwich attacks by providing
a construction that takes as input a blockchain protocol and outputs a new blockchain
protocol with the same security but in which sandwich attacks are not profitable.
Furthermore, our protocol is fully decentralized with no trusted third parties
or heavy cryptography primitives and carries a linear increase in latency and
minimum computation overhead.
acknowledgement: "We would like to thank Krzysztof Pietrzak and Jovana Mićić for useful
discussions. This work has been funded by the Swiss National Science Foundation
(SNSF) under grant agreement Nr. 200021_188443 (Advanced Consensus Protocols).\r\n"
alternative_title:
- LIPIcs
article_number: '12'
article_processing_charge: No
arxiv: 1
author:
- first_name: Orestis
full_name: Alpos, Orestis
last_name: Alpos
- first_name: Ignacio
full_name: Amores-Sesar, Ignacio
last_name: Amores-Sesar
- first_name: Christian
full_name: Cachin, Christian
last_name: Cachin
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
citation:
ama: 'Alpos O, Amores-Sesar I, Cachin C, Yeo MX. Eating sandwiches: Modular and
lightweight elimination of transaction reordering attacks. In: 27th International
Conference on Principles of Distributed Systems. Vol 286. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.OPODIS.2023.12'
apa: 'Alpos, O., Amores-Sesar, I., Cachin, C., & Yeo, M. X. (2024). Eating sandwiches:
Modular and lightweight elimination of transaction reordering attacks. In 27th
International Conference on Principles of Distributed Systems (Vol. 286).
Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2023.12'
chicago: 'Alpos, Orestis, Ignacio Amores-Sesar, Christian Cachin, and Michelle X
Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering
Attacks.” In 27th International Conference on Principles of Distributed Systems,
Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.OPODIS.2023.12.'
ieee: 'O. Alpos, I. Amores-Sesar, C. Cachin, and M. X. Yeo, “Eating sandwiches:
Modular and lightweight elimination of transaction reordering attacks,” in 27th
International Conference on Principles of Distributed Systems, Tokyo, Japan,
2024, vol. 286.'
ista: 'Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular
and lightweight elimination of transaction reordering attacks. 27th International
Conference on Principles of Distributed Systems. OPODIS: Conference on Principles
of Distributed Systems, LIPIcs, vol. 286, 12.'
mla: 'Alpos, Orestis, et al. “Eating Sandwiches: Modular and Lightweight Elimination
of Transaction Reordering Attacks.” 27th International Conference on Principles
of Distributed Systems, vol. 286, 12, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.OPODIS.2023.12.'
short: O. Alpos, I. Amores-Sesar, C. Cachin, M.X. Yeo, in:, 27th International Conference
on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024.
conference:
end_date: 2023-12-08
location: Tokyo, Japan
name: 'OPODIS: Conference on Principles of Distributed Systems'
start_date: 2023-12-06
date_created: 2024-02-18T23:01:02Z
date_published: 2024-01-18T00:00:00Z
date_updated: 2024-02-26T10:18:18Z
day: '18'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.OPODIS.2023.12
external_id:
arxiv:
- '2307.02954'
file:
- access_level: open_access
checksum: 2993e810a45e8c8056106834b07aea92
content_type: application/pdf
creator: dernst
date_created: 2024-02-26T10:16:57Z
date_updated: 2024-02-26T10:16:57Z
file_id: '15031'
file_name: 2024_LIPICs_Alpos.pdf
file_size: 1505994
relation: main_file
success: 1
file_date_updated: 2024-02-26T10:16:57Z
has_accepted_license: '1'
intvolume: ' 286'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
publication: 27th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959773089'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Eating sandwiches: Modular and lightweight elimination of transaction reordering
attacks'
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: '2024'
...
---
_id: '15008'
abstract:
- lang: eng
text: "Oblivious routing is a well-studied paradigm that uses static precomputed
routing tables for selecting routing paths within a network. Existing oblivious
routing schemes with polylogarithmic competitive ratio for general networks are
tree-based, in the sense that routing is performed according to a convex combination
of trees. However, this restriction to trees leads to a construction that has
time quadratic in the size of the network and does not parallelize well. \r\nIn
this paper we study oblivious routing schemes based on electrical routing. In
particular, we show that general networks with n vertices and m edges admit a
routing scheme that has competitive ratio O(log² n) and consists of a convex combination
of only O(√m) electrical routings. This immediately leads to an improved construction
algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with
Õ(√m) depth."
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the
Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P
33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald
Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets),
2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and
Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398
and a Sloan Research Fellowship."
alternative_title:
- LIPIcs
article_number: '55'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Sushant
full_name: Sachdeva, Sushant
last_name: Sachdeva
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
citation:
ama: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. Electrical flows
for polylogarithmic competitive oblivious routing. In: 15th Innovations in
Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55'
apa: 'Goranci, G., Henzinger, M. H., Räcke, H., Sachdeva, S., & Sricharan, A.
R. (2024). Electrical flows for polylogarithmic competitive oblivious routing.
In 15th Innovations in Theoretical Computer Science Conference (Vol. 287).
Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2024.55'
chicago: Goranci, Gramoz, Monika H Henzinger, Harald Räcke, Sushant Sachdeva, and
A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.”
In 15th Innovations in Theoretical Computer Science Conference, Vol. 287.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.55.
ieee: G. Goranci, M. H. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical
flows for polylogarithmic competitive oblivious routing,” in 15th Innovations
in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024,
vol. 287.
ista: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical
flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical
Computer Science Conference. ITCS: Innovations in Theoretical Computer Science
Conference, LIPIcs, vol. 287, 55.'
mla: Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious
Routing.” 15th Innovations in Theoretical Computer Science Conference,
vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ITCS.2024.55.
short: G. Goranci, M.H. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th
Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024.
conference:
end_date: 2024-02-02
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science Conference'
start_date: 2024-01-30
date_created: 2024-02-18T23:01:02Z
date_published: 2024-01-24T00:00:00Z
date_updated: 2025-07-15T12:51:53Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ITCS.2024.55
ec_funded: 1
external_id:
arxiv:
- '2303.02491'
file:
- access_level: open_access
checksum: b89716aae6a5599f187897e39de1e53a
content_type: application/pdf
creator: dernst
date_created: 2024-02-26T10:10:48Z
date_updated: 2024-02-26T10:10:48Z
file_id: '15030'
file_name: 2024_LIPICs_Goranci.pdf
file_size: 1054754
relation: main_file
success: 1
file_date_updated: 2024-02-26T10:10:48Z
has_accepted_license: '1'
intvolume: ' 287'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 15th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959773096'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Electrical flows for polylogarithmic competitive oblivious routing
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: 287
year: '2024'
...
---
_id: '14485'
abstract:
- lang: eng
text: "Batching is a technique that stores multiple keys/values in each node of
a data structure. In sequential search data structures, batching reduces latency
by reducing the number of cache misses and shortening the chain of pointers to
dereference. Applying batching to concurrent data structures is challenging, because
it is difficult to maintain the search property and keep contention low in the
presence of batching.\r\nIn this paper, we present a general methodology for leveraging
batching in concurrent search data structures, called BatchBoost. BatchBoost builds
a search data structure from distinct \"data\" and \"index\" layers. The data
layer’s purpose is to store a batch of key/value pairs in each of its nodes. The
index layer uses an unmodified concurrent search data structure to route operations
to a position in the data layer that is \"close\" to where the corresponding key
should exist. The requirements on the index and data layers are low: with minimal
effort, we were able to compose three highly scalable concurrent search data structures
based on three original data structures as the index layers with a batched version
of the Lazy List as the data layer. The resulting BatchBoost data structures provide
significant performance improvements over their original counterparts."
alternative_title:
- LIPIcs
article_number: '35'
article_processing_charge: Yes
author:
- first_name: Vitaly
full_name: Aksenov, Vitaly
last_name: Aksenov
- first_name: Michael
full_name: Anoprenko, Michael
last_name: Anoprenko
- first_name: Alexander
full_name: Fedorov, Alexander
id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
last_name: Fedorov
- first_name: Michael
full_name: Spear, Michael
last_name: Spear
citation:
ama: 'Aksenov V, Anoprenko M, Fedorov A, Spear M. Brief announcement: BatchBoost:
Universal batching for concurrent data structures. In: 37th International Symposium
on Distributed Computing. Vol 281. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.DISC.2023.35'
apa: 'Aksenov, V., Anoprenko, M., Fedorov, A., & Spear, M. (2023). Brief announcement:
BatchBoost: Universal batching for concurrent data structures. In 37th International
Symposium on Distributed Computing (Vol. 281). L’Aquila, Italy: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2023.35'
chicago: 'Aksenov, Vitaly, Michael Anoprenko, Alexander Fedorov, and Michael Spear.
“Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures.”
In 37th International Symposium on Distributed Computing, Vol. 281. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.DISC.2023.35.'
ieee: 'V. Aksenov, M. Anoprenko, A. Fedorov, and M. Spear, “Brief announcement:
BatchBoost: Universal batching for concurrent data structures,” in 37th International
Symposium on Distributed Computing, L’Aquila, Italy, 2023, vol. 281.'
ista: 'Aksenov V, Anoprenko M, Fedorov A, Spear M. 2023. Brief announcement: BatchBoost:
Universal batching for concurrent data structures. 37th International Symposium
on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol.
281, 35.'
mla: 'Aksenov, Vitaly, et al. “Brief Announcement: BatchBoost: Universal Batching
for Concurrent Data Structures.” 37th International Symposium on Distributed
Computing, vol. 281, 35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.DISC.2023.35.'
short: V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium
on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
conference:
end_date: 2023-10-13
location: L'Aquila, Italy
name: 'DISC: Symposium on Distributed Computing'
start_date: 2023-10-09
date_created: 2023-11-05T23:00:53Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2023-11-07T07:48:01Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
doi: 10.4230/LIPIcs.DISC.2023.35
file:
- access_level: open_access
checksum: d9f8d2915cccdf2df5905b7cd1b4a560
content_type: application/pdf
creator: dernst
date_created: 2023-11-06T11:45:21Z
date_updated: 2023-11-06T11:45:21Z
file_id: '14492'
file_name: 2023_LIPIcs_Aksenov.pdf
file_size: 646665
relation: main_file
success: 1
file_date_updated: 2023-11-06T11:45:21Z
has_accepted_license: '1'
intvolume: ' 281'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: 37th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959773010'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: BatchBoost: Universal batching for concurrent data structures'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 281
year: '2023'
...
---
_id: '14516'
abstract:
- lang: eng
text: 'We revisit decentralized random beacons with a focus on practical distributed
applications. Decentralized random beacons (Beaver and So, Eurocrypt''93) provide
the functionality for n parties to generate an unpredictable sequence of bits
in a way that cannot be biased, which is useful for any decentralized protocol
requiring trusted randomness. Existing beacon constructions are highly inefficient
in practical settings where protocol parties need to rejoin after crashes or disconnections,
and more significantly where smart contracts may rely on arbitrary index points
in high-volume streams. For this, we introduce a new notion of history-generating
decentralized random beacons (HGDRBs). Roughly, the history-generation property
of HGDRBs allows for previous beacon outputs to be efficiently generated knowing
only the current value and the public key. At application layers, history-generation
supports registering a sparser set of on-chain values if desired, so that apps
like lotteries can utilize on-chain values without incurring high-frequency costs,
enjoying all the benefits of DRBs implemented off-chain or with decoupled, special-purpose
chains. Unlike rollups, HG is tailored specifically to recovering and verifying
pseudorandom bit sequences and thus enjoys unique optimizations investigated in
this work. We introduce STROBE: an efficient HGDRB construction which generalizes
the original squaring-based RSA approach of Beaver and So. STROBE enjoys several
useful properties that make it suited for practical applications that use beacons:
1) history-generating: it can regenerate and verify high-throughput beacon streams,
supporting sparse (thus cost-effective) ledger entries; 2) concisely self-verifying:
NIZK-free, with state and validation employing a single ring element; 3) eco-friendly:
stake-based rather than work based; 4) unbounded: refresh-free, addressing limitations
of Beaver and So; 5) delay-free: results are immediately available. 6) storage-efficient:
the last beacon suffices to derive all past outputs, thus O(1) storage requirements
for nodes serving the whole history.'
acknowledgement: Work done when all the authors were at Novi Research, Meta.
alternative_title:
- LIPIcs
article_number: '7'
article_processing_charge: Yes
author:
- first_name: Donald
full_name: Beaver, Donald
last_name: Beaver
- first_name: Mahimna
full_name: Kelkar, Mahimna
last_name: Kelkar
- first_name: Kevin
full_name: Lewi, Kevin
last_name: Lewi
- first_name: Valeria
full_name: Nikolaenko, Valeria
last_name: Nikolaenko
- first_name: Alberto
full_name: Sonnino, Alberto
last_name: Sonnino
- first_name: Konstantinos
full_name: Chalkias, Konstantinos
last_name: Chalkias
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
- first_name: Ladi De
full_name: Naurois, Ladi De
last_name: Naurois
- first_name: Arnab
full_name: Roy, Arnab
last_name: Roy
citation:
ama: 'Beaver D, Kelkar M, Lewi K, et al. STROBE: Streaming Threshold Random Beacons.
In: 5th Conference on Advances in Financial Technologies. Vol 282. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.AFT.2023.7'
apa: 'Beaver, D., Kelkar, M., Lewi, K., Nikolaenko, V., Sonnino, A., Chalkias, K.,
… Roy, A. (2023). STROBE: Streaming Threshold Random Beacons. In 5th Conference
on Advances in Financial Technologies (Vol. 282). Princeton, NJ, United States:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2023.7'
chicago: 'Beaver, Donald, Mahimna Kelkar, Kevin Lewi, Valeria Nikolaenko, Alberto
Sonnino, Konstantinos Chalkias, Eleftherios Kokoris Kogias, Ladi De Naurois, and
Arnab Roy. “STROBE: Streaming Threshold Random Beacons.” In 5th Conference
on Advances in Financial Technologies, Vol. 282. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.AFT.2023.7.'
ieee: 'D. Beaver et al., “STROBE: Streaming Threshold Random Beacons,” in
5th Conference on Advances in Financial Technologies, Princeton, NJ, United
States, 2023, vol. 282.'
ista: 'Beaver D, Kelkar M, Lewi K, Nikolaenko V, Sonnino A, Chalkias K, Kokoris
Kogias E, Naurois LD, Roy A. 2023. STROBE: Streaming Threshold Random Beacons.
5th Conference on Advances in Financial Technologies. AFT: Conference on Advances
in Financial Technologies, LIPIcs, vol. 282, 7.'
mla: 'Beaver, Donald, et al. “STROBE: Streaming Threshold Random Beacons.” 5th
Conference on Advances in Financial Technologies, vol. 282, 7, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.AFT.2023.7.'
short: D. Beaver, M. Kelkar, K. Lewi, V. Nikolaenko, A. Sonnino, K. Chalkias, E.
Kokoris Kogias, L.D. Naurois, A. Roy, in:, 5th Conference on Advances in Financial
Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
conference:
end_date: 2023-10-25
location: Princeton, NJ, United States
name: 'AFT: Conference on Advances in Financial Technologies'
start_date: 2023-10-23
date_created: 2023-11-12T23:00:55Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2023-11-13T08:52:01Z
day: '01'
ddc:
- '000'
department:
- _id: ElKo
doi: 10.4230/LIPIcs.AFT.2023.7
file:
- access_level: open_access
checksum: c1f98831cb5149d6c030c41999e6e960
content_type: application/pdf
creator: dernst
date_created: 2023-11-13T08:44:34Z
date_updated: 2023-11-13T08:44:34Z
file_id: '14521'
file_name: 2023_LIPIcs_Beaver.pdf
file_size: 793495
relation: main_file
success: 1
file_date_updated: 2023-11-13T08:44:34Z
has_accepted_license: '1'
intvolume: ' 282'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1643
month: '10'
oa: 1
oa_version: Published Version
publication: 5th Conference on Advances in Financial Technologies
publication_identifier:
isbn:
- '9783959773034'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'STROBE: Streaming Threshold Random Beacons'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 282
year: '2023'
...
---
_id: '14083'
abstract:
- lang: eng
text: "In this work we consider the list-decodability and list-recoverability of
arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable
if every radius pn Hamming ball contains less than L codewords; (p,\U0001D4C1,L)_q-list-recoverability
is a generalization where we place radius pn Hamming balls on every point of a
combinatorial rectangle with side length \U0001D4C1 and again stipulate that there
be less than L codewords.\r\nOur main contribution is to precisely calculate the
maximum value of p for which there exist infinite families of positive rate (p,\U0001D4C1,L)_q-list-recoverable
codes, the quantity we call the zero-rate threshold. Denoting this value by p_*,
we in fact show that codes correcting a p_*+ε fraction of errors must have size
O_ε(1), i.e., independent of n. Such a result is typically referred to as a \"Plotkin
bound.\" To complement this, a standard random code with expurgation construction
shows that there exist positive rate codes correcting a p_*-ε fraction of errors.
We also follow a classical proof template (typically attributed to Elias and Bassalygo)
to derive from the zero-rate threshold other tradeoffs between rate and decoding
radius for list-decoding and list-recovery.\r\nTechnically, proving the Plotkin
bound boils down to demonstrating the Schur convexity of a certain function defined
on the q-simplex as well as the convexity of a univariate function derived from
it. We remark that an earlier argument claimed similar results for q-ary list-decoding;
however, we point out that this earlier proof is flawed."
acknowledgement: "Nicolas Resch: Research supported in part by ERC H2020 grant No.74079
(ALGSTRONGCRYPTO). Chen Yuan: Research supported in part by the National Key Research
and Development Projects under Grant 2022YFA1004900 and Grant 2021YFE0109900, the
National Natural Science Foundation of China under Grant 12101403 and Grant 12031011.\r\nAcknowledgements
YZ is grateful to Shashank Vatedka, Diyuan Wu and Fengxing Zhu for inspiring discussions."
alternative_title:
- LIPIcs
article_number: '99'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Nicolas
full_name: Resch, Nicolas
last_name: Resch
- first_name: Chen
full_name: Yuan, Chen
last_name: Yuan
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
citation:
ama: 'Resch N, Yuan C, Zhang Y. Zero-rate thresholds and new capacity bounds for
list-decoding and list-recovery. In: 50th International Colloquium on Automata,
Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.99'
apa: 'Resch, N., Yuan, C., & Zhang, Y. (2023). Zero-rate thresholds and new
capacity bounds for list-decoding and list-recovery. In 50th International
Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.99'
chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New
Capacity Bounds for List-Decoding and List-Recovery.” In 50th International
Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.99.
ieee: N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds
for list-decoding and list-recovery,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds
for list-decoding and list-recovery. 50th International Colloquium on Automata,
Languages, and Programming. ICALP: International Colloquium on Automata, Languages,
and Programming, LIPIcs, vol. 261, 99.'
mla: Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding
and List-Recovery.” 50th International Colloquium on Automata, Languages, and
Programming, vol. 261, 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.ICALP.2023.99.
short: N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:13Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:26:01Z
day: '01'
ddc:
- '000'
department:
- _id: MaMo
doi: 10.4230/LIPIcs.ICALP.2023.99
external_id:
arxiv:
- '2210.07754'
file:
- access_level: open_access
checksum: a449143fec3fbebb092cb8ef3b53c226
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T07:23:18Z
date_updated: 2023-08-21T07:23:18Z
file_id: '14091'
file_name: 2023_LIPIcsICALP_Resch.pdf
file_size: 1141497
relation: main_file
success: 1
file_date_updated: 2023-08-21T07:23:18Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '14084'
abstract:
- lang: eng
text: "A central problem in computational statistics is to convert a procedure for
sampling combinatorial objects into a procedure for counting those objects, and
vice versa. We will consider sampling problems which come from Gibbs distributions,
which are families of probability distributions over a discrete space Ω with probability
mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max]
and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor
Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log
Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts
c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²)
samples for integer-valued distributions (ignoring some second-order terms and
parameters), We show this is optimal up to logarithmic factors. We illustrate
with improved algorithms for counting connected subgraphs and perfect matchings
in a graph."
acknowledgement: We thank Heng Guo for helpful explanations of algorithms for sampling
connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the
Wang-Landau algorithm and its use in physics.
alternative_title:
- LIPIcs
article_number: '72'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: David G.
full_name: Harris, David G.
last_name: Harris
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. In:
50th International Colloquium on Automata, Languages, and Programming.
Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.72'
apa: 'Harris, D. G., & Kolmogorov, V. (2023). Parameter estimation for Gibbs
distributions. In 50th International Colloquium on Automata, Languages, and
Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.72'
chicago: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs
Distributions.” In 50th International Colloquium on Automata, Languages, and
Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.72.
ieee: D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,”
in 50th International Colloquium on Automata, Languages, and Programming,
Paderborn, Germany, 2023, vol. 261.
ista: 'Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions.
50th International Colloquium on Automata, Languages, and Programming. ICALP:
International Colloquium on Automata, Languages, and Programming, LIPIcs, vol.
261, 72.'
mla: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs
Distributions.” 50th International Colloquium on Automata, Languages, and Programming,
vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.72.
short: D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T06:49:11Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: VlKo
doi: 10.4230/LIPIcs.ICALP.2023.72
external_id:
arxiv:
- '2007.10824'
file:
- access_level: open_access
checksum: 6dee0684245bb1c524b9c955db1e933d
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T06:45:16Z
date_updated: 2023-08-21T06:45:16Z
file_id: '14088'
file_name: 2023_LIPIcsICALP_Harris.pdf
file_size: 917791
relation: main_file
success: 1
file_date_updated: 2023-08-21T06:45:16Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Parameter estimation for Gibbs distributions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '14085'
abstract:
- lang: eng
text: We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow
under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed,
unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm
in general sparse graphs with arbitrarily good approximation guarantee.
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(Grant agreement No.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
(MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic
Hierarchical Graph Decompositions”,\r\nI 5982-N, and project “Fast Algorithms for
a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the
netidee SCIENCE Stiftung, 2020–2024.\r\nThis work was done in part while Gramoz
Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There,
he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich
Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster
and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their
insightful comments."
alternative_title:
- LIPIcs
article_number: '69'
article_processing_charge: Yes
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Goranci G, Henzinger MH. Efficient data structures for incremental exact and
approximate maximum flow. In: 50th International Colloquium on Automata, Languages,
and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2023. doi:10.4230/LIPIcs.ICALP.2023.69'
apa: 'Goranci, G., & Henzinger, M. H. (2023). Efficient data structures for
incremental exact and approximate maximum flow. In 50th International Colloquium
on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.69'
chicago: Goranci, Gramoz, and Monika H Henzinger. “Efficient Data Structures for
Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium
on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
ieee: G. Goranci and M. H. Henzinger, “Efficient data structures for incremental
exact and approximate maximum flow,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
ista: 'Goranci G, Henzinger MH. 2023. Efficient data structures for incremental
exact and approximate maximum flow. 50th International Colloquium on Automata,
Languages, and Programming. ICALP: International Colloquium on Automata, Languages,
and Programming, LIPIcs, vol. 261, 69.'
mla: Goranci, Gramoz, and Monika H. Henzinger. “Efficient Data Structures for Incremental
Exact and Approximate Maximum Flow.” 50th International Colloquium on Automata,
Languages, and Programming, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.69.
short: G. Goranci, M.H. Henzinger, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T07:00:49Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.69
ec_funded: 1
external_id:
unknown:
- '2211.09606'
file:
- access_level: open_access
checksum: 074177e815a1656de5d4071c7a3dffa6
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T06:59:05Z
date_updated: 2023-08-21T06:59:05Z
file_id: '14089'
file_name: 2023_LIPIcsICALP_Goranci.pdf
file_size: 875910
relation: main_file
success: 1
file_date_updated: 2023-08-21T06:59:05Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: 'P33775 '
name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient data structures for incremental exact and approximate maximum flow
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '12760'
abstract:
- lang: eng
text: "Dynamic programming (DP) is one of the fundamental paradigms in algorithm
design. However,\r\nmany DP algorithms have to fill in large DP tables, represented
by two-dimensional arrays, which causes at least quadratic running times and space
usages. This has led to the development of improved algorithms for special cases
when the DPs satisfy additional properties like, e.g., the Monge property or total
monotonicity.\r\nIn this paper, we consider a new condition which assumes (among
some other technical assumptions) that the rows of the DP table are monotone.
Under this assumption, we introduce\r\na novel data structure for computing (1
+ ϵ)-approximate DP solutions in near-linear time and\r\nspace in the static setting,
and with polylogarithmic update times when the DP entries change\r\ndynamically.
To the best of our knowledge, our new condition is incomparable to previous conditions
and is the first which allows to derive dynamic algorithms based on existing DPs.
Instead of using two-dimensional arrays to store the DP tables, we store the rows
of the DP tables using monotone piecewise constant functions. This allows us to
store length-n DP table rows with entries in [0, W] using only polylog(n, W) bits,
and to perform operations, such as (min, +)-convolution or rounding, on these
functions in polylogarithmic time.\r\nWe further present several applications
of our data structure. For bicriteria versions of k-balanced graph partitioning
and simultaneous source location, we obtain the first dynamic algorithms with
subpolynomial update times, as well as the first static algorithms using only
near-linear time and space. Additionally, we obtain the currently fastest algorithm
for fully dynamic knapsack."
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project
“Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nStefan Neumann: This research
is supported by the the ERC Advanced Grant REBOUND (834862) and the EC H2020 RIA
project SoBigData++ (871042).\r\nStefan Schmid: Research supported by Austrian Science
Fund (FWF) project I 5025-N (DELTA), 2020-2024."
alternative_title:
- LIPIcs
article_number: '36'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefan
full_name: Neumann, Stefan
last_name: Neumann
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Henzinger MH, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone
dynamic programs and applications. In: 40th International Symposium on Theoretical
Aspects of Computer Science. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2023. doi:10.4230/LIPIcs.STACS.2023.36'
apa: 'Henzinger, M. H., Neumann, S., Räcke, H., & Schmid, S. (2023). Dynamic
maintenance of monotone dynamic programs and applications. In 40th International
Symposium on Theoretical Aspects of Computer Science (Vol. 254). Hamburg,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2023.36'
chicago: Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic
Maintenance of Monotone Dynamic Programs and Applications.” In 40th International
Symposium on Theoretical Aspects of Computer Science, Vol. 254. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.36.
ieee: M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance
of monotone dynamic programs and applications,” in 40th International Symposium
on Theoretical Aspects of Computer Science, Hamburg, Germany, 2023, vol. 254.
ista: 'Henzinger MH, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of
monotone dynamic programs and applications. 40th International Symposium on Theoretical
Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer
Science, LIPIcs, vol. 254, 36.'
mla: Henzinger, Monika H., et al. “Dynamic Maintenance of Monotone Dynamic Programs
and Applications.” 40th International Symposium on Theoretical Aspects of Computer
Science, vol. 254, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.STACS.2023.36.
short: M.H. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 40th International
Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-03-09
location: Hamburg, Germany
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2023-03-07
date_created: 2023-03-26T22:01:07Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-03-27T06:46:27Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.STACS.2023.36
external_id:
arxiv:
- '2301.01744'
file:
- access_level: open_access
checksum: 22141ab8bc55188e2dfff665e5daecbd
content_type: application/pdf
creator: dernst
date_created: 2023-03-27T06:37:22Z
date_updated: 2023-03-27T06:37:22Z
file_id: '12769'
file_name: 2023_LIPICS_HenzingerM.pdf
file_size: 872706
relation: main_file
success: 1
file_date_updated: 2023-03-27T06:37:22Z
has_accepted_license: '1'
intvolume: ' 254'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
publication: 40th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
isbn:
- '9783959772662'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic maintenance of monotone dynamic programs and applications
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 254
year: '2023'
...
---
_id: '11183'
abstract:
- lang: eng
text: "Subgraph detection has recently been one of the most studied problems in
the CONGEST model of distributed computing. In this work, we study the distributed
complexity of problems closely related to subgraph detection, mainly focusing
on induced subgraph detection. The main line of this work presents lower bounds
and parameterized algorithms w.r.t structural parameters of the input graph:\r\n-
On general graphs, we give unconditional lower bounds for induced detection of
cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions
from centralized parameterized complexity, we prove lower bounds in CONGEST for
detecting patterns with a 4-clique, and for induced path detection conditional
on the hardness of triangle detection in the congested clique.\r\n- On graphs
of bounded degeneracy, we show that induced paths can be detected fast in CONGEST
using techniques from parameterized algorithms, while detecting cycles and patterns
of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show
that induced subgraph detection is easy in CONGEST for any pattern graph. More
specifically, we adapt a centralized parameterized algorithm for a more general
maximum common induced subgraph detection problem to the distributed setting.
In addition to these induced subgraph detection results, we study various related
problems in the CONGEST and congested clique models, including for multicolored
versions of subgraph-detection-like problems."
acknowledgement: "Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070)
of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007)
operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported
by the European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François
Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced
subgraph detection [36]."
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: No
author:
- first_name: Amir
full_name: Nikabadi, Amir
last_name: Nikabadi
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
citation:
ama: 'Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs,
multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A,
eds. 25th International Conference on Principles of Distributed Systems.
Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.OPODIS.2021.15'
apa: 'Nikabadi, A., & Korhonen, J. (2022). Beyond distributed subgraph detection:
Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V.
Gramoli, & A. Milani (Eds.), 25th International Conference on Principles
of Distributed Systems (Vol. 217). Strasbourg, France: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15'
chicago: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” In 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas,
Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15.'
ieee: 'A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters,” in 25th International
Conference on Principles of Distributed Systems, Strasbourg, France, 2022,
vol. 217.'
ista: 'Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters. 25th International Conference
on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.'
mla: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas
et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
doi:10.4230/LIPIcs.OPODIS.2021.15.'
short: A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2022-05-02T07:56:35Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.15
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
file:
- access_level: open_access
checksum: 626551c14de5d4091573200ed0535752
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T07:53:00Z
date_updated: 2022-05-02T07:53:00Z
file_id: '11345'
file_name: 2022_LIPICs_Nikabadi.pdf
file_size: 790396
relation: main_file
success: 1
file_date_updated: 2022-05-02T07:53:00Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Beyond distributed subgraph detection: Induced subgraphs, multicolored problems
and graph parameters'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '11184'
abstract:
- lang: eng
text: "Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node.\r\nIn this work, we consider the more general setting where
G is an arbitrary regular graph, and present a technique for simulating protocols
designed for fully-connected networks in any connected regular graph. Our main
result is a simulation that is efficient on many interesting graph families: roughly,
the simulation overhead is polylogarithmic in the number of nodes, and quadratic
in the conductance of the graph. As a sample application, we show that, in any
regular graph with conductance φ, both leader election and exact majority can
be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability,
using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast
and space-efficient population protocols for leader election and exact majority
on graphs with good expansion properties. We believe our results will prove generally
useful, as they allow efficient technology transfer between the well-mixed (clique)
case, and the under-explored spatial setting."
acknowledgement: "Dan Alistarh: This project has received funding from the European
Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has
received from the European Union’s Horizon 2020 research and\r\ninnovation programme
under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements
We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock
construction to non-regular graphs. We also thank anonymous reviewers for their
useful comments on earlier versions of this manuscript."
alternative_title:
- LIPIcs
article_number: '14'
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols.
In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles
of Distributed Systems. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.OPODIS.2021.14'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2022). Fast graphical
population protocols. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems (Vol. 217).
Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14'
chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical
Population Protocols.” In 25th International Conference on Principles of Distributed
Systems, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol.
217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14.
ieee: D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population
protocols,” in 25th International Conference on Principles of Distributed Systems,
Strasbourg, France, 2022, vol. 217.
ista: Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols.
25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs,
vol. 217, 14.
mla: Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” 25th
International Conference on Principles of Distributed Systems, edited by Quentin
Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, doi:10.4230/LIPIcs.OPODIS.2021.14.
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A.
Milani (Eds.), 25th International Conference on Principles of Distributed Systems,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2022-05-02T08:09:39Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.14
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: 2c7c982174c6f98c4ca6e92539d15086
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T08:06:33Z
date_updated: 2022-05-02T08:06:33Z
file_id: '11346'
file_name: 2022_LIPICs_Alistarh.pdf
file_size: 959406
relation: main_file
success: 1
file_date_updated: 2022-05-02T08:06:33Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast graphical population protocols
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '11428'
abstract:
- lang: eng
text: The medial axis of a set consists of the points in the ambient space without
a unique closest point on the original set. Since its introduction, the medial
axis has been used extensively in many applications as a method of computing a
topologically equivalent skeleton. Unfortunately, one limiting factor in the use
of the medial axis of a smooth manifold is that it is not necessarily topologically
stable under small perturbations of the manifold. To counter these instabilities
various prunings of the medial axis have been proposed. Here, we examine one type
of pruning, called burning. Because of the good experimental results, it was hoped
that the burning method of simplifying the medial axis would be stable. In this
work we show a simple example that dashes such hopes based on Bing’s house with
two rooms, demonstrating an isotopy of a shape where the medial axis goes from
collapsible to non-collapsible.
acknowledgement: 'Partially supported by the DFG Collaborative Research Center TRR
109, “Discretization in Geometry and Dynamics” and the European Research Council
(ERC), grant no. 788183, “Alpha Shape Theory Extended”. Erin Chambers: Supported
in part by the National Science Foundation through grants DBI-1759807, CCF-1907612,
and CCF-2106672. Mathijs Wintraecken: Supported by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No. 754411. The Austrian science fund (FWF) M-3073 Acknowledgements We thank André
Lieutier, David Letscher, Ellen Gasparovic, Kathryn Leonard, and Tao Ju for early
discussions on this work. We also thank Lu Liu, Yajie Yan and Tao Ju for sharing
code to generate the examples.'
article_processing_charge: No
author:
- first_name: Erin
full_name: Chambers, Erin
last_name: Chambers
- first_name: Christopher D
full_name: Fillmore, Christopher D
id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
last_name: Fillmore
- first_name: Elizabeth R
full_name: Stephenson, Elizabeth R
id: 2D04F932-F248-11E8-B48F-1D18A9856A87
last_name: Stephenson
orcid: 0000-0002-6862-208X
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. A cautionary tale:
Burning the medial axis is unstable. In: Goaoc X, Kerber M, eds. 38th International
Symposium on Computational Geometry. Vol 224. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2022:66:1-66:9. doi:10.4230/LIPIcs.SoCG.2022.66'
apa: 'Chambers, E., Fillmore, C. D., Stephenson, E. R., & Wintraecken, M. (2022).
A cautionary tale: Burning the medial axis is unstable. In X. Goaoc & M. Kerber
(Eds.), 38th International Symposium on Computational Geometry (Vol. 224,
p. 66:1-66:9). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2022.66'
chicago: 'Chambers, Erin, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs
Wintraecken. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” In 38th
International Symposium on Computational Geometry, edited by Xavier Goaoc
and Michael Kerber, 224:66:1-66:9. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SoCG.2022.66.'
ieee: 'E. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “A cautionary
tale: Burning the medial axis is unstable,” in 38th International Symposium
on Computational Geometry, Berlin, Germany, 2022, vol. 224, p. 66:1-66:9.'
ista: 'Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. 2022. A cautionary
tale: Burning the medial axis is unstable. 38th International Symposium on Computational
Geometry. SoCG: Symposium on Computational GeometryLIPIcs vol. 224, 66:1-66:9.'
mla: 'Chambers, Erin, et al. “A Cautionary Tale: Burning the Medial Axis Is Unstable.”
38th International Symposium on Computational Geometry, edited by Xavier
Goaoc and Michael Kerber, vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, p. 66:1-66:9, doi:10.4230/LIPIcs.SoCG.2022.66.'
short: E. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, in:, X. Goaoc,
M. Kerber (Eds.), 38th International Symposium on Computational Geometry, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 66:1-66:9.
conference:
end_date: 2022-06-10
location: Berlin, Germany
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2022-06-07
date_created: 2022-06-01T14:18:04Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-02-21T09:50:52Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2022.66
ec_funded: 1
editor:
- first_name: Xavier
full_name: Goaoc, Xavier
last_name: Goaoc
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
file:
- access_level: open_access
checksum: b25ce40fade4ebc0bcaae176db4f5f1f
content_type: application/pdf
creator: dernst
date_created: 2022-06-07T07:58:30Z
date_updated: 2022-06-07T07:58:30Z
file_id: '11437'
file_name: 2022_LIPICs_Chambers.pdf
file_size: 17580705
relation: main_file
success: 1
file_date_updated: 2022-06-07T07:58:30Z
has_accepted_license: '1'
intvolume: ' 224'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 66:1-66:9
project:
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 38th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-227-3
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
series_title: LIPIcs
status: public
title: 'A cautionary tale: Burning the medial axis is unstable'
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 224
year: '2022'
...
---
_id: '11812'
abstract:
- lang: eng
text: "This paper presents a comprehensive study of algorithms for maintaining the
number of all connected four-vertex subgraphs in a dynamic graph. Specifically,
our algorithms maintain the number of paths of length three in deterministic amortized
O(m^{1/2}) update time, and any other connected four-vertex subgraph which is
not a clique in deterministic amortized update time O(m^{2/3}). Queries can be
answered in constant time. We also study the query times for subgraphs containing
an arbitrary edge that is supplied only with the query as well as the case where
only subgraphs containing a vertex s that is fixed beforehand are considered.
For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far
from (conditional) lower bounds: Based on the OMv conjecture we show that any
dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or
that counts length-3 paths takes update time Ω(m^{1/2-δ}).\r\nAdditionally, for
4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ})
for any small constant δ > 0 for the amortized update time, assuming the static
combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by
Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved
by a polynomial factor."
alternative_title:
- LIPIcs
article_number: '18'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kathrin
full_name: Hanauer, Kathrin
last_name: Hanauer
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Qi Cheng
full_name: Hua, Qi Cheng
last_name: Hua
citation:
ama: 'Hanauer K, Henzinger MH, Hua QC. Fully dynamic four-vertex subgraph counting.
In: 1st Symposium on Algorithmic Foundations of Dynamic Networks. Vol 221.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.18'
apa: 'Hanauer, K., Henzinger, M. H., & Hua, Q. C. (2022). Fully dynamic four-vertex
subgraph counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks
(Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2022.18'
chicago: Hanauer, Kathrin, Monika H Henzinger, and Qi Cheng Hua. “Fully Dynamic
Four-Vertex Subgraph Counting.” In 1st Symposium on Algorithmic Foundations
of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022. https://doi.org/10.4230/LIPIcs.SAND.2022.18.
ieee: K. Hanauer, M. H. Henzinger, and Q. C. Hua, “Fully dynamic four-vertex subgraph
counting,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks,
Virtual, 2022, vol. 221.
ista: 'Hanauer K, Henzinger MH, Hua QC. 2022. Fully dynamic four-vertex subgraph
counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND:
Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.'
mla: Hanauer, Kathrin, et al. “Fully Dynamic Four-Vertex Subgraph Counting.” 1st
Symposium on Algorithmic Foundations of Dynamic Networks, vol. 221, 18, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.SAND.2022.18.
short: K. Hanauer, M.H. Henzinger, Q.C. Hua, in:, 1st Symposium on Algorithmic Foundations
of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2022-04-30
location: Virtual
name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
start_date: 2022-04-28
date_created: 2022-08-12T06:57:55Z
date_published: 2022-04-29T00:00:00Z
date_updated: 2023-02-14T08:25:42Z
day: '29'
doi: 10.4230/LIPIcs.SAND.2022.18
extern: '1'
external_id:
arxiv:
- '2106.15524'
intvolume: ' 221'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.SAND.2022.18
month: '04'
oa: 1
oa_version: Published Version
publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
isbn:
- '9783959772242'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic four-vertex subgraph counting
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 221
year: '2022'
...
---
_id: '12101'
abstract:
- lang: eng
text: 'Spatial games form a widely-studied class of games from biology and physics
modeling the evolution of social behavior. Formally, such a game is defined by
a square (d by d) payoff matrix M and an undirected graph G. Each vertex of G
represents an individual, that initially follows some strategy i ∈ {1,2,…,d}.
In each round of the game, every individual plays the matrix game with each of
its neighbors: An individual following strategy i meeting a neighbor following
strategy j receives a payoff equal to the entry (i,j) of M. Then, each individual
updates its strategy to its neighbors'' strategy with the highest sum of payoffs,
and the next round starts. The basic computational problems consist of reachability
between configurations and the average frequency of a strategy. For general spatial
games and graphs, these problems are in PSPACE. In this paper, we examine restricted
setting: the game is a prisoner’s dilemma; and G is a subgraph of grid. We prove
that basic computational problems for spatial games with prisoner’s dilemma on
a subgraph of a grid are PSPACE-hard.'
acknowledgement: "Krishnendu Chatterjee: The research was partially supported by the
ERC CoG 863818\r\n(ForM-SMArt).\r\nIsmaël Jecker: The research was partially supported
by the ERC grant 950398 (INFSYS).\r\nJakub Svoboda: The research was partially supported
by the ERC CoG 863818 (ForM-SMArt)"
article_number: 11:1-11:14
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Complexity of spatial
games. In: 42nd IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2022. doi:10.4230/LIPIcs.FSTTCS.2022.11'
apa: 'Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., & Svoboda, J. (2022).
Complexity of spatial games. In 42nd IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science (Vol. 250). Madras,
India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11'
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub
Svoboda. “Complexity of Spatial Games.” In 42nd IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science, Vol.
250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11.
ieee: K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Complexity
of spatial games,” in 42nd IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science, Madras, India, 2022, vol. 250.
ista: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2022. Complexity of spatial
games. 42nd IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science. FSTTC: Foundations of Software Technology and Theoretical
Computer Science vol. 250, 11:1-11:14.'
mla: Chatterjee, Krishnendu, et al. “Complexity of Spatial Games.” 42nd IARCS
Annual Conference on Foundations of Software Technology and Theoretical Computer
Science, vol. 250, 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, doi:10.4230/LIPIcs.FSTTCS.2022.11.
short: K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 42nd IARCS
Annual Conference on Foundations of Software Technology and Theoretical Computer
Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2022-12-20
location: Madras, India
name: 'FSTTC: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2022-12-18
date_created: 2023-01-01T23:00:50Z
date_published: 2022-12-14T00:00:00Z
date_updated: 2025-07-14T09:09:55Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2022.11
ec_funded: 1
file:
- access_level: open_access
checksum: a21e3ba2421e2c4a06aa2cb6d530ede1
content_type: application/pdf
creator: dernst
date_created: 2023-01-20T10:19:19Z
date_updated: 2023-01-20T10:19:19Z
file_id: '12323'
file_name: 2022_LIPICs_Chatterjee.pdf
file_size: 657396
relation: main_file
success: 1
file_date_updated: 2023-01-20T10:19:19Z
has_accepted_license: '1'
intvolume: ' 250'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 42nd IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- '9783959772617'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Complexity of spatial games
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: 250
year: '2022'
...
---
_id: '12102'
abstract:
- lang: eng
text: 'Given a Markov chain M = (V, v_0, δ), with state space V and a starting state
v_0, and a probability threshold ε, an ε-core is a subset C of states that is
left with probability at most ε. More formally, C ⊆ V is an ε-core, iff ℙ[reach
(V\C)] ≤ ε. Cores have been applied in a wide variety of verification problems
over Markov chains, Markov decision processes, and probabilistic programs, as
a means of discarding uninteresting and low-probability parts of a probabilistic
system and instead being able to focus on the states that are likely to be encountered
in a real-world run. In this work, we focus on the problem of computing a minimal
ε-core in a Markov chain. Our contributions include both negative and positive
results: (i) We show that the decision problem on the existence of an ε-core of
a given size is NP-complete. This solves an open problem posed in [Jan Kretínský
and Tobias Meggendorfer, 2020]. We additionally show that the problem remains
NP-complete even when limited to acyclic Markov chains with bounded maximal vertex
degree; (ii) We provide a polynomial time algorithm for computing a minimal ε-core
on Markov chains over control-flow graphs of structured programs. A straightforward
combination of our algorithm with standard branch prediction techniques allows
one to apply the idea of cores to find a subset of program lines that are left
with low probability and then focus any desired static analysis on this core subset.'
acknowledgement: "The research was partially supported by the Hong Kong Research Grants
Council ECS\r\nProject No. 26208122, ERC CoG 863818 (FoRM-SMArt), the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
Grant Agreement No. 665385, HKUST– Kaisa Joint Research Institute Project Grant
HKJRI3A-055 and HKUST Startup Grant R9272. Ali Ahmadi and Roodabeh Safavi were interns
at HKUST."
article_number: '29'
article_processing_charge: No
author:
- first_name: Ali
full_name: Ahmadi, Ali
last_name: Ahmadi
- 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: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic
D. Algorithms and hardness results for computing cores of Markov chains. In: 42nd
IARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.FSTTCS.2022.29'
apa: 'Ahmadi, A., Chatterjee, K., Goharshady, A. K., Meggendorfer, T., Safavi Hemami,
R., & Zikelic, D. (2022). Algorithms and hardness results for computing cores
of Markov chains. In 42nd IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (Vol. 250). Madras, India: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29'
chicago: Ahmadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer,
Roodabeh Safavi Hemami, and Dorde Zikelic. “Algorithms and Hardness Results for
Computing Cores of Markov Chains.” In 42nd IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, Vol. 250. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29.
ieee: A. Ahmadi, K. Chatterjee, A. K. Goharshady, T. Meggendorfer, R. Safavi Hemami,
and D. Zikelic, “Algorithms and hardness results for computing cores of Markov
chains,” in 42nd IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, Madras, India, 2022, vol. 250.
ista: 'Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic
D. 2022. Algorithms and hardness results for computing cores of Markov chains.
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science. FSTTC: Foundations of Software Technology and Theoretical Computer
Science vol. 250, 29.'
mla: Ahmadi, Ali, et al. “Algorithms and Hardness Results for Computing Cores of
Markov Chains.” 42nd IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, vol. 250, 29, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022, doi:10.4230/LIPIcs.FSTTCS.2022.29.
short: A. Ahmadi, K. Chatterjee, A.K. Goharshady, T. Meggendorfer, R. Safavi Hemami,
D. Zikelic, in:, 42nd IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022.
conference:
end_date: 2022-12-20
location: Madras, India
name: 'FSTTC: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2022-12-18
date_created: 2023-01-01T23:00:50Z
date_published: 2022-12-14T00:00:00Z
date_updated: 2025-07-14T09:09:55Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
doi: 10.4230/LIPIcs.FSTTCS.2022.29
ec_funded: 1
file:
- access_level: open_access
checksum: 6660c802489013f034c9e8bd57f4d46e
content_type: application/pdf
creator: dernst
date_created: 2023-01-20T10:39:44Z
date_updated: 2023-01-20T10:39:44Z
file_id: '12324'
file_name: 2022_LIPICs_Ahmadi.pdf
file_size: 872534
relation: main_file
success: 1
file_date_updated: 2023-01-20T10:39:44Z
has_accepted_license: '1'
intvolume: ' 250'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: 42nd IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- '9783959772617'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithms and hardness results for computing cores of Markov chains
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: 250
year: '2022'
...
---
_id: '12508'
abstract:
- lang: eng
text: "We explore the notion of history-determinism in the context of timed automata
(TA). History-deterministic automata are those in which nondeterminism can be
resolved on the fly, based on the run constructed thus far. History-determinism
is a robust property that admits different game-based characterisations, and history-deterministic
specifications allow for game-based verification without an expensive determinization
step.\r\nWe show yet another characterisation of history-determinism in terms
of fair simulation, at the general level of labelled transition systems: a system
is history-deterministic precisely if and only if it fairly simulates all language
smaller systems.\r\nFor timed automata over infinite timed words it is known that
universality is undecidable for Büchi TA. We show that for history-deterministic
TA with arbitrary parity acceptance, timed universality, inclusion, and synthesis
all remain decidable and are ExpTime-complete.\r\nFor the subclass of TA with
safety or reachability acceptance, we show that checking whether such an automaton
is history-deterministic is decidable (in ExpTime), and history-deterministic
TA with safety acceptance are effectively determinizable without introducing new
automata states."
acknowledgement: "Thomas A. Henzinger: This work was supported in part by the ERC-2020-AdG
101020093.\r\nPatrick Totzke: acknowledges support from the EPSRC, project no. EP/V025848/1.\r\n"
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Karoliina
full_name: Lehtinen, Karoliina
last_name: Lehtinen
- first_name: Patrick
full_name: Totzke, Patrick
last_name: Totzke
citation:
ama: 'Henzinger TA, Lehtinen K, Totzke P. History-deterministic timed automata.
In: 33rd International Conference on Concurrency Theory. Vol 243. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2022:14:1-14:21. doi:10.4230/LIPIcs.CONCUR.2022.14'
apa: 'Henzinger, T. A., Lehtinen, K., & Totzke, P. (2022). History-deterministic
timed automata. In 33rd International Conference on Concurrency Theory
(Vol. 243, p. 14:1-14:21). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2022.14'
chicago: Henzinger, Thomas A, Karoliina Lehtinen, and Patrick Totzke. “History-Deterministic
Timed Automata.” In 33rd International Conference on Concurrency Theory,
243:14:1-14:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.CONCUR.2022.14.
ieee: T. A. Henzinger, K. Lehtinen, and P. Totzke, “History-deterministic timed
automata,” in 33rd International Conference on Concurrency Theory, Warsaw,
Poland, 2022, vol. 243, p. 14:1-14:21.
ista: 'Henzinger TA, Lehtinen K, Totzke P. 2022. History-deterministic timed automata.
33rd International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 243, 14:1-14:21.'
mla: Henzinger, Thomas A., et al. “History-Deterministic Timed Automata.” 33rd
International Conference on Concurrency Theory, vol. 243, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2022, p. 14:1-14:21, doi:10.4230/LIPIcs.CONCUR.2022.14.
short: T.A. Henzinger, K. Lehtinen, P. Totzke, in:, 33rd International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
p. 14:1-14:21.
conference:
end_date: 2022-09-16
location: Warsaw, Poland
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2022-09-13
date_created: 2023-02-05T17:24:23Z
date_published: 2022-09-06T00:00:00Z
date_updated: 2023-02-06T09:23:31Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2022.14
ec_funded: 1
file:
- access_level: open_access
checksum: 9e97e15628f66b2ad77f535bb0327dee
content_type: application/pdf
creator: dernst
date_created: 2023-02-06T09:21:09Z
date_updated: 2023-02-06T09:21:09Z
file_id: '12520'
file_name: 2022_LIPICs_Henzinger2.pdf
file_size: 717940
relation: main_file
success: 1
file_date_updated: 2023-02-06T09:21:09Z
has_accepted_license: '1'
intvolume: ' 243'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 14:1-14:21
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 33rd International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959772464'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: History-deterministic timed automata
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 243
year: '2022'
...
---
_id: '12509'
abstract:
- lang: eng
text: A graph game is a two-player zero-sum game in which the players move a token
throughout a graph to produce an infinite path, which determines the winner or
payoff of the game. In bidding games, both players have budgets, and in each turn,
we hold an "auction" (bidding) to determine which player moves the token. In this
survey, we consider several bidding mechanisms and their effect on the properties
of the game. Specifically, bidding games, and in particular bidding games of infinite
duration, have an intriguing equivalence with random-turn games in which in each
turn, the player who moves is chosen randomly. We summarize how minor changes
in the bidding mechanism lead to unexpected differences in the equivalence with
random-turn games.
acknowledgement: "Guy Avni: Work partially supported by the Israel Science Foundation,
ISF grant agreement\r\nno 1679/21.\r\nThomas A. Henzinger: This work was supported
in part by the ERC-2020-AdG 101020093.\r\nWe would like to thank all our collaborators
Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný,
Josef Tkadlec, and Ðorđe Žikelić; we hope the collaboration was as fun and meaningful
for you as it was for us."
article_processing_charge: No
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- 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: 'Avni G, Henzinger TA. An updated survey of bidding games on graphs. In: 47th
International Symposium on Mathematical Foundations of Computer Science. Vol
241. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:3:1-3:6. doi:10.4230/LIPIcs.MFCS.2022.3'
apa: 'Avni, G., & Henzinger, T. A. (2022). An updated survey of bidding games
on graphs. In 47th International Symposium on Mathematical Foundations of Computer
Science (Vol. 241, p. 3:1-3:6). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2022.3'
chicago: 'Avni, Guy, and Thomas A Henzinger. “An Updated Survey of Bidding Games
on Graphs.” In 47th International Symposium on Mathematical Foundations of
Computer Science, 241:3:1-3:6. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022. https://doi.org/10.4230/LIPIcs.MFCS.2022.3.'
ieee: G. Avni and T. A. Henzinger, “An updated survey of bidding games on graphs,”
in 47th International Symposium on Mathematical Foundations of Computer Science,
Vienna, Austria, 2022, vol. 241, p. 3:1-3:6.
ista: 'Avni G, Henzinger TA. 2022. An updated survey of bidding games on graphs.
47th International Symposium on Mathematical Foundations of Computer Science.
MFCS: Symposium on Mathematical Foundations of Computer ScienceLeibniz International
Proceedings in Informatics (LIPIcs) vol. 241, 3:1-3:6.'
mla: Avni, Guy, and Thomas A. Henzinger. “An Updated Survey of Bidding Games on
Graphs.” 47th International Symposium on Mathematical Foundations of Computer
Science, vol. 241, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
p. 3:1-3:6, doi:10.4230/LIPIcs.MFCS.2022.3.
short: G. Avni, T.A. Henzinger, in:, 47th International Symposium on Mathematical
Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
Dagstuhl, Germany, 2022, p. 3:1-3:6.
conference:
end_date: 2022-08-26
location: Vienna, Austria
name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
start_date: 2022-08-22
date_created: 2023-02-05T17:26:01Z
date_published: 2022-08-22T00:00:00Z
date_updated: 2023-02-06T09:16:54Z
day: '22'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2022.3
ec_funded: 1
file:
- access_level: open_access
checksum: 1888ec9421622f9526fbec2de035f132
content_type: application/pdf
creator: dernst
date_created: 2023-02-06T09:13:04Z
date_updated: 2023-02-06T09:13:04Z
file_id: '12519'
file_name: 2022_LIPICs_Avni.pdf
file_size: 624586
relation: main_file
success: 1
file_date_updated: 2023-02-06T09:13:04Z
has_accepted_license: '1'
intvolume: ' 241'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 3:1-3:6
place: Dagstuhl, Germany
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 47th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- '9783959772563'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: An updated survey of bidding games on 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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 241
year: '2022'
...
---
_id: '12775'
abstract:
- lang: eng
text: "We consider the problem of approximating the reachability probabilities in
Markov decision processes (MDP) with uncountable (continuous) state and action
spaces. While there are algorithms that, for special classes of such MDP, provide
a sequence of approximations converging to the true value in the limit, our aim
is to obtain an algorithm with guarantees on the precision of the approximation.\r\nAs
this problem is undecidable in general, assumptions on the MDP are necessary.
Our main contribution is to identify sufficient assumptions that are as weak as
possible, thus approaching the \"boundary\" of which systems can be correctly
and reliably analyzed. To this end, we also argue why each of our assumptions
is necessary for algorithms based on processing finitely many observations.\r\nWe
present two solution variants. The first one provides converging lower bounds
under weaker assumptions than typical ones from previous works concerned with
guarantees. The second one then utilizes stronger assumptions to additionally
provide converging upper bounds. Altogether, we obtain an anytime algorithm, i.e.
yielding a sequence of approximants with known and iteratively improving precision,
converging to the true value in the limit. Besides, due to the generality of our
assumptions, our algorithms are very general templates, readily allowing for various
heuristics from literature in contrast to, e.g., a specific discretization algorithm.
Our theoretical contribution thus paves the way for future practical improvements
without sacrificing correctness guarantees."
acknowledgement: "Kush Grover: The author has been supported by the DFG research training
group GRK\r\n2428 ConVeY.\r\nMaximilian Weininger: The author has been partially
supported by DFG projects 383882557\r\nStatistical Unbounded Verification (SUV)
and 427755713 Group-By Objectives in Probabilistic\r\nVerification (GOPro)"
alternative_title:
- LIPIcs
article_number: '11'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kush
full_name: Grover, Kush
last_name: Grover
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: Maimilian
full_name: Weininger, Maimilian
last_name: Weininger
citation:
ama: 'Grover K, Kretinsky J, Meggendorfer T, Weininger M. Anytime guarantees for
reachability in uncountable Markov decision processes. In: 33rd International
Conference on Concurrency Theory . Vol 243. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2022. doi:10.4230/LIPIcs.CONCUR.2022.11'
apa: 'Grover, K., Kretinsky, J., Meggendorfer, T., & Weininger, M. (2022). Anytime
guarantees for reachability in uncountable Markov decision processes. In 33rd
International Conference on Concurrency Theory (Vol. 243). Warsaw, Poland:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2022.11'
chicago: Grover, Kush, Jan Kretinsky, Tobias Meggendorfer, and Maimilian Weininger.
“Anytime Guarantees for Reachability in Uncountable Markov Decision Processes.”
In 33rd International Conference on Concurrency Theory , Vol. 243. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.CONCUR.2022.11.
ieee: K. Grover, J. Kretinsky, T. Meggendorfer, and M. Weininger, “Anytime guarantees
for reachability in uncountable Markov decision processes,” in 33rd International
Conference on Concurrency Theory , Warsaw, Poland, 2022, vol. 243.
ista: 'Grover K, Kretinsky J, Meggendorfer T, Weininger M. 2022. Anytime guarantees
for reachability in uncountable Markov decision processes. 33rd International
Conference on Concurrency Theory . CONCUR: Conference on Concurrency Theory, LIPIcs,
vol. 243, 11.'
mla: Grover, Kush, et al. “Anytime Guarantees for Reachability in Uncountable Markov
Decision Processes.” 33rd International Conference on Concurrency Theory ,
vol. 243, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.CONCUR.2022.11.
short: K. Grover, J. Kretinsky, T. Meggendorfer, M. Weininger, in:, 33rd International
Conference on Concurrency Theory , Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022.
conference:
end_date: 2022-09-16
location: Warsaw, Poland
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2022-09-13
date_created: 2023-03-28T08:09:32Z
date_published: 2022-09-15T00:00:00Z
date_updated: 2023-09-26T10:43:30Z
day: '15'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2022.11
external_id:
arxiv:
- '2008.04824'
file:
- access_level: open_access
checksum: e282e43d3ae0ba6e067b72f4583e13c0
content_type: application/pdf
creator: dernst
date_created: 2023-09-26T10:43:15Z
date_updated: 2023-09-26T10:43:15Z
file_id: '14372'
file_name: 2022_LIPIcS_Grover.pdf
file_size: 960036
relation: main_file
success: 1
file_date_updated: 2023-09-26T10:43:15Z
has_accepted_license: '1'
intvolume: ' 243'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: '33rd International Conference on Concurrency Theory '
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Anytime guarantees for reachability in uncountable 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: 243
year: '2022'
...
---
_id: '9345'
abstract:
- lang: eng
text: Modeling a crystal as a periodic point set, we present a fingerprint consisting
of density functionsthat facilitates the efficient search for new materials and
material properties. We prove invarianceunder isometries, continuity, and completeness
in the generic case, which are necessary featuresfor the reliable comparison of
crystals. The proof of continuity integrates methods from discretegeometry and
lattice theory, while the proof of generic completeness combines techniques fromgeometry
with analysis. The fingerprint has a fast algorithm based on Brillouin zones and
relatedinclusion-exclusion formulae. We have implemented the algorithm and describe
its application tocrystal structure prediction.
acknowledgement: The authors thank Janos Pach for insightful discussions on the topic
of thispaper, Morteza Saghafian for finding the one-dimensional counterexample mentioned
in Section 5,and Larry Andrews for generously sharing his crystallographic perspective.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Vitaliy
full_name: ' Kurlin , Vitaliy'
last_name: ' Kurlin '
- first_name: Philip
full_name: Smith, Philip
last_name: Smith
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. The density fingerprint
of a periodic point set. In: 37th International Symposium on Computational
Geometry (SoCG 2021). Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2021:32:1-32:16. doi:10.4230/LIPIcs.SoCG.2021.32'
apa: 'Edelsbrunner, H., Heiss, T., Kurlin , V., Smith, P., & Wintraecken, M.
(2021). The density fingerprint of a periodic point set. In 37th International
Symposium on Computational Geometry (SoCG 2021) (Vol. 189, p. 32:1-32:16).
Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.32'
chicago: Edelsbrunner, Herbert, Teresa Heiss, Vitaliy Kurlin , Philip Smith, and
Mathijs Wintraecken. “The Density Fingerprint of a Periodic Point Set.” In 37th
International Symposium on Computational Geometry (SoCG 2021), 189:32:1-32:16.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.32.
ieee: H. Edelsbrunner, T. Heiss, V. Kurlin , P. Smith, and M. Wintraecken, “The
density fingerprint of a periodic point set,” in 37th International Symposium
on Computational Geometry (SoCG 2021), Virtual, 2021, vol. 189, p. 32:1-32:16.
ista: 'Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. 2021. The density
fingerprint of a periodic point set. 37th International Symposium on Computational
Geometry (SoCG 2021). SoCG: Symposium on Computational Geometry, LIPIcs, vol.
189, 32:1-32:16.'
mla: Edelsbrunner, Herbert, et al. “The Density Fingerprint of a Periodic Point
Set.” 37th International Symposium on Computational Geometry (SoCG 2021),
vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16,
doi:10.4230/LIPIcs.SoCG.2021.32.
short: H. Edelsbrunner, T. Heiss, V. Kurlin , P. Smith, M. Wintraecken, in:, 37th
International Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16.
conference:
end_date: 2021-06-11
location: Virtual
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2021-06-07
date_created: 2021-04-22T08:09:58Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2023-02-23T13:55:40Z
day: '02'
ddc:
- '004'
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.32
ec_funded: 1
file:
- access_level: open_access
checksum: 1787baef1523d6d93753b90d0c109a6d
content_type: application/pdf
creator: mwintrae
date_created: 2021-04-22T08:08:14Z
date_updated: 2021-04-22T08:08:14Z
file_id: '9346'
file_name: df_socg_final_version.pdf
file_size: 3117435
relation: main_file
success: 1
file_date_updated: 2021-04-22T08:08:14Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 32:1-32:16
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
grant_number: I4887
name: Discretization in Geometry and Dynamics
- _id: 25C5A090-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00312
name: The Wittgenstein Prize
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 37th International Symposium on Computational Geometry (SoCG 2021)
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: The density fingerprint of a periodic point set
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: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...
---
_id: '9441'
abstract:
- lang: eng
text: "Isomanifolds are the generalization of isosurfaces to arbitrary dimension
and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate
multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension
of the manifold. A natural way to approximate a smooth isomanifold M is to consider
its Piecewise-Linear (PL) approximation M̂ based on a triangulation \U0001D4AF
of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace
isomanifolds from a given starting point. The algorithm works for arbitrary dimensions
n and d, and any precision D. Our main result is that, when f (or M) has bounded
complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and
unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂
is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation
of isomanifolds of bounded complexity in time polynomial in d. Combining this
algorithm with dimensionality reduction techniques, the dependency on d in the
size of M̂ can be completely removed with high probability. We also show that
the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds.
The algorithm for isomanifolds with boundary has been implemented and experimental
results are reported, showing that it is practical and can handle cases that are
far ahead of the state-of-the-art. "
acknowledgement: We thank Dominique Attali, Guilherme de Fonseca, Arijit Ghosh, Vincent
Pilaud and Aurélien Alvarez for their comments and suggestions. We also acknowledge
the reviewers.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Siargey
full_name: Kachanovich, Siargey
last_name: Kachanovich
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Boissonnat J-D, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in
time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In: 37th
International Symposium on Computational Geometry (SoCG 2021). Vol 189. Leibniz
International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2021:17:1-17:16. doi:10.4230/LIPIcs.SoCG.2021.17'
apa: 'Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Tracing
isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations.
In 37th International Symposium on Computational Geometry (SoCG 2021) (Vol.
189, p. 17:1-17:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.17'
chicago: 'Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
“Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn
Triangulations.” In 37th International Symposium on Computational Geometry
(SoCG 2021), 189:17:1-17:16. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.17.'
ieee: J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds
in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations,”
in 37th International Symposium on Computational Geometry (SoCG 2021),
Virtual, 2021, vol. 189, p. 17:1-17:16.
ista: 'Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Tracing isomanifolds
in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. 37th
International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium
on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs),
LIPIcs, vol. 189, 17:1-17:16.'
mla: Boissonnat, Jean-Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial
in d Using Coxeter-Freudenthal-Kuhn Triangulations.” 37th International Symposium
on Computational Geometry (SoCG 2021), vol. 189, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021, p. 17:1-17:16, doi:10.4230/LIPIcs.SoCG.2021.17.
short: J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, in:, 37th International
Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, Dagstuhl, Germany, 2021, p. 17:1-17:16.
conference:
end_date: 2021-06-11
location: Virtual
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2021-06-07
date_created: 2021-06-02T10:10:55Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2023-10-10T07:34:34Z
day: '02'
ddc:
- '005'
- '516'
- '514'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.17
ec_funded: 1
file:
- access_level: open_access
checksum: c322aa48d5d35a35877896cc565705b6
content_type: application/pdf
creator: mwintrae
date_created: 2021-06-02T10:22:33Z
date_updated: 2021-06-02T10:22:33Z
file_id: '9442'
file_name: LIPIcs-SoCG-2021-17.pdf
file_size: 1972902
relation: main_file
success: 1
file_date_updated: 2021-06-02T10:22:33Z
has_accepted_license: '1'
intvolume: ' 189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 17:1-17:16
place: Dagstuhl, Germany
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 37th International Symposium on Computational Geometry (SoCG 2021)
publication_identifier:
isbn:
- 978-3-95977-184-9
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '12960'
relation: later_version
status: public
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn
triangulations
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: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...
---
_id: '10052'
abstract:
- lang: eng
text: "A deterministic finite automaton (DFA) \U0001D49C is composite if its language
L(\U0001D49C) can be decomposed into an intersection ⋂_{i = 1}^k L(\U0001D49C_i)
of languages of smaller DFAs. Otherwise, \U0001D49C is prime. This notion of primality
was introduced by Kupferman and Mosheiff in 2013, and while they proved that we
can decide whether a DFA is composite, the precise complexity of this problem
is still open, with a doubly-exponential gap between the upper and lower bounds.
In this work, we focus on permutation DFAs, i.e., those for which the transition
monoid is a group. We provide an NP algorithm to decide whether a permutation
DFA is composite, and show that the difficulty of this problem comes from the
number of non-accepting states of the instance: we give a fixed-parameter tractable
algorithm with the number of rejecting states as the parameter. Moreover, we investigate
the class of commutative permutation DFAs. Their structural properties allow us
to decide compositionality in NL, and even in LOGSPACE if the alphabet size is
fixed. Despite this low complexity, we show that complex behaviors still arise
in this class: we provide a family of composite DFAs each requiring polynomially
many factors with respect to its size. We also consider the variant of the problem
that asks whether a DFA is k-factor composite, that is, decomposable into k smaller
DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation
DFAs, restricting the number of factors makes the decision computationally harder,
and yields a problem with tight bounds: it is NP-complete. Finally, we show that
in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton
alphabet."
acknowledgement: "Ismaël Jecker: Marie Skłodowska-Curie Grant Agreement No. 754411.
Nicolas Mazzocchi: BOSCO project PGC2018-102210-B-I00 (MCIU/AEI/FEDER, UE), BLOQUESCM
project S2018/TCS-4339, and MINECO grant RYC-2016-20281.\r\nPetra Wolf : DFG project
FE 560/9-1.\r\n"
alternative_title:
- LIPIcs
article_number: '18'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Nicolas
full_name: Mazzocchi, Nicolas
last_name: Mazzocchi
- first_name: Petra
full_name: Wolf, Petra
last_name: Wolf
citation:
ama: 'Jecker IR, Mazzocchi N, Wolf P. Decomposing permutation automata. In: 32nd
International Conference on Concurrency Theory. Vol 203. Schloss Dagstuhl
- Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.CONCUR.2021.18'
apa: 'Jecker, I. R., Mazzocchi, N., & Wolf, P. (2021). Decomposing permutation
automata. In 32nd International Conference on Concurrency Theory (Vol.
203). Paris, France: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2021.18'
chicago: Jecker, Ismael R, Nicolas Mazzocchi, and Petra Wolf. “Decomposing Permutation
Automata.” In 32nd International Conference on Concurrency Theory, Vol.
203. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.CONCUR.2021.18.
ieee: I. R. Jecker, N. Mazzocchi, and P. Wolf, “Decomposing permutation automata,”
in 32nd International Conference on Concurrency Theory, Paris, France,
2021, vol. 203.
ista: 'Jecker IR, Mazzocchi N, Wolf P. 2021. Decomposing permutation automata. 32nd
International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 203, 18.'
mla: Jecker, Ismael R., et al. “Decomposing Permutation Automata.” 32nd International
Conference on Concurrency Theory, vol. 203, 18, Schloss Dagstuhl - Leibniz
Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.CONCUR.2021.18.
short: I.R. Jecker, N. Mazzocchi, P. Wolf, in:, 32nd International Conference on
Concurrency Theory, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-08-27
location: Paris, France
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2021-08-23
date_created: 2021-09-27T14:33:14Z
date_published: 2021-08-13T00:00:00Z
date_updated: 2022-05-13T08:12:52Z
day: '13'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2021.18
ec_funded: 1
external_id:
arxiv:
- '2107.04683'
file:
- access_level: open_access
checksum: 4722c81be82265cf45e78adf9db91250
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-01T11:10:53Z
date_updated: 2021-10-01T11:10:53Z
file_id: '10064'
file_name: 2021_CONCUR_Jecker.pdf
file_size: 1003552
relation: main_file
success: 1
file_date_updated: 2021-10-01T11:10:53Z
has_accepted_license: '1'
intvolume: ' 203'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 32nd International Conference on Concurrency Theory
publication_identifier:
isbn:
- 978-3-9597-7203-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decomposing permutation automata
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 203
year: '2021'
...