---
_id: '14820'
abstract:
- lang: eng
text: "We consider a natural problem dealing with weighted packet selection across
a rechargeable link, which e.g., finds applications in cryptocurrency networks.
The capacity of a link (u, v) is determined by how many nodes u and v allocate
for this link. Specifically, the input is a finite ordered sequence of packets
that arrive in both directions along a link. Given (u, v) and a packet of weight
x going from u to v, node u can either accept or reject the packet. If u accepts
the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity
on \r\n increases by x. If a node rejects the packet, this will entail a cost
affinely linear in the weight of the packet. A link is “rechargeable” in the sense
that the total capacity of the link has to remain constant, but the allocation
of capacity at the ends of the link can depend arbitrarily on the nodes' decisions.
The goal is to minimise the sum of the capacity injected into the link and the
cost of rejecting packets. We show that the problem is NP-hard, but can be approximated
efficiently with a ratio of (1+E) . (1+3) for some arbitrary E>0."
acknowledgement: We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful
discussions about different variants of the problem. This work is supported by the
European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025,
the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant
470029389 (FlexNets), 2021-2024.
article_number: '114353'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links
in cryptocurrency networks: Complexity and approximation. Theoretical Computer
Science. 2024;989. doi:10.1016/j.tcs.2023.114353'
apa: 'Schmid, S., Svoboda, J., & Yeo, M. X. (2024). Weighted packet selection
for rechargeable links in cryptocurrency networks: Complexity and approximation.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.114353'
chicago: 'Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection
for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.”
Theoretical Computer Science. Elsevier, 2024. https://doi.org/10.1016/j.tcs.2023.114353.'
ieee: 'S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable
links in cryptocurrency networks: Complexity and approximation,” Theoretical
Computer Science, vol. 989. Elsevier, 2024.'
ista: 'Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable
links in cryptocurrency networks: Complexity and approximation. Theoretical Computer
Science. 989, 114353.'
mla: 'Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in
Cryptocurrency Networks: Complexity and Approximation.” Theoretical Computer
Science, vol. 989, 114353, Elsevier, 2024, doi:10.1016/j.tcs.2023.114353.'
short: S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).
corr_author: '1'
date_created: 2024-01-16T13:40:41Z
date_published: 2024-03-21T00:00:00Z
date_updated: 2025-12-02T14:02:37Z
day: '21'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1016/j.tcs.2023.114353
ec_funded: 1
external_id:
isi:
- '001168211400001'
file:
- access_level: open_access
checksum: efd5b7e738bf845312ba53889a3e13e4
content_type: application/pdf
creator: dernst
date_created: 2024-07-16T12:02:25Z
date_updated: 2024-07-16T12:02:25Z
file_id: '17263'
file_name: 2024_TheorComputerScience_Schmid.pdf
file_size: 603570
relation: main_file
success: 1
file_date_updated: 2024-07-16T12:02:25Z
has_accepted_license: '1'
intvolume: ' 989'
isi: 1
keyword:
- General Computer Science
- Theoretical Computer Science
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '19985'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Weighted packet selection for rechargeable links in cryptocurrency networks:
Complexity and approximation'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 989
year: '2024'
...
---
_id: '12164'
abstract:
- lang: eng
text: 'A shared-memory counter is a widely-used and well-studied concurrent object.
It supports two operations: An Inc operation that increases its value by 1 and
a Read operation that returns its current value. In Jayanti et al (SIAM J Comput,
30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case
step complexity of obstruction-free implementations, from read-write registers,
of a large class of shared objects that includes counters. The lower bound leaves
open the question of finding counter implementations with sub-linear amortized
step complexity. In this work, we address this gap. We show that n-process, wait-free
and linearizable counters can be implemented from read-write registers with O(log2n)
amortized step complexity. This is the first counter algorithm from read-write
registers that provides sub-linear amortized step complexity in executions of
arbitrary length. Since a logarithmic lower bound on the amortized step complexity
of obstruction-free counter implementations exists, our upper bound is within
a logarithmic factor of the optimal. The worst-case step complexity of the construction
remains linear, which is optimal. This is obtained thanks to a new max register
construction with O(logn) amortized step complexity in executions of arbitrary
length in which the value stored in the register does not grow too quickly. We
then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel
[1] in which we “plug” our max register implementation to show that it remains
linearizable while achieving O(log2n) amortized step complexity.'
acknowledgement: A preliminary version of this work appeared in DISC’19. Mirza Ahad
Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes
and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported
by the Israel Science Foundation (Grants 380/18 and 1425/22).
article_processing_charge: No
article_type: original
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Danny
full_name: Hendler, Danny
last_name: Hendler
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 2023;36:29-43. doi:10.1007/s00446-022-00439-5
apa: Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2023). Long-lived
counters with polylogarithmic amortized step complexity. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-022-00439-5
chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
“Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” Distributed
Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00439-5.
ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with
polylogarithmic amortized step complexity,” Distributed Computing, vol.
36. Springer Nature, pp. 29–43, 2023.
ista: Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 36, 29–43.
mla: Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized
Step Complexity.” Distributed Computing, vol. 36, Springer Nature, 2023,
pp. 29–43, doi:10.1007/s00446-022-00439-5.
short: M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023)
29–43.
date_created: 2023-01-12T12:10:08Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-16T08:39:36Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00446-022-00439-5
external_id:
isi:
- '000890138700001'
intvolume: ' 36'
isi: 1
keyword:
- Computational Theory and Mathematics
- Computer Networks and Communications
- Hardware and Architecture
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://drops.dagstuhl.de/opus/volltexte/2019/11310/
month: '03'
oa: 1
oa_version: Preprint
page: 29-43
publication: Distributed Computing
publication_identifier:
eissn:
- 1432-0452
issn:
- 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived counters with polylogarithmic amortized step complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '12287'
abstract:
- lang: eng
text: We present criteria for establishing a triangulation of a manifold. Given
a manifold M, a simplicial complex A, and a map H from the underlying space of
A to M, our criteria are presented in local coordinate charts for M, and ensure
that H is a homeomorphism. These criteria do not require a differentiable structure,
or even an explicit metric on M. No Delaunay property of A is assumed. The result
provides a triangulation guarantee for algorithms that construct a simplicial
complex by working in local coordinate patches. Because the criteria are easily
verified in such a setting, they are expected to be of general use.
acknowledgement: "This work has been funded by the European Research Council under
the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations
of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan
Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh
was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by
the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken
also received funding from the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian
Science Fund (FWF): M-3073. A part of the results described in this paper were presented
at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science
Fund (FWF)."
article_processing_charge: No
article_type: original
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Ramsay
full_name: Dyer, Ramsay
last_name: Dyer
- first_name: Arijit
full_name: Ghosh, Arijit
last_name: Ghosh
- 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, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating
general manifolds. Discrete & Computational Geometry. 2023;69:156-191.
doi:10.1007/s00454-022-00431-7
apa: Boissonnat, J.-D., Dyer, R., Ghosh, A., & Wintraecken, M. (2023). Local
criteria for triangulating general manifolds. Discrete & Computational
Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00431-7
chicago: Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken.
“Local Criteria for Triangulating General Manifolds.” Discrete & Computational
Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00431-7.
ieee: J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for
triangulating general manifolds,” Discrete & Computational Geometry,
vol. 69. Springer Nature, pp. 156–191, 2023.
ista: Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating
general manifolds. Discrete & Computational Geometry. 69, 156–191.
mla: Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.”
Discrete & Computational Geometry, vol. 69, Springer Nature, 2023,
pp. 156–91, doi:10.1007/s00454-022-00431-7.
short: J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete & Computational
Geometry 69 (2023) 156–191.
corr_author: '1'
date_created: 2023-01-16T10:04:06Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2025-04-14T07:44:00Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-022-00431-7
ec_funded: 1
external_id:
isi:
- '000862193600001'
file:
- access_level: open_access
checksum: 46352e0ee71e460848f88685ca852681
content_type: application/pdf
creator: dernst
date_created: 2023-02-02T11:01:10Z
date_updated: 2023-02-02T11:01:10Z
file_id: '12488'
file_name: 2023_DiscreteCompGeometry_Boissonnat.pdf
file_size: 582850
relation: main_file
success: 1
file_date_updated: 2023-02-02T11:01:10Z
has_accepted_license: '1'
intvolume: ' 69'
isi: 1
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 156-191
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local criteria for triangulating general manifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 69
year: '2023'
...
---
_id: '14778'
abstract:
- lang: eng
text: 'We consider the almost-sure (a.s.) termination problem for probabilistic
programs, which are a stochastic extension of classical imperative programs. Lexicographic
ranking functions provide a sound and practical approach for termination of non-probabilistic
programs, and their extension to probabilistic programs is achieved via lexicographic
ranking supermartingales (LexRSMs). However, LexRSMs introduced in the previous
work have a limitation that impedes their automation: all of their components
have to be non-negative in all reachable states. This might result in a LexRSM
not existing even for simple terminating programs. Our contributions are twofold.
First, we introduce a generalization of LexRSMs that allows for some components
to be negative. This standard feature of non-probabilistic termination proofs
was hitherto not known to be sound in the probabilistic setting, as the soundness
proof requires a careful analysis of the underlying stochastic process. Second,
we present polynomial-time algorithms using our generalized LexRSMs for proving
a.s. termination in broad classes of linear-arithmetic programs.'
acknowledgement: This research was partially supported by the ERC CoG (grant no. 863818;
ForM-SMArt), the Czech Science Foundation (grant no. GA21-24711S), and the European
Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie
Grant Agreement No. 665385.
article_number: '11'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ehsan
full_name: Kafshdar Goharshady, Ehsan
last_name: Kafshdar Goharshady
- first_name: Petr
full_name: Novotný, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotný
- first_name: Jiří
full_name: Zárevúcky, Jiří
last_name: Zárevúcky
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: Chatterjee K, Kafshdar Goharshady E, Novotný P, Zárevúcky J, Zikelic D. On
lexicographic proof rules for probabilistic termination. Formal Aspects of
Computing. 2023;35(2). doi:10.1145/3585391
apa: Chatterjee, K., Kafshdar Goharshady, E., Novotný, P., Zárevúcky, J., &
Zikelic, D. (2023). On lexicographic proof rules for probabilistic termination.
Formal Aspects of Computing. Association for Computing Machinery. https://doi.org/10.1145/3585391
chicago: Chatterjee, Krishnendu, Ehsan Kafshdar Goharshady, Petr Novotný, Jiří Zárevúcky,
and Dorde Zikelic. “On Lexicographic Proof Rules for Probabilistic Termination.”
Formal Aspects of Computing. Association for Computing Machinery, 2023.
https://doi.org/10.1145/3585391.
ieee: K. Chatterjee, E. Kafshdar Goharshady, P. Novotný, J. Zárevúcky, and D. Zikelic,
“On lexicographic proof rules for probabilistic termination,” Formal Aspects
of Computing, vol. 35, no. 2. Association for Computing Machinery, 2023.
ista: Chatterjee K, Kafshdar Goharshady E, Novotný P, Zárevúcky J, Zikelic D. 2023.
On lexicographic proof rules for probabilistic termination. Formal Aspects of
Computing. 35(2), 11.
mla: Chatterjee, Krishnendu, et al. “On Lexicographic Proof Rules for Probabilistic
Termination.” Formal Aspects of Computing, vol. 35, no. 2, 11, Association
for Computing Machinery, 2023, doi:10.1145/3585391.
short: K. Chatterjee, E. Kafshdar Goharshady, P. Novotný, J. Zárevúcky, D. Zikelic,
Formal Aspects of Computing 35 (2023).
corr_author: '1'
date_created: 2024-01-10T09:27:43Z
date_published: 2023-06-23T00:00:00Z
date_updated: 2025-09-09T14:19:27Z
day: '23'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1145/3585391
ec_funded: 1
external_id:
arxiv:
- '2108.02188'
isi:
- '001035915800006'
file:
- access_level: open_access
checksum: 3bb133eeb27ec01649a9a36445d952d9
content_type: application/pdf
creator: dernst
date_created: 2024-01-16T08:11:24Z
date_updated: 2024-01-16T08:11:24Z
file_id: '14804'
file_name: 2023_FormalAspectsComputing_Chatterjee.pdf
file_size: 502522
relation: main_file
success: 1
file_date_updated: 2024-01-16T08:11:24Z
has_accepted_license: '1'
intvolume: ' 35'
isi: 1
issue: '2'
keyword:
- Theoretical Computer Science
- Software
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: Formal Aspects of Computing
publication_identifier:
eissn:
- 1433-299X
issn:
- 0934-5043
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '10414'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On lexicographic proof rules for probabilistic termination
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 35
year: '2023'
...
---
_id: '12129'
abstract:
- lang: eng
text: 'Given a finite point set P in general position in the plane, a full triangulation
of P is a maximal straight-line embedded plane graph on P. A partial triangulation
of P is a full triangulation of some subset P′ of P containing all extreme points
in P. A bistellar flip on a partial triangulation either flips an edge (called
edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as
vertex of degree 3. The bistellar flip graph has all partial triangulations as
vertices, and a pair of partial triangulations is adjacent if they can be obtained
from one another by a bistellar flip. The edge flip graph is defined with full
triangulations as vertices, and edge flips determining the adjacencies. Lawson
showed in the early seventies that these graphs are connected. The goal of this
paper is to investigate the structure of these graphs, with emphasis on their
vertex connectivity. For sets P of n points in the plane in general position,
we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar
flip graph is (n−3)-vertex connected; both results are tight. The latter bound
matches the situation for the subfamily of regular triangulations (i.e., partial
triangulations obtained by lifting the points to 3-space and projecting back the
lower convex hull), where (n−3)-vertex connectivity has been known since the late
eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky
and Balinski’s Theorem. For the edge flip-graph, we additionally show that the
vertex connectivity is at least as large as (and hence equal to) the minimum degree
(i.e., the minimum number of flippable edges in any full triangulation), provided
that n is large enough. Our methods also yield several other results: (i) The
edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products
of associahedra) and the bistellar flip graph can be covered by graphs of polytopes
of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation
is regular, if it has distance n−3 in the Hasse diagram of the partial order of
partial subdivisions from the trivial subdivision. (iii) All partial triangulations
of a point set are regular iff the partial order of partial subdivisions has height
n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations
and such that every proper subset has only regular triangulations, i.e., there
are no small certificates for the existence of non-regular triangulations.'
acknowledgement: "This is a full and revised version of [38] (on partial triangulations)
in Proceedings of the 36th Annual International Symposium on Computational Geometry
(SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings
of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis
research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt,
Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on
full triangulations. Research was supported by the Swiss National Science Foundation
within the collaborative DACH project Arrangements and Drawings as SNSF Project
200021E-171681, and by IST Austria and Berlin Free University during a sabbatical
stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco
Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger
and Valentin Stoppiello for carefully reading earlier versions and for many helpful
comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology
Zürich"
article_processing_charge: No
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane.
Discrete & Computational Geometry. 2022;68(4):1227-1284. doi:10.1007/s00454-022-00436-2
apa: Wagner, U., & Welzl, E. (2022). Connectivity of triangulation flip graphs
in the plane. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00436-2
chicago: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane.” Discrete & Computational Geometry. Springer Nature,
2022. https://doi.org/10.1007/s00454-022-00436-2.
ieee: U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane,” Discrete & Computational Geometry, vol. 68, no. 4. Springer
Nature, pp. 1227–1284, 2022.
ista: Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the
plane. Discrete & Computational Geometry. 68(4), 1227–1284.
mla: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the
Plane.” Discrete & Computational Geometry, vol. 68, no. 4, Springer
Nature, 2022, pp. 1227–84, doi:10.1007/s00454-022-00436-2.
short: U. Wagner, E. Welzl, Discrete & Computational Geometry 68 (2022) 1227–1284.
corr_author: '1'
date_created: 2023-01-12T12:02:28Z
date_published: 2022-11-14T00:00:00Z
date_updated: 2025-07-10T11:54:56Z
day: '14'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00436-2
external_id:
isi:
- '000883222200003'
file:
- access_level: open_access
checksum: 307e879d09e52eddf5b225d0aaa9213a
content_type: application/pdf
creator: dernst
date_created: 2023-01-23T11:10:03Z
date_updated: 2023-01-23T11:10:03Z
file_id: '12345'
file_name: 2022_DiscreteCompGeometry_Wagner.pdf
file_size: 1747581
relation: main_file
success: 1
file_date_updated: 2023-01-23T11:10:03Z
has_accepted_license: '1'
intvolume: ' 68'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1227-1284
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '7807'
relation: earlier_version
status: public
- id: '7990'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Connectivity of triangulation flip graphs in the plane
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '12148'
abstract:
- lang: eng
text: 'We prove a general local law for Wigner matrices that optimally handles observables
of arbitrary rank and thus unifies the well-known averaged and isotropic local
laws. As an application, we prove a central limit theorem in quantum unique ergodicity
(QUE): that is, we show that the quadratic forms of a general deterministic matrix
A on the bulk eigenvectors of a Wigner matrix have approximately Gaussian fluctuation.
For the bulk spectrum, we thus generalise our previous result [17] as valid for
test matrices A of large rank as well as the result of Benigni and Lopatto [7]
as valid for specific small-rank observables.'
acknowledgement: L.E. acknowledges support by ERC Advanced Grant ‘RMTBeyond’ No. 101020331.
D.S. acknowledges the support of Dr. Max Rössler, the Walter Haefner Foundation
and the ETH Zürich Foundation.
article_number: e96
article_processing_charge: No
article_type: original
author:
- first_name: Giorgio
full_name: Cipolloni, Giorgio
id: 42198EFA-F248-11E8-B48F-1D18A9856A87
last_name: Cipolloni
orcid: 0000-0002-4901-7992
- first_name: László
full_name: Erdös, László
id: 4DBD5372-F248-11E8-B48F-1D18A9856A87
last_name: Erdös
orcid: 0000-0001-5366-9603
- first_name: Dominik J
full_name: Schröder, Dominik J
id: 408ED176-F248-11E8-B48F-1D18A9856A87
last_name: Schröder
orcid: 0000-0002-2904-1856
citation:
ama: Cipolloni G, Erdös L, Schröder DJ. Rank-uniform local law for Wigner matrices.
Forum of Mathematics, Sigma. 2022;10. doi:10.1017/fms.2022.86
apa: Cipolloni, G., Erdös, L., & Schröder, D. J. (2022). Rank-uniform local
law for Wigner matrices. Forum of Mathematics, Sigma. Cambridge University
Press. https://doi.org/10.1017/fms.2022.86
chicago: Cipolloni, Giorgio, László Erdös, and Dominik J Schröder. “Rank-Uniform
Local Law for Wigner Matrices.” Forum of Mathematics, Sigma. Cambridge
University Press, 2022. https://doi.org/10.1017/fms.2022.86.
ieee: G. Cipolloni, L. Erdös, and D. J. Schröder, “Rank-uniform local law for Wigner
matrices,” Forum of Mathematics, Sigma, vol. 10. Cambridge University Press,
2022.
ista: Cipolloni G, Erdös L, Schröder DJ. 2022. Rank-uniform local law for Wigner
matrices. Forum of Mathematics, Sigma. 10, e96.
mla: Cipolloni, Giorgio, et al. “Rank-Uniform Local Law for Wigner Matrices.” Forum
of Mathematics, Sigma, vol. 10, e96, Cambridge University Press, 2022, doi:10.1017/fms.2022.86.
short: G. Cipolloni, L. Erdös, D.J. Schröder, Forum of Mathematics, Sigma 10 (2022).
corr_author: '1'
date_created: 2023-01-12T12:07:30Z
date_published: 2022-10-27T00:00:00Z
date_updated: 2025-04-14T07:57:18Z
day: '27'
ddc:
- '510'
department:
- _id: LaEr
doi: 10.1017/fms.2022.86
ec_funded: 1
external_id:
isi:
- '000873719200001'
file:
- access_level: open_access
checksum: 94a049aeb1eea5497aa097712a73c400
content_type: application/pdf
creator: dernst
date_created: 2023-01-24T10:02:40Z
date_updated: 2023-01-24T10:02:40Z
file_id: '12356'
file_name: 2022_ForumMath_Cipolloni.pdf
file_size: 817089
relation: main_file
success: 1
file_date_updated: 2023-01-24T10:02:40Z
has_accepted_license: '1'
intvolume: ' 10'
isi: 1
keyword:
- Computational Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Mathematical Physics
- Statistics and Probability
- Algebra and Number Theory
- Theoretical Computer Science
- Analysis
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 62796744-2b32-11ec-9570-940b20777f1d
call_identifier: H2020
grant_number: '101020331'
name: Random matrices beyond Wigner-Dyson-Mehta
publication: Forum of Mathematics, Sigma
publication_identifier:
issn:
- 2050-5094
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Rank-uniform local law for Wigner matrices
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 10
year: '2022'
...
---
_id: '12286'
abstract:
- lang: eng
text: "Inspired by the study of loose cycles in hypergraphs, we define the loose
core in hypergraphs as a structurewhich mirrors the close relationship between
cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random
hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition
at a certain critical threshold and determine this order, as well as the number
of edges, asymptotically in the subcritical and supercritical regimes.
\r\nOur
main tool is an algorithm called CoreConstruct, which enables us to analyse a
peeling process for the loose core. By analysing this algorithm we determine the
asymptotic degree distribution of vertices in the loose core and in particular
how many vertices and edges the loose core contains. As a corollary we obtain
an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$."
acknowledgement: 'Supported by Austrian Science Fund (FWF): I3747, W1230.'
article_number: P4.13
article_processing_charge: No
article_type: original
author:
- first_name: Oliver
full_name: Cooley, Oliver
id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
last_name: Cooley
- first_name: Mihyun
full_name: Kang, Mihyun
last_name: Kang
- first_name: Julian
full_name: Zalla, Julian
last_name: Zalla
citation:
ama: Cooley O, Kang M, Zalla J. Loose cores and cycles in random hypergraphs. The
Electronic Journal of Combinatorics. 2022;29(4). doi:10.37236/10794
apa: Cooley, O., Kang, M., & Zalla, J. (2022). Loose cores and cycles in random
hypergraphs. The Electronic Journal of Combinatorics. The Electronic Journal
of Combinatorics. https://doi.org/10.37236/10794
chicago: Cooley, Oliver, Mihyun Kang, and Julian Zalla. “Loose Cores and Cycles
in Random Hypergraphs.” The Electronic Journal of Combinatorics. The Electronic
Journal of Combinatorics, 2022. https://doi.org/10.37236/10794.
ieee: O. Cooley, M. Kang, and J. Zalla, “Loose cores and cycles in random hypergraphs,”
The Electronic Journal of Combinatorics, vol. 29, no. 4. The Electronic
Journal of Combinatorics, 2022.
ista: Cooley O, Kang M, Zalla J. 2022. Loose cores and cycles in random hypergraphs.
The Electronic Journal of Combinatorics. 29(4), P4.13.
mla: Cooley, Oliver, et al. “Loose Cores and Cycles in Random Hypergraphs.” The
Electronic Journal of Combinatorics, vol. 29, no. 4, P4.13, The Electronic
Journal of Combinatorics, 2022, doi:10.37236/10794.
short: O. Cooley, M. Kang, J. Zalla, The Electronic Journal of Combinatorics 29
(2022).
date_created: 2023-01-16T10:03:57Z
date_published: 2022-10-21T00:00:00Z
date_updated: 2023-08-04T10:29:18Z
day: '21'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/10794
external_id:
isi:
- '000876763300001'
file:
- access_level: open_access
checksum: 00122b2459f09b5ae43073bfba565e94
content_type: application/pdf
creator: dernst
date_created: 2023-01-30T11:45:13Z
date_updated: 2023-01-30T11:45:13Z
file_id: '12462'
file_name: 2022_ElecJournCombinatorics_Cooley_Kang_Zalla.pdf
file_size: 626953
relation: main_file
success: 1
file_date_updated: 2023-01-30T11:45:13Z
has_accepted_license: '1'
intvolume: ' 29'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Geometry and Topology
- Theoretical Computer Science
- Applied Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '10'
oa: 1
oa_version: Published Version
publication: The Electronic Journal of Combinatorics
publication_identifier:
eissn:
- 1077-8926
publication_status: published
publisher: The Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Loose cores and cycles in random hypergraphs
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 29
year: '2022'
...
---
_id: '10643'
abstract:
- lang: eng
text: "We prove a generalised super-adiabatic theorem for extended fermionic systems
assuming a spectral gap only in the bulk. More precisely, we assume that the infinite
system has a unique ground state and that the corresponding Gelfand–Naimark–Segal
Hamiltonian has a spectral gap above its eigenvalue zero. Moreover, we show that
a similar adiabatic theorem also holds in the bulk of finite systems up to errors
that vanish faster than any inverse power of the system size, although the corresponding
finite-volume Hamiltonians need not have a spectral gap.\r\n\r\n"
acknowledgement: J.H. acknowledges partial financial support by the ERC Advanced Grant
‘RMTBeyond’ No. 101020331. Support for publication costs from the Deutsche Forschungsgemeinschaft
and the Open Access Publishing Fund of the University of Tübingen is gratefully
acknowledged.
article_number: e4
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Sven Joscha
full_name: Henheik, Sven Joscha
id: 31d731d7-d235-11ea-ad11-b50331c8d7fb
last_name: Henheik
orcid: 0000-0003-1106-327X
- first_name: Stefan
full_name: Teufel, Stefan
last_name: Teufel
citation:
ama: 'Henheik SJ, Teufel S. Adiabatic theorem in the thermodynamic limit: Systems
with a gap in the bulk. Forum of Mathematics, Sigma. 2022;10. doi:10.1017/fms.2021.80'
apa: 'Henheik, S. J., & Teufel, S. (2022). Adiabatic theorem in the thermodynamic
limit: Systems with a gap in the bulk. Forum of Mathematics, Sigma. Cambridge
University Press. https://doi.org/10.1017/fms.2021.80'
chicago: 'Henheik, Sven Joscha, and Stefan Teufel. “Adiabatic Theorem in the Thermodynamic
Limit: Systems with a Gap in the Bulk.” Forum of Mathematics, Sigma. Cambridge
University Press, 2022. https://doi.org/10.1017/fms.2021.80.'
ieee: 'S. J. Henheik and S. Teufel, “Adiabatic theorem in the thermodynamic limit:
Systems with a gap in the bulk,” Forum of Mathematics, Sigma, vol. 10.
Cambridge University Press, 2022.'
ista: 'Henheik SJ, Teufel S. 2022. Adiabatic theorem in the thermodynamic limit:
Systems with a gap in the bulk. Forum of Mathematics, Sigma. 10, e4.'
mla: 'Henheik, Sven Joscha, and Stefan Teufel. “Adiabatic Theorem in the Thermodynamic
Limit: Systems with a Gap in the Bulk.” Forum of Mathematics, Sigma, vol.
10, e4, Cambridge University Press, 2022, doi:10.1017/fms.2021.80.'
short: S.J. Henheik, S. Teufel, Forum of Mathematics, Sigma 10 (2022).
corr_author: '1'
date_created: 2022-01-18T16:18:51Z
date_published: 2022-01-18T00:00:00Z
date_updated: 2025-04-14T07:57:17Z
day: '18'
ddc:
- '510'
department:
- _id: GradSch
- _id: LaEr
doi: 10.1017/fms.2021.80
ec_funded: 1
external_id:
arxiv:
- '2012.15239'
isi:
- '000743615000001'
file:
- access_level: open_access
checksum: 87592a755adcef22ea590a99dc728dd3
content_type: application/pdf
creator: cchlebak
date_created: 2022-01-19T09:27:43Z
date_updated: 2022-01-19T09:27:43Z
file_id: '10646'
file_name: 2022_ForumMathSigma_Henheik.pdf
file_size: 705323
relation: main_file
success: 1
file_date_updated: 2022-01-19T09:27:43Z
has_accepted_license: '1'
intvolume: ' 10'
isi: 1
keyword:
- computational mathematics
- discrete mathematics and combinatorics
- geometry and topology
- mathematical physics
- statistics and probability
- algebra and number theory
- theoretical computer science
- analysis
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 62796744-2b32-11ec-9570-940b20777f1d
call_identifier: H2020
grant_number: '101020331'
name: Random matrices beyond Wigner-Dyson-Mehta
publication: Forum of Mathematics, Sigma
publication_identifier:
eissn:
- 2050-5094
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 10
year: '2022'
...
---
_id: '11446'
abstract:
- lang: eng
text: Suppose that n is not a prime power and not twice a prime power. We prove
that for any Hausdorff compactum X with a free action of the symmetric group Sn,
there exists an Sn-equivariant map X→Rn whose image avoids the diagonal {(x,x,…,x)∈Rn∣x∈R}.
Previously, the special cases of this statement for certain X were usually proved
using the equivartiant obstruction theory. Such calculations are difficult and
may become infeasible past the first (primary) obstruction. We take a different
approach which allows us to prove the vanishing of all obstructions simultaneously.
The essential step in the proof is classifying the possible degrees of Sn-equivariant
maps from the boundary ∂Δn−1 of (n−1)-simplex to itself. Existence of equivariant
maps between spaces is important for many questions arising from discrete mathematics
and geometry, such as Kneser’s conjecture, the Square Peg conjecture, the Splitting
Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate
the utility of our result applying it to one such question, a specific instance
of envy-free division problem.
acknowledgement: S. Avvakumov has received funding from the European Research Council
under the European Union’s Seventh Framework Programme ERC Grant agreement ERC StG
716424–CASe. S. Kudrya was supported by the Austrian Academic Exchange Service (OeAD),
ICM-2019-13577.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
orcid: 0000-0002-7840-5062
- first_name: Sergey
full_name: Kudrya, Sergey
id: ecf01965-d252-11ea-95a5-8ada5f6c6a67
last_name: Kudrya
citation:
ama: Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping
degree. Discrete & Computational Geometry. 2021;66(3):1202-1216. doi:10.1007/s00454-021-00299-z
apa: Avvakumov, S., & Kudrya, S. (2021). Vanishing of all equivariant obstructions
and the mapping degree. Discrete & Computational Geometry. Springer
Nature. https://doi.org/10.1007/s00454-021-00299-z
chicago: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
and the Mapping Degree.” Discrete & Computational Geometry. Springer
Nature, 2021. https://doi.org/10.1007/s00454-021-00299-z.
ieee: S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and
the mapping degree,” Discrete & Computational Geometry, vol. 66, no.
3. Springer Nature, pp. 1202–1216, 2021.
ista: Avvakumov S, Kudrya S. 2021. Vanishing of all equivariant obstructions and
the mapping degree. Discrete & Computational Geometry. 66(3), 1202–1216.
mla: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
and the Mapping Degree.” Discrete & Computational Geometry, vol. 66,
no. 3, Springer Nature, 2021, pp. 1202–16, doi:10.1007/s00454-021-00299-z.
short: S. Avvakumov, S. Kudrya, Discrete & Computational Geometry 66 (2021)
1202–1216.
corr_author: '1'
date_created: 2022-06-17T08:45:15Z
date_published: 2021-10-01T00:00:00Z
date_updated: 2025-04-14T09:10:06Z
day: '01'
doi: 10.1007/s00454-021-00299-z
extern: '1'
external_id:
arxiv:
- '1910.12628'
intvolume: ' 66'
issue: '3'
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '10'
oa_version: Preprint
page: 1202-1216
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '8182'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Vanishing of all equivariant obstructions and the mapping degree
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2021'
...
---
_id: '8940'
abstract:
- lang: eng
text: We quantise Whitney’s construction to prove the existence of a triangulation
for any C^2 manifold, so that we get an algorithm with explicit bounds. We also
give a new elementary proof, which is completely geometric.
acknowledgement: This work has been funded by the European Research Council under
the European Union’s ERC Grant Agreement Number 339025 GUDHI (Algorithmic Foundations
of Geometric Understanding in Higher Dimensions). The third author also received
funding from the European Union’s Horizon 2020 research and innovation programme
under the Marie Skłodowska-Curie Grant Agreement No. 754411. Open access funding
provided by the Institute of Science and Technology (IST Austria).
article_processing_charge: Yes (via OA deal)
article_type: original
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. Triangulating submanifolds:
An elementary and quantified version of Whitney’s method. Discrete & Computational
Geometry. 2021;66(1):386-434. doi:10.1007/s00454-020-00250-8'
apa: 'Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Triangulating
submanifolds: An elementary and quantified version of Whitney’s method. Discrete
& Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00250-8'
chicago: 'Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
“Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s
Method.” Discrete & Computational Geometry. Springer Nature, 2021.
https://doi.org/10.1007/s00454-020-00250-8.'
ieee: 'J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Triangulating submanifolds:
An elementary and quantified version of Whitney’s method,” Discrete & Computational
Geometry, vol. 66, no. 1. Springer Nature, pp. 386–434, 2021.'
ista: 'Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Triangulating submanifolds:
An elementary and quantified version of Whitney’s method. Discrete & Computational
Geometry. 66(1), 386–434.'
mla: 'Boissonnat, Jean-Daniel, et al. “Triangulating Submanifolds: An Elementary
and Quantified Version of Whitney’s Method.” Discrete & Computational Geometry,
vol. 66, no. 1, Springer Nature, 2021, pp. 386–434, doi:10.1007/s00454-020-00250-8.'
short: J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete & Computational
Geometry 66 (2021) 386–434.
corr_author: '1'
date_created: 2020-12-12T11:07:02Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2025-04-14T07:43:50Z
day: '01'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00250-8
ec_funded: 1
external_id:
isi:
- '000597770300001'
file:
- access_level: open_access
checksum: c848986091e56699dc12de85adb1e39c
content_type: application/pdf
creator: kschuh
date_created: 2021-08-06T09:52:29Z
date_updated: 2021-08-06T09:52:29Z
file_id: '9795'
file_name: 2021_DescreteCompGeopmetry_Boissonnat.pdf
file_size: 983307
relation: main_file
success: 1
file_date_updated: 2021-08-06T09:52:29Z
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
issue: '1'
keyword:
- Theoretical Computer Science
- Computational Theory and Mathematics
- Geometry and Topology
- Discrete Mathematics and Combinatorics
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 386-434
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Triangulating submanifolds: An elementary and quantified version of Whitney’s
method'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2021'
...
---
_id: '11657'
abstract:
- lang: eng
text: The minimum cut problem for an undirected edge-weighted graph asks us to divide
its set of nodes into two blocks while minimizing the weight sum of the cut edges.
Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm
is based on cluster contraction using label propagation and Padberg and Rinaldi’s
contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory
parallel implementations of our algorithm. Extensive experiments on both real-world
and generated instances show that our algorithm finds the optimal cut on nearly
all instances significantly faster than other state-of-the-art exact algorithms,
and our error rate is lower than that of other heuristic algorithms. In addition,
our parallel algorithm runs a factor 7.5× faster on average when using 32 threads.
To further speed up computations, we also give a version of our algorithm that
performs random edge contractions as preprocessing. This version achieves a lower
running time and better parallel scalability at the expense of a higher error
rate.
article_processing_charge: No
article_type: original
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: Alexander
full_name: Noe, Alexander
last_name: Noe
- first_name: Christian
full_name: Schulz, Christian
last_name: Schulz
- first_name: Darren
full_name: Strash, Darren
last_name: Strash
citation:
ama: Henzinger M, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. ACM
Journal of Experimental Algorithmics. 2018;23:1-22. doi:10.1145/3274662
apa: Henzinger, M., Noe, A., Schulz, C., & Strash, D. (2018). Practical minimum
cut algorithms. ACM Journal of Experimental Algorithmics. Association for
Computing Machinery. https://doi.org/10.1145/3274662
chicago: Henzinger, Monika, Alexander Noe, Christian Schulz, and Darren Strash.
“Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics.
Association for Computing Machinery, 2018. https://doi.org/10.1145/3274662.
ieee: M. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,”
ACM Journal of Experimental Algorithmics, vol. 23. Association for Computing
Machinery, pp. 1–22, 2018.
ista: Henzinger M, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms.
ACM Journal of Experimental Algorithmics. 23, 1–22.
mla: Henzinger, Monika, et al. “Practical Minimum Cut Algorithms.” ACM Journal
of Experimental Algorithmics, vol. 23, Association for Computing Machinery,
2018, pp. 1–22, doi:10.1145/3274662.
short: M. Henzinger, A. Noe, C. Schulz, D. Strash, ACM Journal of Experimental Algorithmics
23 (2018) 1–22.
date_created: 2022-07-27T08:28:26Z
date_published: 2018-10-01T00:00:00Z
date_updated: 2024-11-06T12:05:24Z
day: '01'
doi: 10.1145/3274662
extern: '1'
external_id:
arxiv:
- '1708.06127'
intvolume: ' 23'
keyword:
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.06127
month: '10'
oa: 1
oa_version: Preprint
page: 1-22
publication: ACM Journal of Experimental Algorithmics
publication_identifier:
eissn:
- 1084-6654
issn:
- 1084-6654
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical minimum cut algorithms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2018'
...
---
_id: '8509'
abstract:
- lang: eng
text: The goal of this paper is to present to nonspecialists what is perhaps the
simplest possible geometrical picture explaining the mechanism of Arnold diffusion.
We choose to speak of a specific model—that of geometric rays in a periodic optical
medium. This model is equivalent to that of a particle in a periodic potential
in ${\mathbb R}^{n}$ with energy prescribed and to the geodesic flow in a Riemannian
metric on ${\mathbb R}^{n} $.
article_processing_charge: No
article_type: original
author:
- first_name: Vadim
full_name: Kaloshin, Vadim
id: FE553552-CDE8-11E9-B324-C0EBE5697425
last_name: Kaloshin
orcid: 0000-0002-6051-2628
- first_name: Mark
full_name: Levi, Mark
last_name: Levi
citation:
ama: Kaloshin V, Levi M. Geometry of Arnold diffusion. SIAM Review. 2008;50(4):702-720.
doi:10.1137/070703235
apa: Kaloshin, V., & Levi, M. (2008). Geometry of Arnold diffusion. SIAM
Review. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/070703235
chicago: Kaloshin, Vadim, and Mark Levi. “Geometry of Arnold Diffusion.” SIAM
Review. Society for Industrial & Applied Mathematics, 2008. https://doi.org/10.1137/070703235.
ieee: V. Kaloshin and M. Levi, “Geometry of Arnold diffusion,” SIAM Review,
vol. 50, no. 4. Society for Industrial & Applied Mathematics, pp. 702–720,
2008.
ista: Kaloshin V, Levi M. 2008. Geometry of Arnold diffusion. SIAM Review. 50(4),
702–720.
mla: Kaloshin, Vadim, and Mark Levi. “Geometry of Arnold Diffusion.” SIAM Review,
vol. 50, no. 4, Society for Industrial & Applied Mathematics, 2008, pp. 702–20,
doi:10.1137/070703235.
short: V. Kaloshin, M. Levi, SIAM Review 50 (2008) 702–720.
date_created: 2020-09-18T10:48:12Z
date_published: 2008-11-05T00:00:00Z
date_updated: 2021-01-12T08:19:46Z
day: '05'
doi: 10.1137/070703235
extern: '1'
intvolume: ' 50'
issue: '4'
keyword:
- Theoretical Computer Science
- Applied Mathematics
- Computational Mathematics
language:
- iso: eng
month: '11'
oa_version: None
page: 702-720
publication: SIAM Review
publication_identifier:
issn:
- 0036-1445
- 1095-7200
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
status: public
title: Geometry of Arnold diffusion
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2008'
...