---
_id: '10023'
abstract:
- lang: eng
text: We study the temporal dissipation of variance and relative entropy for ergodic
Markov Chains in continuous time, and compute explicitly the corresponding dissipation
rates. These are identified, as is well known, in the case of the variance in
terms of an appropriate Hilbertian norm; and in the case of the relative entropy,
in terms of a Dirichlet form which morphs into a version of the familiar Fisher
information under conditions of detailed balance. Here we obtain trajectorial
versions of these results, valid along almost every path of the random motion
and most transparent in the backwards direction of time. Martingale arguments
and time reversal play crucial roles, as in the recent work of Karatzas, Schachermayer
and Tschiderer for conservative diffusions. Extensions are developed to general
“convex divergences” and to countable state-spaces. The steepest descent and gradient
flow properties for the variance, the relative entropy, and appropriate generalizations,
are studied along with their respective geometries under conditions of detailed
balance, leading to a very direct proof for the HWI inequality of Otto and Villani
in the present context.
acknowledgement: I.K. acknowledges support from the U.S. National Science Foundation
under Grant NSF-DMS-20-04997. J.M. acknowledges support from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 716117) and from the Austrian Science Fund (FWF) through project
F65. W.S. acknowledges support from the Austrian Science Fund (FWF) under grant
P28861 and by the Vienna Science and Technology Fund (WWTF) through projects MA14-008
and MA16-021.
article_processing_charge: No
article_type: original
author:
- first_name: Ioannis
full_name: Karatzas, Ioannis
last_name: Karatzas
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
- first_name: Walter
full_name: Schachermayer, Walter
last_name: Schachermayer
citation:
ama: Karatzas I, Maas J, Schachermayer W. Trajectorial dissipation and gradient
flow for the relative entropy in Markov chains. Communications in Information
and Systems. 2021;21(4):481-536. doi:10.4310/CIS.2021.v21.n4.a1
apa: Karatzas, I., Maas, J., & Schachermayer, W. (2021). Trajectorial dissipation
and gradient flow for the relative entropy in Markov chains. Communications
in Information and Systems. International Press. https://doi.org/10.4310/CIS.2021.v21.n4.a1
chicago: Karatzas, Ioannis, Jan Maas, and Walter Schachermayer. “Trajectorial Dissipation
and Gradient Flow for the Relative Entropy in Markov Chains.” Communications
in Information and Systems. International Press, 2021. https://doi.org/10.4310/CIS.2021.v21.n4.a1.
ieee: I. Karatzas, J. Maas, and W. Schachermayer, “Trajectorial dissipation and
gradient flow for the relative entropy in Markov chains,” Communications in
Information and Systems, vol. 21, no. 4. International Press, pp. 481–536,
2021.
ista: Karatzas I, Maas J, Schachermayer W. 2021. Trajectorial dissipation and gradient
flow for the relative entropy in Markov chains. Communications in Information
and Systems. 21(4), 481–536.
mla: Karatzas, Ioannis, et al. “Trajectorial Dissipation and Gradient Flow for the
Relative Entropy in Markov Chains.” Communications in Information and Systems,
vol. 21, no. 4, International Press, 2021, pp. 481–536, doi:10.4310/CIS.2021.v21.n4.a1.
short: I. Karatzas, J. Maas, W. Schachermayer, Communications in Information and
Systems 21 (2021) 481–536.
date_created: 2021-09-19T08:53:19Z
date_published: 2021-06-04T00:00:00Z
date_updated: 2021-09-20T12:51:18Z
day: '04'
department:
- _id: JaMa
doi: 10.4310/CIS.2021.v21.n4.a1
ec_funded: 1
external_id:
arxiv:
- '2005.14177'
intvolume: ' 21'
issue: '4'
keyword:
- Markov Chain
- relative entropy
- time reversal
- steepest descent
- gradient flow
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.14177
month: '06'
oa: 1
oa_version: Preprint
page: 481-536
project:
- _id: 256E75B8-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '716117'
name: Optimal Transport and Stochastic Dynamics
- _id: fc31cba2-9c52-11eb-aca3-ff467d239cd2
grant_number: F6504
name: Taming Complexity in Partial Differential Systems
publication: Communications in Information and Systems
publication_identifier:
issn:
- 1526-7555
publication_status: published
publisher: International Press
quality_controlled: '1'
status: public
title: Trajectorial dissipation and gradient flow for the relative entropy in Markov
chains
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 21
year: '2021'
...
---
_id: '10052'
abstract:
- lang: eng
text: "A deterministic finite automaton (DFA) \U0001D49C is composite if its language
L(\U0001D49C) can be decomposed into an intersection ⋂_{i = 1}^k L(\U0001D49C_i)
of languages of smaller DFAs. Otherwise, \U0001D49C is prime. This notion of primality
was introduced by Kupferman and Mosheiff in 2013, and while they proved that we
can decide whether a DFA is composite, the precise complexity of this problem
is still open, with a doubly-exponential gap between the upper and lower bounds.
In this work, we focus on permutation DFAs, i.e., those for which the transition
monoid is a group. We provide an NP algorithm to decide whether a permutation
DFA is composite, and show that the difficulty of this problem comes from the
number of non-accepting states of the instance: we give a fixed-parameter tractable
algorithm with the number of rejecting states as the parameter. Moreover, we investigate
the class of commutative permutation DFAs. Their structural properties allow us
to decide compositionality in NL, and even in LOGSPACE if the alphabet size is
fixed. Despite this low complexity, we show that complex behaviors still arise
in this class: we provide a family of composite DFAs each requiring polynomially
many factors with respect to its size. We also consider the variant of the problem
that asks whether a DFA is k-factor composite, that is, decomposable into k smaller
DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation
DFAs, restricting the number of factors makes the decision computationally harder,
and yields a problem with tight bounds: it is NP-complete. Finally, we show that
in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton
alphabet."
acknowledgement: "Ismaël Jecker: Marie Skłodowska-Curie Grant Agreement No. 754411.
Nicolas Mazzocchi: BOSCO project PGC2018-102210-B-I00 (MCIU/AEI/FEDER, UE), BLOQUESCM
project S2018/TCS-4339, and MINECO grant RYC-2016-20281.\r\nPetra Wolf : DFG project
FE 560/9-1.\r\n"
alternative_title:
- LIPIcs
article_number: '18'
article_processing_charge: No
author:
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Nicolas
full_name: Mazzocchi, Nicolas
last_name: Mazzocchi
- first_name: Petra
full_name: Wolf, Petra
last_name: Wolf
citation:
ama: 'Jecker IR, Mazzocchi N, Wolf P. Decomposing permutation automata. In: 32nd
International Conference on Concurrency Theory. Vol 203. Schloss Dagstuhl
- Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.CONCUR.2021.18'
apa: 'Jecker, I. R., Mazzocchi, N., & Wolf, P. (2021). Decomposing permutation
automata. In 32nd International Conference on Concurrency Theory (Vol.
203). Paris, France: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2021.18'
chicago: Jecker, Ismael R, Nicolas Mazzocchi, and Petra Wolf. “Decomposing Permutation
Automata.” In 32nd International Conference on Concurrency Theory, Vol.
203. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.CONCUR.2021.18.
ieee: I. R. Jecker, N. Mazzocchi, and P. Wolf, “Decomposing permutation automata,”
in 32nd International Conference on Concurrency Theory, Paris, France,
2021, vol. 203.
ista: 'Jecker IR, Mazzocchi N, Wolf P. 2021. Decomposing permutation automata. 32nd
International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 203, 18.'
mla: Jecker, Ismael R., et al. “Decomposing Permutation Automata.” 32nd International
Conference on Concurrency Theory, vol. 203, 18, Schloss Dagstuhl - Leibniz
Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.CONCUR.2021.18.
short: I.R. Jecker, N. Mazzocchi, P. Wolf, in:, 32nd International Conference on
Concurrency Theory, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-08-27
location: Paris, France
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2021-08-23
date_created: 2021-09-27T14:33:14Z
date_published: 2021-08-13T00:00:00Z
date_updated: 2022-05-13T08:12:52Z
day: '13'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2021.18
ec_funded: 1
external_id:
arxiv:
- '2107.04683'
file:
- access_level: open_access
checksum: 4722c81be82265cf45e78adf9db91250
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-01T11:10:53Z
date_updated: 2021-10-01T11:10:53Z
file_id: '10064'
file_name: 2021_CONCUR_Jecker.pdf
file_size: 1003552
relation: main_file
success: 1
file_date_updated: 2021-10-01T11:10:53Z
has_accepted_license: '1'
intvolume: ' 203'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 32nd International Conference on Concurrency Theory
publication_identifier:
isbn:
- 978-3-9597-7203-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decomposing permutation automata
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 203
year: '2021'
...
---
_id: '10054'
abstract:
- lang: eng
text: 'Graphs and games on graphs are fundamental models for the analysis of reactive
systems, in particular, for model-checking and the synthesis of reactive systems.
The class of ω-regular languages provides a robust specification formalism for
the desired properties of reactive systems. In the classical infinitary formulation
of the liveness part of an ω-regular specification, a "good" event must happen
eventually without any bound between the good events. A stronger notion of liveness
is bounded liveness, which requires that good events happen within d transitions.
Given a graph or a game graph with n vertices, m edges, and a bounded liveness
objective, the previous best-known algorithmic bounds are as follows: (i) O(dm)
for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs.
Our main contributions improve these long-standing algorithmic bounds. For graphs
we present: (i) a randomized algorithm with one-sided error with running time
O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic
linear-time algorithm for the complement of bounded liveness objectives. For games
on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.'
acknowledgement: 'Krishnendu Chatterjee: Supported by the ERC CoG 863818 (ForM-SMArt).
Monika Henzinger: Supported by the Austrian Science Fund (FWF) and netIDEE SCIENCE
project P 33775-N. Sagar Sudhir Kale: Partially supported by the Vienna Science
and Technology Fund (WWTF) through project ICT15-003. Alexander Svozil: Fully supported
by the Vienna Science and Technology Fund (WWTF) through project ICT15-003.'
alternative_title:
- LIPIcs
article_number: '124'
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sagar Sudhir
full_name: Kale, Sagar Sudhir
last_name: Kale
- first_name: Alexander
full_name: Svozil, Alexander
last_name: Svozil
citation:
ama: 'Chatterjee K, Henzinger MH, Kale SS, Svozil A. Faster algorithms for bounded
liveness in graphs and game graphs. In: 48th International Colloquium on Automata,
Languages, and Programming. Vol 198. Schloss Dagstuhl - Leibniz Zentrum für
Informatik; 2021. doi:10.4230/LIPIcs.ICALP.2021.124'
apa: 'Chatterjee, K., Henzinger, M. H., Kale, S. S., & Svozil, A. (2021). Faster
algorithms for bounded liveness in graphs and game graphs. In 48th International
Colloquium on Automata, Languages, and Programming (Vol. 198). Glasgow, Scotland:
Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2021.124'
chicago: Chatterjee, Krishnendu, Monika H Henzinger, Sagar Sudhir Kale, and Alexander
Svozil. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” In
48th International Colloquium on Automata, Languages, and Programming,
Vol. 198. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.124.
ieee: K. Chatterjee, M. H. Henzinger, S. S. Kale, and A. Svozil, “Faster algorithms
for bounded liveness in graphs and game graphs,” in 48th International Colloquium
on Automata, Languages, and Programming, Glasgow, Scotland, 2021, vol. 198.
ista: 'Chatterjee K, Henzinger MH, Kale SS, Svozil A. 2021. Faster algorithms for
bounded liveness in graphs and game graphs. 48th International Colloquium on Automata,
Languages, and Programming. ICALP: International Colloquium on Automata, Languages,
and Programming, LIPIcs, vol. 198, 124.'
mla: Chatterjee, Krishnendu, et al. “Faster Algorithms for Bounded Liveness in Graphs
and Game Graphs.” 48th International Colloquium on Automata, Languages, and
Programming, vol. 198, 124, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.ICALP.2021.124.
short: K. Chatterjee, M.H. Henzinger, S.S. Kale, A. Svozil, in:, 48th International
Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz
Zentrum für Informatik, 2021.
conference:
end_date: 2021-07-16
location: Glasgow, Scotland
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2021-07-12
date_created: 2021-09-27T14:33:15Z
date_published: 2021-07-02T00:00:00Z
date_updated: 2022-08-12T10:55:02Z
day: '02'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2021.124
ec_funded: 1
file:
- access_level: open_access
checksum: 5a3fed8dbba8c088cbeac1e24cc10bc5
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-01T08:49:26Z
date_updated: 2021-10-01T08:49:26Z
file_id: '10062'
file_name: 2021_LIPIcs_Chatterjee.pdf
file_size: 854576
relation: main_file
success: 1
file_date_updated: 2021-10-01T08:49:26Z
has_accepted_license: '1'
intvolume: ' 198'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 48th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- 978-3-95977-195-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster algorithms for bounded liveness in graphs and game graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 198
year: '2021'
...
---
_id: '10071'
alternative_title:
- Early Career
article_processing_charge: No
article_type: letter_note
author:
- first_name: Henry
full_name: Adams, Henry
last_name: Adams
- first_name: Hana
full_name: Kourimska, Hana
id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
last_name: Kourimska
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Sarah
full_name: Percival, Sarah
last_name: Percival
- first_name: Lori
full_name: Ziegelmeier, Lori
last_name: Ziegelmeier
citation:
ama: Adams H, Kourimska H, Heiss T, Percival S, Ziegelmeier L. How to tutorial-a-thon.
Notices of the American Mathematical Society. 2021;68(9):1511-1514. doi:10.1090/noti2349
apa: Adams, H., Kourimska, H., Heiss, T., Percival, S., & Ziegelmeier, L. (2021).
How to tutorial-a-thon. Notices of the American Mathematical Society. American
Mathematical Society. https://doi.org/10.1090/noti2349
chicago: Adams, Henry, Hana Kourimska, Teresa Heiss, Sarah Percival, and Lori Ziegelmeier.
“How to Tutorial-a-Thon.” Notices of the American Mathematical Society.
American Mathematical Society, 2021. https://doi.org/10.1090/noti2349.
ieee: H. Adams, H. Kourimska, T. Heiss, S. Percival, and L. Ziegelmeier, “How to
tutorial-a-thon,” Notices of the American Mathematical Society, vol. 68,
no. 9. American Mathematical Society, pp. 1511–1514, 2021.
ista: Adams H, Kourimska H, Heiss T, Percival S, Ziegelmeier L. 2021. How to tutorial-a-thon.
Notices of the American Mathematical Society. 68(9), 1511–1514.
mla: Adams, Henry, et al. “How to Tutorial-a-Thon.” Notices of the American Mathematical
Society, vol. 68, no. 9, American Mathematical Society, 2021, pp. 1511–14,
doi:10.1090/noti2349.
short: H. Adams, H. Kourimska, T. Heiss, S. Percival, L. Ziegelmeier, Notices of
the American Mathematical Society 68 (2021) 1511–1514.
date_created: 2021-10-03T22:01:22Z
date_published: 2021-10-01T00:00:00Z
date_updated: 2021-12-03T07:31:26Z
day: '01'
department:
- _id: HeEd
doi: 10.1090/noti2349
intvolume: ' 68'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ams.org/notices/
month: '10'
oa: 1
oa_version: Published Version
page: 1511-1514
publication: Notices of the American Mathematical Society
publication_identifier:
eissn:
- 1088-9477
issn:
- 0002-9920
publication_status: published
publisher: American Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: How to tutorial-a-thon
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 68
year: '2021'
...
---
_id: '10072'
abstract:
- lang: eng
text: The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics
which can be used to establish the existence of objects that satisfy certain properties.
The breakthrough paper of Moser and Tardos and follow-up works revealed that the
LLL has intimate connections with a class of stochastic local search algorithms
for finding such desirable objects. In particular, it can be seen as a sufficient
condition for this type of algorithms to converge fast. Besides conditions for
existence of and fast convergence to desirable objects, one may naturally ask
further questions regarding properties of these algorithms. For instance, "are
they parallelizable?", "how many solutions can they output?", "what is the expected
"weight" of a solution?", etc. These questions and more have been answered for
a class of LLL-inspired algorithms called commutative. In this paper we introduce
a new, very natural and more general notion of commutativity (essentially matrix
commutativity) which allows us to show a number of new refined properties of LLL-inspired
local search algorithms with significantly simpler proofs.
acknowledgement: "Fotis Iliopoulos: This material is based upon work directly supported
by the IAS Fund for Math and indirectly supported by the National Science Foundation
Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations
expressed in this material are those of the author(s) and do not necessarily reflect
the views of the National Science Foundation. This work is also supported by the
National Science Foundation Grant No. CCF-1815328.\r\nVladimir Kolmogorov: Supported
by the European Research Council under the European Unions Seventh Framework Programme
(FP7/2007-2013)/ERC grant agreement no 616160."
alternative_title:
- LIPIcs
article_number: '31'
article_processing_charge: Yes
author:
- first_name: David G.
full_name: Harris, David G.
last_name: Harris
- first_name: Fotis
full_name: Iliopoulos, Fotis
last_name: Iliopoulos
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Harris DG, Iliopoulos F, Kolmogorov V. A new notion of commutativity for the
algorithmic Lovász Local Lemma. In: Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques. Vol 207. Schloss Dagstuhl - Leibniz
Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.31'
apa: 'Harris, D. G., Iliopoulos, F., & Kolmogorov, V. (2021). A new notion of
commutativity for the algorithmic Lovász Local Lemma. In Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques (Vol. 207). Virtual:
Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31'
chicago: Harris, David G., Fotis Iliopoulos, and Vladimir Kolmogorov. “A New Notion
of Commutativity for the Algorithmic Lovász Local Lemma.” In Approximation,
Randomization, and Combinatorial Optimization. Algorithms and Techniques,
Vol. 207. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31.
ieee: D. G. Harris, F. Iliopoulos, and V. Kolmogorov, “A new notion of commutativity
for the algorithmic Lovász Local Lemma,” in Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques, Virtual, 2021, vol.
207.
ista: 'Harris DG, Iliopoulos F, Kolmogorov V. 2021. A new notion of commutativity
for the algorithmic Lovász Local Lemma. Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques. APPROX/RANDOM: Approximation Algorithms
for Combinatorial Optimization Problems/ Randomization and Computation, LIPIcs,
vol. 207, 31.'
mla: Harris, David G., et al. “A New Notion of Commutativity for the Algorithmic
Lovász Local Lemma.” Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques, vol. 207, 31, Schloss Dagstuhl - Leibniz Zentrum
für Informatik, 2021, doi:10.4230/LIPIcs.APPROX/RANDOM.2021.31.
short: D.G. Harris, F. Iliopoulos, V. Kolmogorov, in:, Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl -
Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-08-18
location: Virtual
name: 'APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/
Randomization and Computation'
start_date: 2021-08-16
date_created: 2021-10-03T22:01:22Z
date_published: 2021-09-15T00:00:00Z
date_updated: 2022-03-18T10:08:25Z
day: '15'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.4230/LIPIcs.APPROX/RANDOM.2021.31
ec_funded: 1
external_id:
arxiv:
- '2008.05569'
file:
- access_level: open_access
checksum: 9d2544d53aa5b01565c6891d97a4d765
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-06T13:51:54Z
date_updated: 2021-10-06T13:51:54Z
file_id: '10098'
file_name: 2021_LIPIcs_Harris.pdf
file_size: 804472
relation: main_file
success: 1
file_date_updated: 2021-10-06T13:51:54Z
has_accepted_license: '1'
intvolume: ' 207'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques
publication_identifier:
isbn:
- 978-3-9597-7207-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A new notion of commutativity for the algorithmic Lovász Local Lemma
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 207
year: '2021'
...
---
_id: '10075'
abstract:
- lang: eng
text: We study the expressiveness and succinctness of good-for-games pushdown automata
(GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can
be resolved based on the run constructed so far, but independently of the remainder
of the input word. We prove that GFG-PDA recognise more languages than deterministic
PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal
to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct
than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We
also study GFGness in visibly pushdown automata (VPA), which enjoy better closure
properties than PDA, and for which we show GFGness to be ExpTime-complete. GFG-VPA
can be exponentially more succinct than deterministic VPA, while VPA can be exponentially
more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we
study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has
a positional resolver, a function that resolves nondeterminism and that is only
dependant on the current configuration. Pushdown transducers are sufficient to
implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state
resolvers are determinisable.
acknowledgement: 'Ismaël Jecker: Funded by the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411.
Karoliina Lehtinen: Funded by the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No 892704.'
alternative_title:
- LIPIcs
article_number: '53'
article_processing_charge: No
author:
- first_name: Shibashis
full_name: Guha, Shibashis
last_name: Guha
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Karoliina
full_name: Lehtinen, Karoliina
last_name: Lehtinen
- first_name: Martin
full_name: Zimmermann, Martin
last_name: Zimmermann
citation:
ama: 'Guha S, Jecker IR, Lehtinen K, Zimmermann M. A bit of nondeterminism makes
pushdown automata expressive and succinct. In: 46th International Symposium
on Mathematical Foundations of Computer Science. Vol 202. Schloss Dagstuhl
- Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.MFCS.2021.53'
apa: 'Guha, S., Jecker, I. R., Lehtinen, K., & Zimmermann, M. (2021). A bit
of nondeterminism makes pushdown automata expressive and succinct. In 46th
International Symposium on Mathematical Foundations of Computer Science (Vol.
202). Tallinn, Estonia: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2021.53'
chicago: Guha, Shibashis, Ismael R Jecker, Karoliina Lehtinen, and Martin Zimmermann.
“A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.” In
46th International Symposium on Mathematical Foundations of Computer Science,
Vol. 202. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.MFCS.2021.53.
ieee: S. Guha, I. R. Jecker, K. Lehtinen, and M. Zimmermann, “A bit of nondeterminism
makes pushdown automata expressive and succinct,” in 46th International Symposium
on Mathematical Foundations of Computer Science, Tallinn, Estonia, 2021, vol.
202.
ista: 'Guha S, Jecker IR, Lehtinen K, Zimmermann M. 2021. A bit of nondeterminism
makes pushdown automata expressive and succinct. 46th International Symposium
on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations
of Computer Science, LIPIcs, vol. 202, 53.'
mla: Guha, Shibashis, et al. “A Bit of Nondeterminism Makes Pushdown Automata Expressive
and Succinct.” 46th International Symposium on Mathematical Foundations of
Computer Science, vol. 202, 53, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.MFCS.2021.53.
short: S. Guha, I.R. Jecker, K. Lehtinen, M. Zimmermann, in:, 46th International
Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl -
Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-08-27
location: Tallinn, Estonia
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2021-08-23
date_created: 2021-10-03T22:01:23Z
date_published: 2021-08-18T00:00:00Z
date_updated: 2022-05-13T08:21:56Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2021.53
ec_funded: 1
external_id:
arxiv:
- '2105.02611'
file:
- access_level: open_access
checksum: f4d407d43a97330c3fb11e6a7a6fbfb2
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-06T12:44:05Z
date_updated: 2021-10-06T12:44:05Z
file_id: '10097'
file_name: 2021_LIPIcs_Guha.pdf
file_size: 825567
relation: main_file
success: 1
file_date_updated: 2021-10-06T12:44:05Z
has_accepted_license: '1'
intvolume: ' 202'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 46th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- 978-3-9597-7201-3
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A bit of nondeterminism makes pushdown automata expressive and succinct
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2021'
...
---
_id: '10080'
abstract:
- lang: eng
text: Hippocampal and neocortical neural activity is modulated by the position of
the individual in space. While hippocampal neurons provide the basis for a spatial
map, prefrontal cortical neurons generalize over environmental features. Whether
these generalized representations result from a bidirectional interaction with,
or are mainly derived from hippocampal spatial representations is not known. By
examining simultaneously recorded hippocampal and medial prefrontal neurons, we
observed that prefrontal spatial representations show a delayed coherence with
hippocampal ones. We also identified subpopulations of cells in the hippocampus
and medial prefrontal cortex that formed functional cross-area couplings; these
resembled the optimal connections predicted by a probabilistic model of spatial
information transfer and generalization. Moreover, cross-area couplings were strongest
and had the shortest delay preceding spatial decision-making. Our results suggest
that generalized spatial coding in the medial prefrontal cortex is inherited from
spatial representations in the hippocampus, and that the routing of information
can change dynamically with behavioral demands.
acknowledgement: We thank Federico Stella for invaluable suggestions and discussions.
We thank Yosman BapatDhar and Andrea Cumpelik for comments, help and suggestions
on the exposure of the text. We thank Predrag Živadinović and Juliana Couras for
comments on the text and the figures. This work was supported by the EU-FP7 MC-ITN
IN-SENS (grant 607616).
article_processing_charge: No
author:
- first_name: Michele
full_name: Nardin, Michele
id: 30BD0376-F248-11E8-B48F-1D18A9856A87
last_name: Nardin
orcid: 0000-0001-8849-6570
- first_name: Karola
full_name: Käfer, Karola
id: 2DAA49AA-F248-11E8-B48F-1D18A9856A87
last_name: Käfer
- first_name: Jozsef L
full_name: Csicsvari, Jozsef L
id: 3FA14672-F248-11E8-B48F-1D18A9856A87
last_name: Csicsvari
orcid: 0000-0002-5193-4036
citation:
ama: Nardin M, Käfer K, Csicsvari JL. The generalized spatial representation in
the prefrontal cortex is inherited from the hippocampus. bioRxiv. doi:10.1101/2021.09.30.462269
apa: Nardin, M., Käfer, K., & Csicsvari, J. L. (n.d.). The generalized spatial
representation in the prefrontal cortex is inherited from the hippocampus. bioRxiv.
Cold Spring Harbor Laboratory. https://doi.org/10.1101/2021.09.30.462269
chicago: Nardin, Michele, Karola Käfer, and Jozsef L Csicsvari. “The Generalized
Spatial Representation in the Prefrontal Cortex Is Inherited from the Hippocampus.”
BioRxiv. Cold Spring Harbor Laboratory, n.d. https://doi.org/10.1101/2021.09.30.462269.
ieee: M. Nardin, K. Käfer, and J. L. Csicsvari, “The generalized spatial representation
in the prefrontal cortex is inherited from the hippocampus,” bioRxiv. Cold
Spring Harbor Laboratory.
ista: Nardin M, Käfer K, Csicsvari JL. The generalized spatial representation in
the prefrontal cortex is inherited from the hippocampus. bioRxiv, 10.1101/2021.09.30.462269.
mla: Nardin, Michele, et al. “The Generalized Spatial Representation in the Prefrontal
Cortex Is Inherited from the Hippocampus.” BioRxiv, Cold Spring Harbor
Laboratory, doi:10.1101/2021.09.30.462269.
short: M. Nardin, K. Käfer, J.L. Csicsvari, BioRxiv (n.d.).
date_created: 2021-10-04T06:28:32Z
date_published: 2021-10-02T00:00:00Z
date_updated: 2021-10-05T12:34:26Z
day: '02'
department:
- _id: GradSch
- _id: JoCs
doi: 10.1101/2021.09.30.462269
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.biorxiv.org/content/10.1101/2021.09.30.462269
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 257BBB4C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '607616'
name: Inter-and intracellular signalling in schizophrenia
publication: bioRxiv
publication_status: submitted
publisher: Cold Spring Harbor Laboratory
status: public
title: The generalized spatial representation in the prefrontal cortex is inherited
from the hippocampus
type: preprint
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10124'
abstract:
- lang: eng
text: The transport of macromolecules and nanoscopic particles to a target cellular
site is a crucial aspect in many physiological processes. This directional motion
is generally controlled via active mechanical and chemical processes. Here we
show, by means of molecular dynamics simulations and an analytical theory, that
completely passive nanoparticles can exhibit directional motion when embedded
in non-uniform mechanical environments. Specifically, we study the motion of a
passive nanoparticle adhering to a mechanically non-uniform elastic membrane.
We observe a non-monotonic affinity of the particle to the membrane as a function
of the membrane’s rigidity, which results in the particle transport. This transport
can be both up or down the rigidity gradient, depending on the absolute values
of the rigidities that the gradient spans across. We conclude that rigidity gradients
can be used to direct average motion of passive macromolecules and nanoparticles
on deformable membranes, resulting in the preferential accumulation of the macromolecules
in regions of certain mechanical properties.
acknowledgement: We acknowledge support from the Engineering and Physical Sciences
Research Council (A.P. and A.Š.), the Royal Society (A.Š.) and the European Research
Council (I.P. and A.Š.).
article_processing_charge: No
article_type: original
author:
- first_name: Ivan
full_name: Palaia, Ivan
last_name: Palaia
- first_name: Alexandru
full_name: Paraschiv, Alexandru
last_name: Paraschiv
- first_name: Vincent
full_name: Debets, Vincent
last_name: Debets
- first_name: Cornelis
full_name: Storm, Cornelis
last_name: Storm
- first_name: Anđela
full_name: Šarić, Anđela
id: bf63d406-f056-11eb-b41d-f263a6566d8b
last_name: Šarić
orcid: 0000-0002-7854-2139
citation:
ama: Palaia I, Paraschiv A, Debets V, Storm C, Šarić A. Durotaxis of passive nanoparticles
on elastic membranes. ACS Nano. 2021. doi:10.1021/acsnano.1c02777
apa: Palaia, I., Paraschiv, A., Debets, V., Storm, C., & Šarić, A. (2021). Durotaxis
of passive nanoparticles on elastic membranes. ACS Nano. American Chemical
Society. https://doi.org/10.1021/acsnano.1c02777
chicago: Palaia, Ivan, Alexandru Paraschiv, Vincent Debets, Cornelis Storm, and
Anđela Šarić. “Durotaxis of Passive Nanoparticles on Elastic Membranes.” ACS
Nano. American Chemical Society, 2021. https://doi.org/10.1021/acsnano.1c02777 .
ieee: I. Palaia, A. Paraschiv, V. Debets, C. Storm, and A. Šarić, “Durotaxis of
passive nanoparticles on elastic membranes,” ACS Nano. American Chemical
Society, 2021.
ista: Palaia I, Paraschiv A, Debets V, Storm C, Šarić A. 2021. Durotaxis of passive
nanoparticles on elastic membranes. ACS Nano.
mla: Palaia, Ivan, et al. “Durotaxis of Passive Nanoparticles on Elastic Membranes.”
ACS Nano, American Chemical Society, 2021, doi:10.1021/acsnano.1c02777 .
short: I. Palaia, A. Paraschiv, V. Debets, C. Storm, A. Šarić, ACS Nano (2021).
date_created: 2021-10-12T07:31:21Z
date_published: 2021-09-22T00:00:00Z
date_updated: 2021-10-12T09:50:19Z
day: '22'
doi: '10.1021/acsnano.1c02777 '
extern: '1'
external_id:
pmid:
- '34550677 '
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.biorxiv.org/content/10.1101/2021.04.01.438065
month: '09'
oa: 1
oa_version: Preprint
pmid: 1
publication: ACS Nano
publication_status: published
publisher: American Chemical Society
quality_controlled: '1'
status: public
title: Durotaxis of passive nanoparticles on elastic membranes
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10125'
abstract:
- lang: eng
text: Living systems propagate by undergoing rounds of cell growth and division.
Cell division is at heart a physical process that requires mechanical forces,
usually exerted by protein assemblies. Here we developed the first physical model
for the division of archaeal cells, which despite their structural simplicity
share machinery and evolutionary origins with eukaryotes. We show how active geometry
changes of elastic ESCRT-III filaments, coupled to filament disassembly, are sufficient
to efficiently split the cell. We explore how the non-equilibrium processes that
govern the filament behaviour impact the resulting cell division. We show how
a quantitative comparison between our simulations and dynamic data for ESCRTIII-mediated
division in Sulfolobus acidocaldarius, the closest archaeal relative to eukaryotic
cells that can currently be cultured in the lab, and reveal the most likely physical
mechanism behind its division.
acknowledgement: We acknowledge support from the Biotechnology and Biological Sciences
Research Council (L.H.K.), EPSRC (A.E.H), UCL IPLS (T.Y and D. H.), Wellcome Trust
(203276/Z/16/Z, A.P., S.C., R. H., B.B.), Volkswagen Foundation (Az 96727, A.P.,
B.B., A.Š.), MRC (MC CF1226, R.H., B.B., A.Š.), the ERC grant (”NEPA” 802960, A.Š.),
the Royal Society (C.V.-H., A.Š.), the UK Materials and Molecular Modelling Hub
for computational resources (EP/P020194/1).
article_processing_charge: No
author:
- first_name: L.
full_name: Harker-Kirschneck, L.
last_name: Harker-Kirschneck
- first_name: A. E.
full_name: Hafner, A. E.
last_name: Hafner
- first_name: T.
full_name: Yao, T.
last_name: Yao
- first_name: A.
full_name: Pulschen, A.
last_name: Pulschen
- first_name: F.
full_name: Hurtig, F.
last_name: Hurtig
- first_name: C.
full_name: Vanhille-Campos, C.
last_name: Vanhille-Campos
- first_name: D.
full_name: Hryniuk, D.
last_name: Hryniuk
- first_name: S.
full_name: Culley, S.
last_name: Culley
- first_name: R.
full_name: Henriques, R.
last_name: Henriques
- first_name: B.
full_name: Baum, B.
last_name: Baum
- first_name: Anđela
full_name: Šarić, Anđela
id: bf63d406-f056-11eb-b41d-f263a6566d8b
last_name: Šarić
orcid: 0000-0002-7854-2139
citation:
ama: Harker-Kirschneck L, Hafner AE, Yao T, et al. Physical mechanisms of ESCRT-III-driven
cell division in archaea. bioRxiv. doi:10.1101/2021.03.23.436559
apa: Harker-Kirschneck, L., Hafner, A. E., Yao, T., Pulschen, A., Hurtig, F., Vanhille-Campos,
C., … Šarić, A. (n.d.). Physical mechanisms of ESCRT-III-driven cell division
in archaea. bioRxiv. Cold Spring Harbor Laboratory. https://doi.org/10.1101/2021.03.23.436559
chicago: Harker-Kirschneck, L., A. E. Hafner, T. Yao, A. Pulschen, F. Hurtig, C.
Vanhille-Campos, D. Hryniuk, et al. “Physical Mechanisms of ESCRT-III-Driven Cell
Division in Archaea.” BioRxiv. Cold Spring Harbor Laboratory, n.d. https://doi.org/10.1101/2021.03.23.436559.
ieee: L. Harker-Kirschneck et al., “Physical mechanisms of ESCRT-III-driven
cell division in archaea,” bioRxiv. Cold Spring Harbor Laboratory.
ista: Harker-Kirschneck L, Hafner AE, Yao T, Pulschen A, Hurtig F, Vanhille-Campos
C, Hryniuk D, Culley S, Henriques R, Baum B, Šarić A. Physical mechanisms of ESCRT-III-driven
cell division in archaea. bioRxiv, 10.1101/2021.03.23.436559.
mla: Harker-Kirschneck, L., et al. “Physical Mechanisms of ESCRT-III-Driven Cell
Division in Archaea.” BioRxiv, Cold Spring Harbor Laboratory, doi:10.1101/2021.03.23.436559.
short: L. Harker-Kirschneck, A.E. Hafner, T. Yao, A. Pulschen, F. Hurtig, C. Vanhille-Campos,
D. Hryniuk, S. Culley, R. Henriques, B. Baum, A. Šarić, BioRxiv (n.d.).
date_created: 2021-10-12T07:45:07Z
date_published: 2021-03-23T00:00:00Z
date_updated: 2021-10-12T09:50:26Z
day: '23'
doi: 10.1101/2021.03.23.436559
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.biorxiv.org/content/10.1101/2021.03.23.436559
month: '03'
oa: 1
oa_version: Preprint
publication: bioRxiv
publication_status: submitted
publisher: Cold Spring Harbor Laboratory
status: public
title: Physical mechanisms of ESCRT-III-driven cell division in archaea
type: preprint
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10144'
abstract:
- lang: eng
text: FGFs and their high-affinity receptors (FGFRs) play key roles in development,
tissue repair, and disease. Because FGFRs bind overlapping sets of ligands, their
individual functions cannot be determined using ligand stimulation. Here, we generated
a light-activated FGFR2 variant (OptoR2) to selectively activate signaling by
the major FGFR in keratinocytes. Illumination of OptoR2-expressing HEK 293T cells
activated FGFR signaling with remarkable temporal precision and promoted cell
migration and proliferation. In murine and human keratinocytes, OptoR2 activation
rapidly induced the classical FGFR signaling pathways and expression of FGF target
genes. Surprisingly, multi-level counter-regulation occurred in keratinocytes
in vitro and in transgenic mice in vivo, including OptoR2 down-regulation and
loss of responsiveness to light activation. These results demonstrate unexpected
cell type-specific limitations of optogenetic FGFRs in long-term in vitro and
in vivo settings and highlight the complex consequences of transferring optogenetic
cell signaling tools into their relevant cellular contexts.
acknowledgement: We thank Connor Richterich and Patricia Reinert, ETH Zurich, for
invaluable experimental help; Manuela Pérez Berlanga, University Zurich, for help
with the confocal imaging; Lukas Fischer for help with electrical engineering; Thomas
Hennek, Sol Taguinod, and Dr. Stephan Sonntag, EPIC Phenomics Center, ETH Zürich,
for the generation and maintenance of K14-OptoR2 mice; and Dr. Petra Boukamp, Leibniz
Institute, Düsseldorf, Germany, for early-passage HaCaT keratinocytes. This work
was supported by the ETH Zurich (grant ETH-06 15-1 to S Werner and L Maddaluno),
the Swiss National Science Foundation (grant 31003B-189364 to S Werner), and a Marie
Curie postdoctoral fellowship from the European Union (to L Maddaluno).
article_number: e202101100
article_processing_charge: Yes
article_type: original
author:
- first_name: Theresa
full_name: Rauschendorfer, Theresa
last_name: Rauschendorfer
- first_name: Selina
full_name: Gurri, Selina
last_name: Gurri
- first_name: Irina
full_name: Heggli, Irina
last_name: Heggli
- first_name: Luigi
full_name: Maddaluno, Luigi
last_name: Maddaluno
- first_name: Michael
full_name: Meyer, Michael
last_name: Meyer
- first_name: Álvaro
full_name: Inglés Prieto, Álvaro
id: 2A9DB292-F248-11E8-B48F-1D18A9856A87
last_name: Inglés Prieto
orcid: 0000-0002-5409-8571
- first_name: Harald L
full_name: Janovjak, Harald L
id: 33BA6C30-F248-11E8-B48F-1D18A9856A87
last_name: Janovjak
orcid: 0000-0002-8023-9315
- first_name: Sabine
full_name: Werner, Sabine
last_name: Werner
citation:
ama: Rauschendorfer T, Gurri S, Heggli I, et al. Acute and chronic effects of a
light-activated FGF receptor in keratinocytes in vitro and in mice. Life Science
Alliance. 2021;4(11). doi:10.26508/lsa.202101100
apa: Rauschendorfer, T., Gurri, S., Heggli, I., Maddaluno, L., Meyer, M., Inglés
Prieto, Á., … Werner, S. (2021). Acute and chronic effects of a light-activated
FGF receptor in keratinocytes in vitro and in mice. Life Science Alliance.
Life Science Alliance. https://doi.org/10.26508/lsa.202101100
chicago: Rauschendorfer, Theresa, Selina Gurri, Irina Heggli, Luigi Maddaluno, Michael
Meyer, Álvaro Inglés Prieto, Harald L Janovjak, and Sabine Werner. “Acute and
Chronic Effects of a Light-Activated FGF Receptor in Keratinocytes in Vitro and
in Mice.” Life Science Alliance. Life Science Alliance, 2021. https://doi.org/10.26508/lsa.202101100.
ieee: T. Rauschendorfer et al., “Acute and chronic effects of a light-activated
FGF receptor in keratinocytes in vitro and in mice,” Life Science Alliance,
vol. 4, no. 11. Life Science Alliance, 2021.
ista: Rauschendorfer T, Gurri S, Heggli I, Maddaluno L, Meyer M, Inglés Prieto Á,
Janovjak HL, Werner S. 2021. Acute and chronic effects of a light-activated FGF
receptor in keratinocytes in vitro and in mice. Life Science Alliance. 4(11),
e202101100.
mla: Rauschendorfer, Theresa, et al. “Acute and Chronic Effects of a Light-Activated
FGF Receptor in Keratinocytes in Vitro and in Mice.” Life Science Alliance,
vol. 4, no. 11, e202101100, Life Science Alliance, 2021, doi:10.26508/lsa.202101100.
short: T. Rauschendorfer, S. Gurri, I. Heggli, L. Maddaluno, M. Meyer, Á. Inglés
Prieto, H.L. Janovjak, S. Werner, Life Science Alliance 4 (2021).
date_created: 2021-10-17T22:01:16Z
date_published: 2021-09-21T00:00:00Z
date_updated: 2022-08-31T14:01:56Z
day: '21'
ddc:
- '576'
doi: 10.26508/lsa.202101100
extern: '1'
external_id:
pmid:
- '34548382'
file:
- access_level: open_access
checksum: 89fb95b211dbe8678809e7cca4626952
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-18T14:48:06Z
date_updated: 2021-10-18T14:48:06Z
file_id: '10152'
file_name: 2021_LifeScAlliance_Rauschendorfer.pdf
file_size: 2055981
relation: main_file
success: 1
file_date_updated: 2021-10-18T14:48:06Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '11'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
pmid: 1
publication: Life Science Alliance
publication_identifier:
eissn:
- 2575-1077
publication_status: published
publisher: Life Science Alliance
quality_controlled: '1'
scopus_import: '1'
status: public
title: Acute and chronic effects of a light-activated FGF receptor in keratinocytes
in vitro and in mice
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2021'
...
---
_id: '10153'
abstract:
- lang: eng
text: "Gradual typing is a principled means for mixing typed and untyped code. But
typed and untyped code often exhibit different programming patterns. There is
already substantial research investigating gradually giving types to code exhibiting
typical untyped patterns, and some research investigating gradually removing types
from code exhibiting typical typed patterns. This paper investigates how to extend
these established gradual-typing concepts to give formal guarantees not only about
how to change types as code evolves but also about how to change such programming
patterns as well.\r\n\r\nIn particular, we explore mixing untyped \"structural\"
code with typed \"nominal\" code in an object-oriented language. But whereas previous
work only allowed \"nominal\" objects to be treated as \"structural\" objects,
we also allow \"structural\" objects to dynamically acquire certain nominal types,
namely interfaces. We present a calculus that supports such \"cross-paradigm\"
code migration and interoperation in a manner satisfying both the static and dynamic
gradual guarantees, and demonstrate that the calculus can be implemented efficiently."
acknowledgement: "We thank the reviewers for their valuable suggestions towards improving
the paper. We also \r\nthank Mae Milano and Adrian Sampson, as well as the members
of the Programming Languages Discussion Group at Cornell University and of the Programming
Research Laboratory at Northeastern University, for their helpful feedback on preliminary
findings of this work.\r\n\r\nThis material is based upon work supported in part
by the National Science Foundation (NSF) through grant CCF-1350182 and the Austrian
Science Fund (FWF) through grant Z211-N23 (Wittgenstein~Award).\r\nAny opinions,
findings, and conclusions or recommendations expressed in this material are those
of the authors and do not necessarily reflect the views of the NSF or the FWF."
article_number: '127'
article_processing_charge: No
article_type: original
author:
- first_name: Fabian
full_name: Mühlböck, Fabian
id: 6395C5F6-89DF-11E9-9C97-6BDFE5697425
last_name: Mühlböck
orcid: 0000-0003-1548-0177
- first_name: Ross
full_name: Tate, Ross
last_name: Tate
citation:
ama: Mühlböck F, Tate R. Transitioning from structural to nominal code with efficient
gradual typing. Proceedings of the ACM on Programming Languages. 2021;5.
doi:10.1145/3485504
apa: 'Mühlböck, F., & Tate, R. (2021). Transitioning from structural to nominal
code with efficient gradual typing. Proceedings of the ACM on Programming Languages.
Chicago, IL, United States: Association for Computing Machinery. https://doi.org/10.1145/3485504'
chicago: Mühlböck, Fabian, and Ross Tate. “Transitioning from Structural to Nominal
Code with Efficient Gradual Typing.” Proceedings of the ACM on Programming
Languages. Association for Computing Machinery, 2021. https://doi.org/10.1145/3485504.
ieee: F. Mühlböck and R. Tate, “Transitioning from structural to nominal code with
efficient gradual typing,” Proceedings of the ACM on Programming Languages,
vol. 5. Association for Computing Machinery, 2021.
ista: Mühlböck F, Tate R. 2021. Transitioning from structural to nominal code with
efficient gradual typing. Proceedings of the ACM on Programming Languages. 5,
127.
mla: Mühlböck, Fabian, and Ross Tate. “Transitioning from Structural to Nominal
Code with Efficient Gradual Typing.” Proceedings of the ACM on Programming
Languages, vol. 5, 127, Association for Computing Machinery, 2021, doi:10.1145/3485504.
short: F. Mühlböck, R. Tate, Proceedings of the ACM on Programming Languages 5 (2021).
conference:
end_date: 2021-10-23
location: Chicago, IL, United States
name: 'OOPSLA: Object-Oriented Programming, Systems, Languages, and Applications'
start_date: 2021-10-17
date_created: 2021-10-19T12:48:44Z
date_published: 2021-10-15T00:00:00Z
date_updated: 2021-11-12T11:30:07Z
day: '15'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1145/3485504
file:
- access_level: open_access
checksum: 71011efd2da771cafdec7f0d9693f8c1
content_type: application/pdf
creator: fmuehlbo
date_created: 2021-10-19T12:52:23Z
date_updated: 2021-10-19T12:52:23Z
file_id: '10154'
file_name: monnom-oopsla21.pdf
file_size: 770269
relation: main_file
success: 1
file_date_updated: 2021-10-19T12:52:23Z
has_accepted_license: '1'
intvolume: ' 5'
keyword:
- gradual typing
- gradual guarantee
- nominal
- structural
- call tags
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Transitioning from structural to nominal code with efficient gradual typing
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 5
year: '2021'
...
---
_id: '10148'
abstract:
- lang: eng
text: Tactile feedback of an object’s surface enables us to discern its material
properties and affordances. This understanding is used in digital fabrication
processes by creating objects with high-resolution surface variations to influence
a user’s tactile perception. As the design of such surface haptics commonly relies
on knowledge from real-life experiences, it is unclear how to adapt this information
for digital design methods. In this work, we investigate replicating the haptics
of real materials. Using an existing process for capturing an object’s microgeometry,
we digitize and reproduce the stable surface information of a set of 15 fabric
samples. In a psychophysical experiment, we evaluate the tactile qualities of
our set of original samples and their replicas. From our results, we see that
direct reproduction of surface variations is able to influence different psychophysical
dimensions of the tactile perception of surface textures. While the fabrication
process did not preserve all properties, our approach underlines that replication
of surface microgeometries benefits fabrication methods in terms of haptic perception
by covering a large range of tactile variations. Moreover, by changing the surface
structure of a single fabricated material, its material perception can be influenced.
We conclude by proposing strategies for capturing and reproducing digitized textures
to better resemble the perceived haptics of the originals.
acknowledgement: Our gratitude goes out to Kamila Mushkina, Akhmajon Makhsadov, Jordan
Espenshade, Bruno Fruchard, Roland Bennewitz, and Robert Drumm. This project has
received funding from the EU’s Horizon 2020 research and innovation programme, under
the Marie Skłodowska-Curie grant agreement No 642841 (DISTRO).
article_processing_charge: No
author:
- first_name: Donald
full_name: Degraen, Donald
last_name: Degraen
- first_name: Michael
full_name: Piovarci, Michael
id: 62E473F4-5C99-11EA-A40E-AF823DDC885E
last_name: Piovarci
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Antonio
full_name: Kruger, Antonio
last_name: Kruger
citation:
ama: 'Degraen D, Piovarci M, Bickel B, Kruger A. Capturing tactile properties of
real surfaces for haptic reproduction. In: 34th Annual ACM Symposium. Association
for Computing Machinery; 2021:954-971. doi:10.1145/3472749.3474798'
apa: 'Degraen, D., Piovarci, M., Bickel, B., & Kruger, A. (2021). Capturing
tactile properties of real surfaces for haptic reproduction. In 34th Annual
ACM Symposium (pp. 954–971). Virtual: Association for Computing Machinery.
https://doi.org/10.1145/3472749.3474798'
chicago: Degraen, Donald, Michael Piovarci, Bernd Bickel, and Antonio Kruger. “Capturing
Tactile Properties of Real Surfaces for Haptic Reproduction.” In 34th Annual
ACM Symposium, 954–71. Association for Computing Machinery, 2021. https://doi.org/10.1145/3472749.3474798.
ieee: D. Degraen, M. Piovarci, B. Bickel, and A. Kruger, “Capturing tactile properties
of real surfaces for haptic reproduction,” in 34th Annual ACM Symposium,
Virtual, 2021, pp. 954–971.
ista: 'Degraen D, Piovarci M, Bickel B, Kruger A. 2021. Capturing tactile properties
of real surfaces for haptic reproduction. 34th Annual ACM Symposium. UIST: User
Interface Software and Technology, 954–971.'
mla: Degraen, Donald, et al. “Capturing Tactile Properties of Real Surfaces for
Haptic Reproduction.” 34th Annual ACM Symposium, Association for Computing
Machinery, 2021, pp. 954–71, doi:10.1145/3472749.3474798.
short: D. Degraen, M. Piovarci, B. Bickel, A. Kruger, in:, 34th Annual ACM Symposium,
Association for Computing Machinery, 2021, pp. 954–971.
conference:
end_date: 2021-10-14
location: Virtual
name: 'UIST: User Interface Software and Technology'
start_date: 2021-10-10
date_created: 2021-10-18T07:36:11Z
date_published: 2021-10-10T00:00:00Z
date_updated: 2021-10-19T19:29:06Z
day: '10'
ddc:
- '000'
department:
- _id: BeBi
doi: 10.1145/3472749.3474798
ec_funded: 1
file:
- access_level: open_access
checksum: b0b26464df79b3a59e8ed82e4e19ab15
content_type: application/pdf
creator: bbickel
date_created: 2021-10-18T07:36:03Z
date_updated: 2021-10-18T07:36:03Z
file_id: '10149'
file_name: degraen-UIST2021_Texture_Appropriation_CR_preprint.pdf
file_size: 29796364
relation: main_file
file_date_updated: 2021-10-18T07:36:03Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Preprint
page: 954-971
project:
- _id: 2508E324-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '642841'
name: Distributed 3D Object Design
publication: 34th Annual ACM Symposium
publication_identifier:
isbn:
- 978-1-4503-8635-7
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Capturing tactile properties of real surfaces for haptic reproduction
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10174'
abstract:
- lang: eng
text: Quantitative stochastic homogenization of linear elliptic operators is by
now well-understood. In this contribution we move forward to the nonlinear setting
of monotone operators with p-growth. This first work is dedicated to a quantitative
two-scale expansion result. Fluctuations will be addressed in companion articles.
By treating the range of exponents 2≤p<∞ in dimensions d≤3, we are able to consider
genuinely nonlinear elliptic equations and systems such as −∇⋅A(x)(1+|∇u|p−2)∇u=f
(with A random, non-necessarily symmetric) for the first time. When going from
p=2 to p>2, the main difficulty is to analyze the associated linearized operator,
whose coefficients are degenerate, unbounded, and depend on the random input A
via the solution of a nonlinear equation. One of our main achievements is the
control of this intricate nonlinear dependence, leading to annealed Meyers' estimates
for the linearized operator, which are key to the quantitative two-scale expansion
result.
acknowledgement: The authors warmly thank Mitia Duerinckx for discussions on annealed
estimates, and Mathias Schäffner for pointing out that the conditions of [14] apply
to ̄a in the setting of Theorem 2.2 and for discussions on regularity theory for
operators with non-standard growth conditions. The authors received financial support
from the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (Grant Agreement n◦ 864066).
article_number: '2104.04263'
article_processing_charge: No
author:
- first_name: Nicolas
full_name: Clozeau, Nicolas
id: fea1b376-906f-11eb-847d-b2c0cf46455b
last_name: Clozeau
- first_name: Antoine
full_name: Gloria, Antoine
last_name: Gloria
citation:
ama: 'Clozeau N, Gloria A. Quantitative nonlinear homogenization: control of oscillations.
arXiv.'
apa: 'Clozeau, N., & Gloria, A. (n.d.). Quantitative nonlinear homogenization:
control of oscillations. arXiv.'
chicago: 'Clozeau, Nicolas, and Antoine Gloria. “Quantitative Nonlinear Homogenization:
Control of Oscillations.” ArXiv, n.d.'
ieee: 'N. Clozeau and A. Gloria, “Quantitative nonlinear homogenization: control
of oscillations,” arXiv. .'
ista: 'Clozeau N, Gloria A. Quantitative nonlinear homogenization: control of oscillations.
arXiv, 2104.04263.'
mla: 'Clozeau, Nicolas, and Antoine Gloria. “Quantitative Nonlinear Homogenization:
Control of Oscillations.” ArXiv, 2104.04263.'
short: N. Clozeau, A. Gloria, ArXiv (n.d.).
date_created: 2021-10-23T10:50:55Z
date_published: 2021-04-09T00:00:00Z
date_updated: 2021-10-28T15:44:05Z
day: '09'
department:
- _id: JuFi
external_id:
arxiv:
- '2104.04263'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2104.04263
month: '04'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
status: public
title: 'Quantitative nonlinear homogenization: control of oscillations'
type: preprint
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
year: '2021'
...
---
_id: '10180'
abstract:
- lang: eng
text: The growing energy and performance costs of deep learning have driven the
community to reduce the size of neural networks by selectively pruning components.
Similarly to their biological counterparts, sparse networks generalize just as
well, sometimes even better than, the original dense networks. Sparsity promises
to reduce the memory footprint of regular networks to fit mobile devices, as well
as shorten training time for ever growing networks. In this paper, we survey prior
work on sparsity in deep learning and provide an extensive tutorial of sparsification
for both inference and training. We describe approaches to remove and add elements
of neural networks, different training strategies to achieve model sparsity, and
mechanisms to exploit sparsity in practice. Our work distills ideas from more
than 300 research papers and provides guidance to practitioners who wish to utilize
sparsity today, as well as to researchers whose goal is to push the frontier forward.
We include the necessary background on mathematical methods in sparsification,
describe phenomena such as early structure adaptation, the intricate relations
between sparsity and the training process, and show techniques for achieving acceleration
on real hardware. We also define a metric of pruned parameter efficiency that
could serve as a baseline for comparison of different sparse networks. We close
by speculating on how sparsity can improve future workloads and outline major
open problems in the field.
acknowledgement: "We thank Doug Burger, Steve Scott, Marco Heddes, and the respective
teams at Microsoft for inspiring discussions on the topic. We thank Angelika Steger
for uplifting debates about the connections to biological brains, Sidak Pal Singh
for his support regarding experimental results, and Utku Evci as well as Xin Wang
for comments on previous versions of this\r\nwork. Special thanks go to Bernhard
Schölkopf, our JMLR editor Samy Bengio, and the three anonymous reviewers who provided
excellent comprehensive, pointed, and deep review comments that improved the quality
of our manuscript significantly."
article_processing_charge: No
article_type: original
author:
- first_name: Torsten
full_name: Hoefler, Torsten
last_name: Hoefler
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Tal
full_name: Ben-Nun, Tal
last_name: Ben-Nun
- first_name: Nikoli
full_name: Dryden, Nikoli
last_name: Dryden
- first_name: Elena-Alexandra
full_name: Peste, Elena-Alexandra
id: 32D78294-F248-11E8-B48F-1D18A9856A87
last_name: Peste
citation:
ama: 'Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Peste E-A. Sparsity in deep
learning: Pruning and growth for efficient inference and training in neural networks.
Journal of Machine Learning Research. 2021;22(241):1-124.'
apa: 'Hoefler, T., Alistarh, D.-A., Ben-Nun, T., Dryden, N., & Peste, E.-A.
(2021). Sparsity in deep learning: Pruning and growth for efficient inference
and training in neural networks. Journal of Machine Learning Research.
Journal of Machine Learning Research.'
chicago: 'Hoefler, Torsten, Dan-Adrian Alistarh, Tal Ben-Nun, Nikoli Dryden, and
Elena-Alexandra Peste. “Sparsity in Deep Learning: Pruning and Growth for Efficient
Inference and Training in Neural Networks.” Journal of Machine Learning Research.
Journal of Machine Learning Research, 2021.'
ieee: 'T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, and E.-A. Peste, “Sparsity
in deep learning: Pruning and growth for efficient inference and training in neural
networks,” Journal of Machine Learning Research, vol. 22, no. 241. Journal
of Machine Learning Research, pp. 1–124, 2021.'
ista: 'Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Peste E-A. 2021. Sparsity in
deep learning: Pruning and growth for efficient inference and training in neural
networks. Journal of Machine Learning Research. 22(241), 1–124.'
mla: 'Hoefler, Torsten, et al. “Sparsity in Deep Learning: Pruning and Growth for
Efficient Inference and Training in Neural Networks.” Journal of Machine Learning
Research, vol. 22, no. 241, Journal of Machine Learning Research, 2021, pp.
1–124.'
short: T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, E.-A. Peste, Journal of
Machine Learning Research 22 (2021) 1–124.
date_created: 2021-10-24T22:01:34Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2022-05-13T09:36:08Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
external_id:
arxiv:
- '2102.00554'
file:
- access_level: open_access
checksum: 3389d9d01fc58f8fb4c1a53e14a8abbf
content_type: application/pdf
creator: cziletti
date_created: 2021-10-27T15:34:18Z
date_updated: 2021-10-27T15:34:18Z
file_id: '10192'
file_name: 2021_JMachLearnRes_Hoefler.pdf
file_size: 3527521
relation: main_file
success: 1
file_date_updated: 2021-10-27T15:34:18Z
has_accepted_license: '1'
intvolume: ' 22'
issue: '241'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.jmlr.org/papers/v22/21-0366.html
month: '09'
oa: 1
oa_version: Published Version
page: 1-124
publication: Journal of Machine Learning Research
publication_identifier:
eissn:
- 1533-7928
issn:
- 1532-4435
publication_status: published
publisher: Journal of Machine Learning Research
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Sparsity in deep learning: Pruning and growth for efficient inference and
training in 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2021'
...
---
_id: '10218'
abstract:
- lang: eng
text: 'Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node. In this work, we consider the more general setting where G
is an arbitrary graph, and present a technique for simulating protocols designed
for fully-connected networks in any connected regular graph. Our main result is
a simulation that is efficient on many interesting graph families: roughly, the
simulation overhead is polylogarithmic in the number of nodes, and quadratic in
the conductance of the graph. As an example, this implies that, in any regular
graph with conductance φ, both leader election and exact majority can be solved
in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at
most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient
population protocols for leader election and exact majority on graphs with good
expansion properties.'
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 840605.
alternative_title:
- LIPIcs
article_number: '43'
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical
population protocols. In: 35th International Symposium on Distributed Computing.
Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.43'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2021). Brief announcement:
Fast graphical population protocols. In 35th International Symposium on Distributed
Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.43'
chicago: 'Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement:
Fast Graphical Population Protocols.” In 35th International Symposium on Distributed
Computing, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
https://doi.org/10.4230/LIPIcs.DISC.2021.43.'
ieee: 'D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast
graphical population protocols,” in 35th International Symposium on Distributed
Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical
population protocols. 35th International Symposium on Distributed Computing. DISC:
Distributed Computing , LIPIcs, vol. 209, 43.'
mla: 'Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population
Protocols.” 35th International Symposium on Distributed Computing, vol.
209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.43.'
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium
on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing '
start_date: 2021-10-04
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2023-02-21T09:24:08Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.43
ec_funded: 1
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: fd2a690f6856d21247e9aa952b0e2885
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T08:16:44Z
date_updated: 2021-11-12T08:16:44Z
file_id: '10274'
file_name: 2021_LIPIcsDISC_Alistarh.pdf
file_size: 534219
relation: main_file
success: 1
file_date_updated: 2021-11-12T08:16:44Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Fast graphical population protocols'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '10217'
abstract:
- lang: eng
text: This paper gives tight logarithmic lower bounds on the solo step complexity
of leader election in an asynchronous shared-memory model with single-writer multi-reader
(SWMR) registers, for both deterministic and randomized obstruction-free algorithms.
The approach extends to lower bounds for deterministic and randomized obstruction-free
algorithms using multi-writer registers under bounded write concurrency, showing
a trade-off between the solo step complexity of a leader election algorithm, and
the worst-case number of stalls incurred by a processor in an execution.
acknowledgement: "Dan Alistarh: Supported in part by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 805223 ScaleML). Giorgi Nadiradze: Supported in part by the
European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (grant agreement No 805223 ScaleML). The authors would
like to thank the DISC anonymous reviewers for their useful\r\nfeedback and comments."
alternative_title:
- LIPIcs
article_number: '4'
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
citation:
ama: 'Alistarh D-A, Gelashvili R, Nadiradze G. Lower bounds for shared-memory leader
election under bounded write contention. In: 35th International Symposium on
Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik;
2021. doi:10.4230/LIPIcs.DISC.2021.4'
apa: 'Alistarh, D.-A., Gelashvili, R., & Nadiradze, G. (2021). Lower bounds
for shared-memory leader election under bounded write contention. In 35th International
Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss
Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.4'
chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Giorgi Nadiradze. “Lower Bounds
for Shared-Memory Leader Election under Bounded Write Contention.” In 35th
International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl
- Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.4.
ieee: D.-A. Alistarh, R. Gelashvili, and G. Nadiradze, “Lower bounds for shared-memory
leader election under bounded write contention,” in 35th International Symposium
on Distributed Computing, Freiburg, Germany, 2021, vol. 209.
ista: 'Alistarh D-A, Gelashvili R, Nadiradze G. 2021. Lower bounds for shared-memory
leader election under bounded write contention. 35th International Symposium on
Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 4.'
mla: Alistarh, Dan-Adrian, et al. “Lower Bounds for Shared-Memory Leader Election
under Bounded Write Contention.” 35th International Symposium on Distributed
Computing, vol. 209, 4, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.DISC.2021.4.
short: D.-A. Alistarh, R. Gelashvili, G. Nadiradze, in:, 35th International Symposium
on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing'
start_date: 2021-10-04
date_created: 2021-11-07T23:01:23Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2022-08-19T07:23:28Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.4
ec_funded: 1
file:
- access_level: open_access
checksum: b4cdc6668c899a601c5e6a96b8ca54d9
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T09:33:26Z
date_updated: 2021-11-12T09:33:26Z
file_id: '10277'
file_name: 2021_LIPIcsDISC_Alistarh.pdf
file_size: 706791
relation: main_file
success: 1
file_date_updated: 2021-11-12T09:33:26Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for shared-memory leader election under bounded write contention
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 209
year: '2021'
...
---
_id: '10216'
abstract:
- lang: eng
text: 'This paper reports a new concurrent graph data structure that supports updates
of both edges and vertices and queries: Breadth-first search, Single-source shortest-path,
and Betweenness centrality. The operations are provably linearizable and non-blocking.'
acknowledgement: "This work was partially funded by National Supercomputing Mission,
Govt. of India under the project “Concurrent and Distributed Programming primitives
and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).\r\n"
alternative_title:
- LIPIcs
article_number: '52'
article_processing_charge: No
author:
- first_name: Bapi
full_name: Chatterjee, Bapi
id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
- first_name: Sathya
full_name: Peri, Sathya
last_name: Peri
- first_name: Muktikanta
full_name: Sa, Muktikanta
last_name: Sa
citation:
ama: 'Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded
graphs with worst-case amortized bounds. In: 35th International Symposium on
Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik;
2021. doi:10.4230/LIPIcs.DISC.2021.52'
apa: 'Chatterjee, B., Peri, S., & Sa, M. (2021). Brief announcement: Non-blocking
dynamic unbounded graphs with worst-case amortized bounds. In 35th International
Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss
Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.52'
chicago: 'Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement:
Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In 35th
International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl
- Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.52.'
ieee: 'B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic
unbounded graphs with worst-case amortized bounds,” in 35th International Symposium
on Distributed Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic
unbounded graphs with worst-case amortized bounds. 35th International Symposium
on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.'
mla: 'Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded
Graphs with Worst-Case Amortized Bounds.” 35th International Symposium on Distributed
Computing, vol. 209, 52, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.DISC.2021.52.'
short: B. Chatterjee, S. Peri, M. Sa, in:, 35th International Symposium on Distributed
Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing'
start_date: 2021-10-04
date_created: 2021-11-07T23:01:23Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2021-11-12T09:42:55Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.52
external_id:
arxiv:
- '2003.01697'
file:
- access_level: open_access
checksum: 76546df112a0ba1166c864d33d7834e2
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T09:23:22Z
date_updated: 2021-11-12T09:23:22Z
file_id: '10276'
file_name: 2021_LIPIcsDISC_BChatterjee.pdf
file_size: 795860
relation: main_file
success: 1
file_date_updated: 2021-11-12T09:23:22Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Non-blocking dynamic unbounded graphs with worst-case
amortized bounds'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '10219'
abstract:
- lang: eng
text: We show that any algorithm that solves the sinkless orientation problem in
the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported
LOCAL is at least as strong as the usual LOCAL model, and as a corollary this
also gives a new, short and elementary proof that shows that the round complexity
of the sinkless orientation problem in the deterministic LOCAL model is Ω(log
n).
acknowledgement: "Janne H. Korhonen: Project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian
Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research
supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n"
alternative_title:
- LIPIcs
article_number: '58'
article_processing_charge: No
author:
- 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
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
citation:
ama: 'Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless
orientation is hard also in the supported LOCAL model. In: 35th International
Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum
für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.58'
apa: 'Korhonen, J., Paz, A., Rybicki, J., Schmid, S., & Suomela, J. (2021).
Brief announcement: Sinkless orientation is hard also in the supported LOCAL model.
In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg,
Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.58'
chicago: 'Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela.
“Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL
Model.” In 35th International Symposium on Distributed Computing, Vol.
209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.58.'
ieee: 'J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement:
Sinkless orientation is hard also in the supported LOCAL model,” in 35th International
Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement:
Sinkless orientation is hard also in the supported LOCAL model. 35th International
Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol.
209, 58.'
mla: 'Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard
Also in the Supported LOCAL Model.” 35th International Symposium on Distributed
Computing, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.DISC.2021.58.'
short: J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International
Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing '
start_date: 2021-10-04
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2021-11-12T09:37:18Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.58
ec_funded: 1
external_id:
arxiv:
- '2108.02655'
file:
- access_level: open_access
checksum: c43188dc2070bbd2bf5fd6fdaf9ce36d
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T08:27:42Z
date_updated: 2021-11-12T08:27:42Z
file_id: '10275'
file_name: 2021_LIPIcsDISC_Korhonen.pdf
file_size: 474242
relation: main_file
success: 1
file_date_updated: 2021-11-12T08:27:42Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Sinkless orientation is hard also in the supported LOCAL
model'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '10267'
abstract:
- lang: eng
text: Tropisms are among the most important growth responses for plant adaptation
to the surrounding environment. One of the most common tropisms is root gravitropism.
Root gravitropism enables the plant to anchor securely to the soil enabling the
absorption of water and nutrients. Most of the knowledge related to the plant
gravitropism has been acquired from the flowering plants, due to limited research
in non-seed plants. Limited research on non-seed plants is due in large part to
the lack of standard research methods. Here, we describe the experimental methods
to evaluate gravitropism in representative non-seed plant species, including the
non-vascular plant moss Physcomitrium patens, the early diverging extant vascular
plant lycophyte Selaginella moellendorffii and fern Ceratopteris richardii. In
addition, we introduce the methods used for statistical analysis of the root gravitropism
in non-seed plant species.
acknowledgement: The Ceratopteris richardii spores were obtained from the lab of Jo
Ann Banks at Purdue University. This work was supported by funding from the European
Union’s Horizon 2020 research and innovation program (ERC grant agreement number
742985), Austrian Science Fund (FWF, grant number I 3630-B25), IST Fellow program
and DOC Fellowship of the Austrian Academy of Sciences.
alternative_title:
- Methods in Molecular Biology
article_processing_charge: No
author:
- first_name: Yuzhou
full_name: Zhang, Yuzhou
id: 3B6137F2-F248-11E8-B48F-1D18A9856A87
last_name: Zhang
orcid: 0000-0003-2627-6956
- first_name: Lanxin
full_name: Li, Lanxin
id: 367EF8FA-F248-11E8-B48F-1D18A9856A87
last_name: Li
orcid: 0000-0002-5607-272X
- first_name: Jiří
full_name: Friml, Jiří
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
citation:
ama: 'Zhang Y, Li L, Friml J. Evaluation of gravitropism in non-seed plants. In:
Blancaflor EB, ed. Plant Gravitropism. Vol 2368. MIMB. Springer Nature;
2021:43-51. doi:10.1007/978-1-0716-1677-2_2'
apa: Zhang, Y., Li, L., & Friml, J. (2021). Evaluation of gravitropism in non-seed
plants. In E. B. Blancaflor (Ed.), Plant Gravitropism (Vol. 2368, pp. 43–51).
Springer Nature. https://doi.org/10.1007/978-1-0716-1677-2_2
chicago: Zhang, Yuzhou, Lanxin Li, and Jiří Friml. “Evaluation of Gravitropism in
Non-Seed Plants.” In Plant Gravitropism, edited by Elison B Blancaflor,
2368:43–51. MIMB. Springer Nature, 2021. https://doi.org/10.1007/978-1-0716-1677-2_2.
ieee: Y. Zhang, L. Li, and J. Friml, “Evaluation of gravitropism in non-seed plants,”
in Plant Gravitropism, vol. 2368, E. B. Blancaflor, Ed. Springer Nature,
2021, pp. 43–51.
ista: 'Zhang Y, Li L, Friml J. 2021.Evaluation of gravitropism in non-seed plants.
In: Plant Gravitropism. Methods in Molecular Biology, vol. 2368, 43–51.'
mla: Zhang, Yuzhou, et al. “Evaluation of Gravitropism in Non-Seed Plants.” Plant
Gravitropism, edited by Elison B Blancaflor, vol. 2368, Springer Nature, 2021,
pp. 43–51, doi:10.1007/978-1-0716-1677-2_2.
short: Y. Zhang, L. Li, J. Friml, in:, E.B. Blancaflor (Ed.), Plant Gravitropism,
Springer Nature, 2021, pp. 43–51.
date_created: 2021-11-11T09:26:10Z
date_published: 2021-10-14T00:00:00Z
date_updated: 2022-08-26T09:13:00Z
day: '14'
department:
- _id: JiFr
doi: 10.1007/978-1-0716-1677-2_2
ec_funded: 1
editor:
- first_name: Elison B
full_name: Blancaflor, Elison B
last_name: Blancaflor
external_id:
pmid:
- '34647246'
intvolume: ' 2368'
language:
- iso: eng
month: '10'
oa_version: None
page: 43-51
pmid: 1
project:
- _id: 261099A6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '742985'
name: Tracing Evolution of Auxin Transport and Polarity in Plants
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 26538374-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I03630
name: Molecular mechanisms of endocytic cargo recognition in plants
publication: Plant Gravitropism
publication_identifier:
eisbn:
- 978-1-0716-1677-2
isbn:
- 978-1-0716-1676-5
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: MIMB
status: public
title: Evaluation of gravitropism in non-seed plants
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2368
year: '2021'
...
---
_id: '10268'
abstract:
- lang: eng
text: The analysis of dynamic cellular processes such as plant cytokinesis stands
and falls with live-cell time-lapse confocal imaging. Conventional approaches
to time-lapse imaging of cell division in Arabidopsis root tips are tedious and
have low throughput. Here, we describe a protocol for long-term time-lapse simultaneous
imaging of multiple root tips on a vertical-stage confocal microscope with automated
root tracking. We also provide modifications of the basic protocol to implement
this imaging method in the analysis of genetic, pharmacological or laser ablation
wounding-mediated experimental manipulations. Our method dramatically improves
the efficiency of cell division time-lapse imaging by increasing the throughput,
while reducing the person-hour requirements of such experiments.
acknowledged_ssus:
- _id: Bio
acknowledgement: We thank B. De Rybel for allowing M.G. to work on this manuscript
during a postdoc in his laboratory, and EMBO for supporting M.G. with a Long-Term
fellowship (ALTF 1005-2019) during this time. We acknowledge the service and support
by the Bioimaging Facility at IST Austria, and finally, we thank A. Mally for proofreading
and correcting the manuscript.
alternative_title:
- Methods in Molecular Biology
article_processing_charge: No
author:
- first_name: Lukas
full_name: Hörmayer, Lukas
id: 2EEE7A2A-F248-11E8-B48F-1D18A9856A87
last_name: Hörmayer
- first_name: Jiří
full_name: Friml, Jiří
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
- first_name: Matous
full_name: Glanc, Matous
id: 1AE1EA24-02D0-11E9-9BAA-DAF4881429F2
last_name: Glanc
orcid: 0000-0003-0619-7783
citation:
ama: 'Hörmayer L, Friml J, Glanc M. Automated time-lapse imaging and manipulation
of cell divisions in Arabidopsis roots by vertical-stage confocal microscopy.
In: Plant Cell Division. Vol 2382. MIMB. Humana Press; 2021:105-114. doi:10.1007/978-1-0716-1744-1_6'
apa: Hörmayer, L., Friml, J., & Glanc, M. (2021). Automated time-lapse imaging
and manipulation of cell divisions in Arabidopsis roots by vertical-stage confocal
microscopy. In Plant Cell Division (Vol. 2382, pp. 105–114). Humana Press.
https://doi.org/10.1007/978-1-0716-1744-1_6
chicago: Hörmayer, Lukas, Jiří Friml, and Matous Glanc. “Automated Time-Lapse Imaging
and Manipulation of Cell Divisions in Arabidopsis Roots by Vertical-Stage Confocal
Microscopy.” In Plant Cell Division, 2382:105–14. MIMB. Humana Press, 2021.
https://doi.org/10.1007/978-1-0716-1744-1_6.
ieee: L. Hörmayer, J. Friml, and M. Glanc, “Automated time-lapse imaging and manipulation
of cell divisions in Arabidopsis roots by vertical-stage confocal microscopy,”
in Plant Cell Division, vol. 2382, Humana Press, 2021, pp. 105–114.
ista: 'Hörmayer L, Friml J, Glanc M. 2021.Automated time-lapse imaging and manipulation
of cell divisions in Arabidopsis roots by vertical-stage confocal microscopy.
In: Plant Cell Division. Methods in Molecular Biology, vol. 2382, 105–114.'
mla: Hörmayer, Lukas, et al. “Automated Time-Lapse Imaging and Manipulation of Cell
Divisions in Arabidopsis Roots by Vertical-Stage Confocal Microscopy.” Plant
Cell Division, vol. 2382, Humana Press, 2021, pp. 105–14, doi:10.1007/978-1-0716-1744-1_6.
short: L. Hörmayer, J. Friml, M. Glanc, in:, Plant Cell Division, Humana Press,
2021, pp. 105–114.
date_created: 2021-11-11T10:03:30Z
date_published: 2021-10-28T00:00:00Z
date_updated: 2022-06-03T06:47:06Z
day: '28'
department:
- _id: JiFr
doi: 10.1007/978-1-0716-1744-1_6
external_id:
pmid:
- '34705235'
intvolume: ' 2382'
language:
- iso: eng
month: '10'
oa_version: None
page: 105-114
pmid: 1
publication: Plant Cell Division
publication_identifier:
eisbn:
- 978-1-0716-1744-1
eissn:
- 1940-6029
isbn:
- 978-1-0716-1743-4
issn:
- 1064-3745
publication_status: published
publisher: Humana Press
quality_controlled: '1'
scopus_import: '1'
series_title: MIMB
status: public
title: Automated time-lapse imaging and manipulation of cell divisions in Arabidopsis
roots by vertical-stage confocal microscopy
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2382
year: '2021'
...