---
_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: '10842'
abstract:
- lang: eng
text: We determine the unique factorization of some polynomials over a finite local
commutative ring with identity explicitly. This solves and generalizes the main
conjecture of Qian, Shi and Solé in [13]. We also give some applications to enumeration
of certain generalized double circulant self-dual and linear complementary dual
(LCD) codes over some finite rings together with an application in asymptotic
coding theory.
acknowledgement: The authors would like to thank Prof. Dr. Minjia Shi for bringing
[13, Conjecture 3.5] to our attention. We would also like to thank the associate
editor and anonymous reviewers for their valuable comments and suggestions which
improved and clarified the manuscript.
article_processing_charge: No
article_type: original
author:
- first_name: Seyda
full_name: Köse, Seyda
id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb
last_name: Köse
- first_name: Ferruh
full_name: Özbudak, Ferruh
last_name: Özbudak
citation:
ama: Köse S, Özbudak F. Factorization of some polynomials over finite local commutative
rings and applications to certain self-dual and LCD codes. Cryptography and
Communications. 2022;14(4):933-948. doi:10.1007/s12095-022-00557-8
apa: Köse, S., & Özbudak, F. (2022). Factorization of some polynomials over
finite local commutative rings and applications to certain self-dual and LCD codes.
Cryptography and Communications. Springer Nature. https://doi.org/10.1007/s12095-022-00557-8
chicago: Köse, Seyda, and Ferruh Özbudak. “Factorization of Some Polynomials over
Finite Local Commutative Rings and Applications to Certain Self-Dual and LCD Codes.”
Cryptography and Communications. Springer Nature, 2022. https://doi.org/10.1007/s12095-022-00557-8.
ieee: S. Köse and F. Özbudak, “Factorization of some polynomials over finite local
commutative rings and applications to certain self-dual and LCD codes,” Cryptography
and Communications, vol. 14, no. 4. Springer Nature, pp. 933–948, 2022.
ista: Köse S, Özbudak F. 2022. Factorization of some polynomials over finite local
commutative rings and applications to certain self-dual and LCD codes. Cryptography
and Communications. 14(4), 933–948.
mla: Köse, Seyda, and Ferruh Özbudak. “Factorization of Some Polynomials over Finite
Local Commutative Rings and Applications to Certain Self-Dual and LCD Codes.”
Cryptography and Communications, vol. 14, no. 4, Springer Nature, 2022,
pp. 933–48, doi:10.1007/s12095-022-00557-8.
short: S. Köse, F. Özbudak, Cryptography and Communications 14 (2022) 933–948.
date_created: 2022-03-10T12:16:19Z
date_published: 2022-07-01T00:00:00Z
date_updated: 2023-09-05T15:35:55Z
day: '01'
department:
- _id: GradSch
doi: 10.1007/s12095-022-00557-8
external_id:
isi:
- '000766422000002'
intvolume: ' 14'
isi: 1
issue: '4'
keyword:
- Applied Mathematics
- Computational Theory and Mathematics
- Computer Networks and Communications
language:
- iso: eng
month: '07'
oa_version: None
page: 933-948
publication: Cryptography and Communications
publication_identifier:
eissn:
- 1936-2455
issn:
- 1936-2447
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Factorization of some polynomials over finite local commutative rings and applications
to certain self-dual and LCD codes
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 14
year: '2022'
...
---
_id: '10602'
abstract:
- lang: eng
text: Transforming ω-automata into parity automata is traditionally done using appearance
records. We present an efficient variant of this idea, tailored to Rabin automata,
and several optimizations applicable to all appearance records. We compare the
methods experimentally and show that our method produces significantly smaller
automata than previous approaches.
acknowledgement: This work is partially funded by the German Research Foundation (DFG)
projects Verified Model Checkers (No. 317422601) and Statistical Unbounded Verification
(No. 383882557), and the Alexander von Humboldt Foundation with funds from the German
Federal Ministry of Education and Research. It is an extended version of [21], including
all proofs together with further explanations and examples. Moreover, we provide
a new, more efficient construction based on (total) preorders, unifying previous
optimizations. Experiments are performed with a new, performant implementation,
comparing our approach to the current state of the art.
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- 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: Clara
full_name: Waldmann, Clara
last_name: Waldmann
- first_name: Maximilian
full_name: Weininger, Maximilian
last_name: Weininger
citation:
ama: Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. Index appearance record
with preorders. Acta Informatica. 2022;59:585-618. doi:10.1007/s00236-021-00412-y
apa: Kretinsky, J., Meggendorfer, T., Waldmann, C., & Weininger, M. (2022).
Index appearance record with preorders. Acta Informatica. Springer Nature.
https://doi.org/10.1007/s00236-021-00412-y
chicago: Kretinsky, Jan, Tobias Meggendorfer, Clara Waldmann, and Maximilian Weininger.
“Index Appearance Record with Preorders.” Acta Informatica. Springer Nature,
2022. https://doi.org/10.1007/s00236-021-00412-y.
ieee: J. Kretinsky, T. Meggendorfer, C. Waldmann, and M. Weininger, “Index appearance
record with preorders,” Acta Informatica, vol. 59. Springer Nature, pp.
585–618, 2022.
ista: Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2022. Index appearance
record with preorders. Acta Informatica. 59, 585–618.
mla: Kretinsky, Jan, et al. “Index Appearance Record with Preorders.” Acta Informatica,
vol. 59, Springer Nature, 2022, pp. 585–618, doi:10.1007/s00236-021-00412-y.
short: J. Kretinsky, T. Meggendorfer, C. Waldmann, M. Weininger, Acta Informatica
59 (2022) 585–618.
date_created: 2022-01-06T12:37:27Z
date_published: 2022-10-01T00:00:00Z
date_updated: 2023-08-02T13:49:28Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/s00236-021-00412-y
external_id:
isi:
- '000735765500001'
file:
- access_level: open_access
checksum: bf1c195b6aaf59e8530cf9e3a9d731f7
content_type: application/pdf
creator: cchlebak
date_created: 2022-01-07T07:50:31Z
date_updated: 2022-01-07T07:50:31Z
file_id: '10603'
file_name: 2021_ActaInfor_Křetínský.pdf
file_size: 1066082
relation: main_file
success: 1
file_date_updated: 2022-01-07T07:50:31Z
has_accepted_license: '1'
intvolume: ' 59'
isi: 1
keyword:
- computer networks and communications
- information systems
- software
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 585-618
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Acta Informatica
publication_identifier:
eissn:
- 1432-0525
issn:
- 0001-5903
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Index appearance record with preorders
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: 59
year: '2022'
...
---
_id: '12134'
abstract:
- lang: eng
text: Standard epidemic models exhibit one continuous, second order phase transition
to macroscopic outbreaks. However, interventions to control outbreaks may fundamentally
alter epidemic dynamics. Here we reveal how such interventions modify the type
of phase transition. In particular, we uncover three distinct types of explosive
phase transitions for epidemic dynamics with capacity-limited interventions. Depending
on the capacity limit, interventions may (i) leave the standard second order phase
transition unchanged but exponentially suppress the probability of large outbreaks,
(ii) induce a first-order discontinuous transition to macroscopic outbreaks, or
(iii) cause a secondary explosive yet continuous third-order transition. These
insights highlight inherent limitations in predicting and containing epidemic
outbreaks. More generally our study offers a cornerstone example of a third-order
explosive phase transition in complex systems.
acknowledgement: We acknowledge support from the Volkswagen Foundation under Grant
No. 99720 and the German Federal Ministry for Education and Research (BMBF) under
Grant No. 16ICR01. This research was supported by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) under Germany’s Excellence Strategy—EXC-2068—390729961—Cluster
of Excellence Physics of Life of TU Dresden.
article_number: 04LT02
article_processing_charge: No
article_type: original
author:
- first_name: Georg
full_name: Börner, Georg
last_name: Börner
- first_name: Malte
full_name: Schröder, Malte
last_name: Schröder
- first_name: Davide
full_name: Scarselli, Davide
id: 40315C30-F248-11E8-B48F-1D18A9856A87
last_name: Scarselli
orcid: 0000-0001-5227-4271
- first_name: Nazmi B
full_name: Budanur, Nazmi B
id: 3EA1010E-F248-11E8-B48F-1D18A9856A87
last_name: Budanur
orcid: 0000-0003-0423-5010
- first_name: Björn
full_name: Hof, Björn
id: 3A374330-F248-11E8-B48F-1D18A9856A87
last_name: Hof
orcid: 0000-0003-2057-2754
- first_name: Marc
full_name: Timme, Marc
last_name: Timme
citation:
ama: 'Börner G, Schröder M, Scarselli D, Budanur NB, Hof B, Timme M. Explosive transitions
in epidemic dynamics. Journal of Physics: Complexity. 2022;3(4). doi:10.1088/2632-072x/ac99cd'
apa: 'Börner, G., Schröder, M., Scarselli, D., Budanur, N. B., Hof, B., & Timme,
M. (2022). Explosive transitions in epidemic dynamics. Journal of Physics:
Complexity. IOP Publishing. https://doi.org/10.1088/2632-072x/ac99cd'
chicago: 'Börner, Georg, Malte Schröder, Davide Scarselli, Nazmi B Budanur, Björn
Hof, and Marc Timme. “Explosive Transitions in Epidemic Dynamics.” Journal
of Physics: Complexity. IOP Publishing, 2022. https://doi.org/10.1088/2632-072x/ac99cd.'
ieee: 'G. Börner, M. Schröder, D. Scarselli, N. B. Budanur, B. Hof, and M. Timme,
“Explosive transitions in epidemic dynamics,” Journal of Physics: Complexity,
vol. 3, no. 4. IOP Publishing, 2022.'
ista: 'Börner G, Schröder M, Scarselli D, Budanur NB, Hof B, Timme M. 2022. Explosive
transitions in epidemic dynamics. Journal of Physics: Complexity. 3(4), 04LT02.'
mla: 'Börner, Georg, et al. “Explosive Transitions in Epidemic Dynamics.” Journal
of Physics: Complexity, vol. 3, no. 4, 04LT02, IOP Publishing, 2022, doi:10.1088/2632-072x/ac99cd.'
short: 'G. Börner, M. Schröder, D. Scarselli, N.B. Budanur, B. Hof, M. Timme, Journal
of Physics: Complexity 3 (2022).'
date_created: 2023-01-12T12:03:43Z
date_published: 2022-10-25T00:00:00Z
date_updated: 2023-02-13T09:15:13Z
day: '25'
ddc:
- '530'
department:
- _id: BjHo
doi: 10.1088/2632-072x/ac99cd
file:
- access_level: open_access
checksum: 35c5c5cb0eb17ea1b5184755daab9fc9
content_type: application/pdf
creator: dernst
date_created: 2023-01-24T07:24:37Z
date_updated: 2023-01-24T07:24:37Z
file_id: '12350'
file_name: 2022_JourPhysics_Boerner.pdf
file_size: 1006106
relation: main_file
success: 1
file_date_updated: 2023-01-24T07:24:37Z
has_accepted_license: '1'
intvolume: ' 3'
issue: '4'
keyword:
- Artificial Intelligence
- Computer Networks and Communications
- Computer Science Applications
- Information Systems
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: 'Journal of Physics: Complexity'
publication_identifier:
issn:
- 2632-072X
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: Explosive transitions in epidemic dynamics
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3
year: '2022'
...
---
_id: '12147'
abstract:
- lang: eng
text: Continuous-time neural networks are a class of machine learning systems that
can tackle representation learning on spatiotemporal decision-making tasks. These
models are typically represented by continuous differential equations. However,
their expressive power when they are deployed on computers is bottlenecked by
numerical differential equation solvers. This limitation has notably slowed down
the scaling and understanding of numerous natural physical phenomena such as the
dynamics of nervous systems. Ideally, we would circumvent this bottleneck by solving
the given dynamical system in closed form. This is known to be intractable in
general. Here, we show that it is possible to closely approximate the interaction
between neurons and synapses—the building blocks of natural and artificial neural
networks—constructed by liquid time-constant networks efficiently in closed form.
To this end, we compute a tightly bounded approximation of the solution of an
integral appearing in liquid time-constant dynamics that has had no known closed-form
solution so far. This closed-form solution impacts the design of continuous-time
and continuous-depth neural models. For instance, since time appears explicitly
in closed form, the formulation relaxes the need for complex numerical solvers.
Consequently, we obtain models that are between one and five orders of magnitude
faster in training and inference compared with differential equation-based counterparts.
More importantly, in contrast to ordinary differential equation-based continuous
networks, closed-form networks can scale remarkably well compared with other deep
learning instances. Lastly, as these models are derived from liquid networks,
they show good performance in time-series modelling compared with advanced recurrent
neural network models.
acknowledgement: This research was supported in part by the AI2050 program at Schmidt
Futures (grant G-22-63172), the Boeing Company, and the United States Air Force
Research Laboratory and the United States Air Force Artificial Intelligence Accelerator
and was accomplished under cooperative agreement number FA8750-19-2-1000. The views
and conclusions contained in this document are those of the authors and should not
be interpreted as representing the official policies, either expressed or implied,
of the United States Air Force or the U.S. Government. The U.S. Government is authorized
to reproduce and distribute reprints for Government purposes, notwithstanding any
copyright notation herein. This work was further supported by The Boeing Company
and Office of Naval Research grant N00014-18-1-2830. M.T. is supported by the Poul
Due Jensen Foundation, grant 883901. M.L. was supported in part by the Austrian
Science Fund under grant Z211-N23 (Wittgenstein Award). A.A. was supported by the
National Science Foundation Graduate Research Fellowship Program. We thank T.-H.
Wang, P. Kao, M. Chahine, W. Xiao, X. Li, L. Yin and Y. Ben for useful suggestions
and for testing of CfC models to confirm the results across other domains.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ramin
full_name: Hasani, Ramin
last_name: Hasani
- first_name: Mathias
full_name: Lechner, Mathias
id: 3DC22916-F248-11E8-B48F-1D18A9856A87
last_name: Lechner
- first_name: Alexander
full_name: Amini, Alexander
last_name: Amini
- first_name: Lucas
full_name: Liebenwein, Lucas
last_name: Liebenwein
- first_name: Aaron
full_name: Ray, Aaron
last_name: Ray
- first_name: Max
full_name: Tschaikowski, Max
last_name: Tschaikowski
- first_name: Gerald
full_name: Teschl, Gerald
last_name: Teschl
- first_name: Daniela
full_name: Rus, Daniela
last_name: Rus
citation:
ama: Hasani R, Lechner M, Amini A, et al. Closed-form continuous-time neural networks.
Nature Machine Intelligence. 2022;4(11):992-1003. doi:10.1038/s42256-022-00556-7
apa: Hasani, R., Lechner, M., Amini, A., Liebenwein, L., Ray, A., Tschaikowski,
M., … Rus, D. (2022). Closed-form continuous-time neural networks. Nature Machine
Intelligence. Springer Nature. https://doi.org/10.1038/s42256-022-00556-7
chicago: Hasani, Ramin, Mathias Lechner, Alexander Amini, Lucas Liebenwein, Aaron
Ray, Max Tschaikowski, Gerald Teschl, and Daniela Rus. “Closed-Form Continuous-Time
Neural Networks.” Nature Machine Intelligence. Springer Nature, 2022. https://doi.org/10.1038/s42256-022-00556-7.
ieee: R. Hasani et al., “Closed-form continuous-time neural networks,” Nature
Machine Intelligence, vol. 4, no. 11. Springer Nature, pp. 992–1003, 2022.
ista: Hasani R, Lechner M, Amini A, Liebenwein L, Ray A, Tschaikowski M, Teschl
G, Rus D. 2022. Closed-form continuous-time neural networks. Nature Machine Intelligence.
4(11), 992–1003.
mla: Hasani, Ramin, et al. “Closed-Form Continuous-Time Neural Networks.” Nature
Machine Intelligence, vol. 4, no. 11, Springer Nature, 2022, pp. 992–1003,
doi:10.1038/s42256-022-00556-7.
short: R. Hasani, M. Lechner, A. Amini, L. Liebenwein, A. Ray, M. Tschaikowski,
G. Teschl, D. Rus, Nature Machine Intelligence 4 (2022) 992–1003.
date_created: 2023-01-12T12:07:21Z
date_published: 2022-11-15T00:00:00Z
date_updated: 2023-08-04T09:00:10Z
day: '15'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1038/s42256-022-00556-7
external_id:
arxiv:
- '2106.13898'
isi:
- '000884215600003'
file:
- access_level: open_access
checksum: b4789122ce04bfb4ac042390f59aaa8b
content_type: application/pdf
creator: dernst
date_created: 2023-01-24T09:49:44Z
date_updated: 2023-01-24T09:49:44Z
file_id: '12355'
file_name: 2022_NatureMachineIntelligence_Hasani.pdf
file_size: 3259553
relation: main_file
success: 1
file_date_updated: 2023-01-24T09:49:44Z
has_accepted_license: '1'
intvolume: ' 4'
isi: 1
issue: '11'
keyword:
- Artificial Intelligence
- Computer Networks and Communications
- Computer Vision and Pattern Recognition
- Human-Computer Interaction
- Software
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 992-1003
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: Nature Machine Intelligence
publication_identifier:
issn:
- 2522-5839
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: erratum
url: https://doi.org/10.1038/s42256-022-00597-y
scopus_import: '1'
status: public
title: Closed-form continuous-time neural networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 4
year: '2022'
...
---
_id: '10855'
abstract:
- lang: eng
text: 'Consider a distributed task where the communication network is fixed but
the local inputs given to the nodes of the distributed system may change over
time. In this work, we explore the following question: if some of the local inputs
change, can an existing solution be updated efficiently, in a dynamic and distributed
manner? To address this question, we define the batch dynamic \congest model in
which we are given a bandwidth-limited communication network and a dynamic edge
labelling defines the problem input. The task is to maintain a solution to a graph
problem on the labeled graph under batch changes. We investigate, when a batch
of α edge label changes arrive, \beginitemize \item how much time as a function
of α we need to update an existing solution, and \item how much information the
nodes have to keep in local memory between batches in order to update the solution
quickly. \enditemize Our work lays the foundations for the theory of input-dynamic
distributed network algorithms. We give a general picture of the complexity landscape
in this model, design both universal algorithms and algorithms for concrete problems,
and present a general framework for lower bounds. In particular, we derive non-trivial
upper bounds for two selected, contrasting problems: maintaining a minimum spanning
tree and detecting cliques.'
acknowledgement: "We thank Jukka Suomela for discussions. We also thank our shepherd
Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how
to improve the paper. This project\r\nhas received funding from the European Research
Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation
programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon
2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant
agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project
WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE
SCIENCE project P 33775-N."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Klaus-Tycho
full_name: Foerster, Klaus-Tycho
last_name: Foerster
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Ami
full_name: Paz, Ami
last_name: Paz
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed
algorithms for communication networks. Proceedings of the ACM on Measurement
and Analysis of Computing Systems. 2021;5(1):1-33. doi:10.1145/3447384
apa: Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021).
Input-dynamic distributed algorithms for communication networks. Proceedings
of the ACM on Measurement and Analysis of Computing Systems. Association for
Computing Machinery. https://doi.org/10.1145/3447384
chicago: Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan
Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” Proceedings
of the ACM on Measurement and Analysis of Computing Systems. Association for
Computing Machinery, 2021. https://doi.org/10.1145/3447384.
ieee: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic
distributed algorithms for communication networks,” Proceedings of the ACM
on Measurement and Analysis of Computing Systems, vol. 5, no. 1. Association
for Computing Machinery, pp. 1–33, 2021.
ista: Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic
distributed algorithms for communication networks. Proceedings of the ACM on Measurement
and Analysis of Computing Systems. 5(1), 1–33.
mla: Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication
Networks.” Proceedings of the ACM on Measurement and Analysis of Computing
Systems, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33,
doi:10.1145/3447384.
short: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of
the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.
date_created: 2022-03-18T09:10:27Z
date_published: 2021-03-01T00:00:00Z
date_updated: 2023-09-26T10:40:55Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3447384
ec_funded: 1
external_id:
arxiv:
- '2005.07637'
intvolume: ' 5'
issue: '1'
keyword:
- Computer Networks and Communications
- Hardware and Architecture
- Safety
- Risk
- Reliability and Quality
- Computer Science (miscellaneous)
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.07637
month: '03'
oa: 1
oa_version: Preprint
page: 1-33
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the ACM on Measurement and Analysis of Computing Systems
publication_identifier:
issn:
- 2476-1249
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '10854'
relation: shorter_version
status: public
scopus_import: '1'
status: public
title: Input-dynamic distributed algorithms for communication networks
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2021'
...
---
_id: '9234'
abstract:
- lang: eng
text: In this paper, we present two new inertial projection-type methods for solving
multivalued variational inequality problems in finite-dimensional spaces. We establish
the convergence of the sequence generated by these methods when the multivalued
mapping associated with the problem is only required to be locally bounded without
any monotonicity assumption. Furthermore, the inertial techniques that we employ
in this paper are quite different from the ones used in most papers. Moreover,
based on the weaker assumptions on the inertial factor in our methods, we derive
several special cases of our methods. Finally, we present some experimental results
to illustrate the profits that we gain by introducing the inertial extrapolation
steps.
acknowledgement: 'The authors sincerely thank the Editor-in-Chief and anonymous referees
for their careful reading, constructive comments and fruitful suggestions that help
improve the manuscript. The research of the first author is supported by the National
Research Foundation (NRF) South Africa (S& F-DSI/NRF Free Standing Postdoctoral
Fellowship; Grant Number: 120784). The first author also acknowledges the financial
support from DSI/NRF, South Africa Center of Excellence in Mathematical and Statistical
Sciences (CoE-MaSS) Postdoctoral Fellowship. The second author has received funding
from the European Research Council (ERC) under the European Union’s Seventh Framework
Program (FP7 - 2007-2013) (Grant agreement No. 616160). Open Access funding provided
by Institute of Science and Technology (IST Austria).'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Chinedu
full_name: Izuchukwu, Chinedu
last_name: Izuchukwu
- first_name: Yekini
full_name: Shehu, Yekini
id: 3FC7CB58-F248-11E8-B48F-1D18A9856A87
last_name: Shehu
orcid: 0000-0001-9224-7139
citation:
ama: Izuchukwu C, Shehu Y. New inertial projection methods for solving multivalued
variational inequality problems beyond monotonicity. Networks and Spatial Economics.
2021;21(2):291-323. doi:10.1007/s11067-021-09517-w
apa: Izuchukwu, C., & Shehu, Y. (2021). New inertial projection methods for
solving multivalued variational inequality problems beyond monotonicity. Networks
and Spatial Economics. Springer Nature. https://doi.org/10.1007/s11067-021-09517-w
chicago: Izuchukwu, Chinedu, and Yekini Shehu. “New Inertial Projection Methods
for Solving Multivalued Variational Inequality Problems beyond Monotonicity.”
Networks and Spatial Economics. Springer Nature, 2021. https://doi.org/10.1007/s11067-021-09517-w.
ieee: C. Izuchukwu and Y. Shehu, “New inertial projection methods for solving multivalued
variational inequality problems beyond monotonicity,” Networks and Spatial
Economics, vol. 21, no. 2. Springer Nature, pp. 291–323, 2021.
ista: Izuchukwu C, Shehu Y. 2021. New inertial projection methods for solving multivalued
variational inequality problems beyond monotonicity. Networks and Spatial Economics.
21(2), 291–323.
mla: Izuchukwu, Chinedu, and Yekini Shehu. “New Inertial Projection Methods for
Solving Multivalued Variational Inequality Problems beyond Monotonicity.” Networks
and Spatial Economics, vol. 21, no. 2, Springer Nature, 2021, pp. 291–323,
doi:10.1007/s11067-021-09517-w.
short: C. Izuchukwu, Y. Shehu, Networks and Spatial Economics 21 (2021) 291–323.
date_created: 2021-03-10T12:18:47Z
date_published: 2021-06-01T00:00:00Z
date_updated: 2023-09-05T15:32:32Z
day: '01'
ddc:
- '510'
department:
- _id: VlKo
doi: 10.1007/s11067-021-09517-w
ec_funded: 1
external_id:
isi:
- '000625002100001'
file:
- access_level: open_access
checksum: 22b4253a2e5da843622a2df713784b4c
content_type: application/pdf
creator: kschuh
date_created: 2021-08-11T12:44:16Z
date_updated: 2021-08-11T12:44:16Z
file_id: '9884'
file_name: 2021_NetworksSpatialEconomics_Shehu.pdf
file_size: 834964
relation: main_file
success: 1
file_date_updated: 2021-08-11T12:44:16Z
has_accepted_license: '1'
intvolume: ' 21'
isi: 1
issue: '2'
keyword:
- Computer Networks and Communications
- Software
- Artificial Intelligence
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 291-323
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Networks and Spatial Economics
publication_identifier:
eissn:
- 1572-9427
issn:
- 1566-113X
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: New inertial projection methods for solving multivalued variational inequality
problems beyond monotonicity
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: 21
year: '2021'
...
---
_id: '8765'
abstract:
- lang: eng
text: This paper introduces a simple method for simulating highly anisotropic elastoplastic
material behaviors like the dissolution of fibrous phenomena (splintering wood,
shredding bales of hay) and materials composed of large numbers of irregularly‐shaped
bodies (piles of twigs, pencils, or cards). We introduce a simple transformation
of the anisotropic problem into an equivalent isotropic one, and we solve this
new “fictitious” isotropic problem using an existing simulator based on the material
point method. Our approach results in minimal changes to existing simulators,
and it allows us to re‐use popular isotropic plasticity models like the Drucker‐Prager
yield criterion instead of inventing new anisotropic plasticity models for every
phenomenon we wish to simulate.
acknowledged_ssus:
- _id: ScienComp
acknowledgement: "We wish to thank the anonymous reviewers and the members of the
Visual Computing Group at IST Austria for their valuable feedback. This research
was supported by the Scientific Service Units (SSU) of IST Austria through resources
provided by Scientific Computing. We would also like to thank Joseph Teran and Chenfanfu
Jiang for the helpful discussions.\r\nThis project has received funding from the
European Research Council (ERC) under the European Union's Horizon 2020 research
and innovation programme under grant agreement No. 638176."
article_processing_charge: No
article_type: original
author:
- first_name: Camille
full_name: Schreck, Camille
id: 2B14B676-F248-11E8-B48F-1D18A9856A87
last_name: Schreck
- first_name: Christopher J
full_name: Wojtan, Christopher J
id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
last_name: Wojtan
orcid: 0000-0001-6646-5546
citation:
ama: Schreck C, Wojtan C. A practical method for animating anisotropic elastoplastic
materials. Computer Graphics Forum. 2020;39(2):89-99. doi:10.1111/cgf.13914
apa: Schreck, C., & Wojtan, C. (2020). A practical method for animating anisotropic
elastoplastic materials. Computer Graphics Forum. Wiley. https://doi.org/10.1111/cgf.13914
chicago: Schreck, Camille, and Chris Wojtan. “A Practical Method for Animating Anisotropic
Elastoplastic Materials.” Computer Graphics Forum. Wiley, 2020. https://doi.org/10.1111/cgf.13914.
ieee: C. Schreck and C. Wojtan, “A practical method for animating anisotropic elastoplastic
materials,” Computer Graphics Forum, vol. 39, no. 2. Wiley, pp. 89–99,
2020.
ista: Schreck C, Wojtan C. 2020. A practical method for animating anisotropic elastoplastic
materials. Computer Graphics Forum. 39(2), 89–99.
mla: Schreck, Camille, and Chris Wojtan. “A Practical Method for Animating Anisotropic
Elastoplastic Materials.” Computer Graphics Forum, vol. 39, no. 2, Wiley,
2020, pp. 89–99, doi:10.1111/cgf.13914.
short: C. Schreck, C. Wojtan, Computer Graphics Forum 39 (2020) 89–99.
date_created: 2020-11-17T09:35:10Z
date_published: 2020-05-01T00:00:00Z
date_updated: 2023-09-05T16:00:13Z
day: '01'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1111/cgf.13914
ec_funded: 1
external_id:
isi:
- '000548709600008'
file:
- access_level: open_access
checksum: 7605f605acd84d0942b48bc7a1c2d72e
content_type: application/pdf
creator: dernst
date_created: 2020-11-23T09:05:13Z
date_updated: 2020-11-23T09:05:13Z
file_id: '8796'
file_name: 2020_poff_revisited.pdf
file_size: 38969122
relation: main_file
success: 1
file_date_updated: 2020-11-23T09:05:13Z
has_accepted_license: '1'
intvolume: ' 39'
isi: 1
issue: '2'
keyword:
- Computer Networks and Communications
language:
- iso: eng
month: '05'
oa: 1
oa_version: Submitted Version
page: 89-99
project:
- _id: 2533E772-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '638176'
name: Efficient Simulation of Natural Phenomena at Extremely Large Scales
publication: Computer Graphics Forum
publication_identifier:
eissn:
- 1467-8659
issn:
- 0167-7055
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: A practical method for animating anisotropic elastoplastic materials
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 39
year: '2020'
...
---
_id: '11671'
abstract:
- lang: eng
text: "Given only the URL of a Web page, can we identify its language? In this article
we examine this question. URL-based language classification is useful when the
content of the Web page is not available or downloading the content is a waste
of bandwidth and time.\r\nWe built URL-based language classifiers for English,
German, French, Spanish, and Italian by applying a variety of algorithms and features.
As algorithms we used machine learning algorithms which are widely applied for
text classification and state-of-art algorithms for language identification of
text. As features we used words, various sized n-grams, and custom-made features
(our novel feature set). We compared our approaches with two baseline methods,
namely classification by country code top-level domains and classification by
IP addresses of the hosting Web servers.\r\n\r\nWe trained and tested our classifiers
in a 10-fold cross-validation setup on a dataset obtained from the Open Directory
Project and from querying a commercial search engine. We obtained the lowest F1-measure
for English (94) and the highest F1-measure for German (98) with the best performing
classifiers.\r\n\r\nWe also evaluated the performance of our methods: (i) on a
set of Web pages written in Adobe Flash and (ii) as part of a language-focused
crawler. In the first case, the content of the Web page is hard to extract and
in the second page downloading pages of the “wrong” language constitutes a waste
of bandwidth. In both settings the best classifiers have a high accuracy with
an F1-measure between 95 (for English) and 98 (for Italian) for the Adobe Flash
pages and a precision between 90 (for Italian) and 97 (for French) for the language-focused
crawler."
article_number: '3'
article_processing_charge: No
article_type: original
author:
- first_name: Eda
full_name: Baykan, Eda
last_name: Baykan
- first_name: Ingmar
full_name: Weber, Ingmar
last_name: Weber
- 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: Baykan E, Weber I, Henzinger MH. A comprehensive study of techniques for URL-based
web page language classification. ACM Transactions on the Web. 2013;7(1).
doi:10.1145/2435215.2435218
apa: Baykan, E., Weber, I., & Henzinger, M. H. (2013). A comprehensive study
of techniques for URL-based web page language classification. ACM Transactions
on the Web. Association for Computing Machinery. https://doi.org/10.1145/2435215.2435218
chicago: Baykan, Eda, Ingmar Weber, and Monika H Henzinger. “A Comprehensive Study
of Techniques for URL-Based Web Page Language Classification.” ACM Transactions
on the Web. Association for Computing Machinery, 2013. https://doi.org/10.1145/2435215.2435218.
ieee: E. Baykan, I. Weber, and M. H. Henzinger, “A comprehensive study of techniques
for URL-based web page language classification,” ACM Transactions on the Web,
vol. 7, no. 1. Association for Computing Machinery, 2013.
ista: Baykan E, Weber I, Henzinger MH. 2013. A comprehensive study of techniques
for URL-based web page language classification. ACM Transactions on the Web. 7(1),
3.
mla: Baykan, Eda, et al. “A Comprehensive Study of Techniques for URL-Based Web
Page Language Classification.” ACM Transactions on the Web, vol. 7, no.
1, 3, Association for Computing Machinery, 2013, doi:10.1145/2435215.2435218.
short: E. Baykan, I. Weber, M.H. Henzinger, ACM Transactions on the Web 7 (2013).
date_created: 2022-07-27T12:50:18Z
date_published: 2013-03-01T00:00:00Z
date_updated: 2022-09-12T08:51:57Z
day: '01'
doi: 10.1145/2435215.2435218
extern: '1'
intvolume: ' 7'
issue: '1'
keyword:
- Computer Networks and Communications
language:
- iso: eng
month: '03'
oa_version: None
publication: ACM Transactions on the Web
publication_identifier:
eissn:
- 1559-114X
issn:
- 1559-1131
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A comprehensive study of techniques for URL-based web page language classification
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2013'
...