---
_id: '1607'
abstract:
- lang: eng
text: We consider the core algorithmic problems related to verification of systems
with respect to three classical quantitative properties, namely, the mean-payoff
property, the ratio property, and the minimum initial credit for energy property.
The algorithmic problem given a graph and a quantitative property asks to compute
the optimal value (the infimum value over all traces) from every node of the graph.
We consider graphs with constant treewidth, and it is well-known that the control-flow
graphs of most programs have constant treewidth. Let n denote the number of nodes
of a graph, m the number of edges (for constant treewidth graphs m=O(n)) and W
the largest absolute value of the weights. Our main theoretical results are as
follows. First, for constant treewidth graphs we present an algorithm that approximates
the mean-payoff value within a multiplicative factor of ϵ in time O(n⋅log(n/ϵ))
and linear space, as compared to the classical algorithms that require quadratic
time. Second, for the ratio property we present an algorithm that for constant
treewidth graphs works in time O(n⋅log(|a⋅b|))=O(n⋅log(n⋅W)), when the output
is ab, as compared to the previously best known algorithm with running time O(n2⋅log(n⋅W)).
Third, for the minimum initial credit problem we show that (i) for general graphs
the problem can be solved in O(n2⋅m) time and the associated decision problem
can be solved in O(n⋅m) time, improving the previous known O(n3⋅m⋅log(n⋅W)) and
O(n2⋅m) bounds, respectively; and (ii) for constant treewidth graphs we present
an algorithm that requires O(n⋅logn) time, improving the previous known O(n4⋅log(n⋅W))
bound. We have implemented some of our algorithms and show that they present a
significant speedup on standard benchmarks.
acknowledgement: 'The research was partly supported by Austrian Science Fund (FWF)
Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant
(279307: Graph Games), and Microsoft faculty fellows award.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster algorithms for quantitative
verification in constant treewidth graphs. In: Vol 9206. Springer; 2015:140-157.
doi:10.1007/978-3-319-21690-4_9'
apa: 'Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms
for quantitative verification in constant treewidth graphs (Vol. 9206, pp. 140–157).
Presented at the CAV: Computer Aided Verification, San Francisco, CA, USA: Springer.
https://doi.org/10.1007/978-3-319-21690-4_9'
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
“Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs,”
9206:140–57. Springer, 2015. https://doi.org/10.1007/978-3-319-21690-4_9.
ieee: 'K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Faster algorithms for
quantitative verification in constant treewidth graphs,” presented at the CAV:
Computer Aided Verification, San Francisco, CA, USA, 2015, vol. 9206, pp. 140–157.'
ista: 'Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for
quantitative verification in constant treewidth graphs. CAV: Computer Aided Verification,
LNCS, vol. 9206, 140–157.'
mla: Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification
in Constant Treewidth Graphs. Vol. 9206, Springer, 2015, pp. 140–57, doi:10.1007/978-3-319-21690-4_9.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Springer, 2015, pp.
140–157.
conference:
end_date: 2015-07-24
location: San Francisco, CA, USA
name: 'CAV: Computer Aided Verification'
start_date: 2015-07-18
date_created: 2018-12-11T11:52:59Z
date_published: 2015-07-16T00:00:00Z
date_updated: 2023-09-07T12:01:59Z
day: '16'
department:
- _id: KrCh
doi: 10.1007/978-3-319-21690-4_9
ec_funded: 1
intvolume: ' 9206'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1504.07384
month: '07'
oa: 1
oa_version: Preprint
page: 140 - 157
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '5560'
quality_controlled: '1'
related_material:
record:
- id: '5430'
relation: earlier_version
status: public
- id: '5437'
relation: earlier_version
status: public
- id: '821'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Faster algorithms for quantitative verification in constant treewidth graphs
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9206
year: '2015'
...
---
_id: '1714'
abstract:
- lang: eng
text: 'We present a flexible framework for the automated competitive analysis of
on-line scheduling algorithms for firm-deadline real-time tasks based on multi-objective
graphs: Given a task set and an on-line scheduling algorithm specified as a labeled
transition system, along with some optional safety, liveness, and/or limit-average
constraints for the adversary, we automatically compute the competitive ratio
of the algorithm w.r.t. A clairvoyant scheduler. We demonstrate the flexibility
and power of our approach by comparing the competitive ratio of several on-line
algorithms, including Dover, that have been proposed in the past, for various
task sets. Our experimental results reveal that none of these algorithms is universally
optimal, in the sense that there are task sets where other schedulers provide
better performance. Our framework is hence a very useful design tool for selecting
optimal algorithms for a given application.'
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: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Alexander
full_name: Kößler, Alexander
last_name: Kößler
- first_name: Ulrich
full_name: Schmid, Ulrich
last_name: Schmid
citation:
ama: 'Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. A framework for automated
competitive analysis of on-line scheduling of firm-deadline tasks. In: Real-Time
Systems Symposium. Vol 2015. IEEE; 2015:118-127. doi:10.1109/RTSS.2014.9'
apa: 'Chatterjee, K., Pavlogiannis, A., Kößler, A., & Schmid, U. (2015). A framework
for automated competitive analysis of on-line scheduling of firm-deadline tasks.
In Real-Time Systems Symposium (Vol. 2015, pp. 118–127). Rome, Italy: IEEE.
https://doi.org/10.1109/RTSS.2014.9'
chicago: Chatterjee, Krishnendu, Andreas Pavlogiannis, Alexander Kößler, and Ulrich
Schmid. “A Framework for Automated Competitive Analysis of On-Line Scheduling
of Firm-Deadline Tasks.” In Real-Time Systems Symposium, 2015:118–27. IEEE,
2015. https://doi.org/10.1109/RTSS.2014.9.
ieee: K. Chatterjee, A. Pavlogiannis, A. Kößler, and U. Schmid, “A framework for
automated competitive analysis of on-line scheduling of firm-deadline tasks,”
in Real-Time Systems Symposium, Rome, Italy, 2015, vol. 2015, no. January,
pp. 118–127.
ista: 'Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. 2015. A framework for automated
competitive analysis of on-line scheduling of firm-deadline tasks. Real-Time Systems
Symposium. RTSS: Real-Time Systems Symposium vol. 2015, 118–127.'
mla: Chatterjee, Krishnendu, et al. “A Framework for Automated Competitive Analysis
of On-Line Scheduling of Firm-Deadline Tasks.” Real-Time Systems Symposium,
vol. 2015, no. January, IEEE, 2015, pp. 118–27, doi:10.1109/RTSS.2014.9.
short: K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, in:, Real-Time Systems
Symposium, IEEE, 2015, pp. 118–127.
conference:
end_date: 2014-12-05
location: Rome, Italy
name: 'RTSS: Real-Time Systems Symposium'
start_date: 2014-12-02
date_created: 2018-12-11T11:53:37Z
date_published: 2015-01-15T00:00:00Z
date_updated: 2023-09-07T12:01:59Z
day: '15'
department:
- _id: KrCh
doi: 10.1109/RTSS.2014.9
intvolume: ' 2015'
issue: January
language:
- iso: eng
month: '01'
oa_version: None
page: 118 - 127
publication: Real-Time Systems Symposium
publication_status: published
publisher: IEEE
publist_id: '5417'
quality_controlled: '1'
related_material:
record:
- id: '5423'
relation: earlier_version
status: public
- id: '821'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: A framework for automated competitive analysis of on-line scheduling of firm-deadline
tasks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2015
year: '2015'
...
---
_id: '1633'
abstract:
- lang: eng
text: "We present a method for simulating brittle fracture under the assumptions
of quasi-static linear elastic fracture mechanics (LEFM). Using the boundary element
method (BEM) and Lagrangian crack-fronts, we produce highly detailed fracture
surfaces. The computational cost of the BEM is alleviated by using a low-resolution
mesh and interpolating the resulting stress intensity factors when propagating
the high-resolution crack-front.\r\n\r\nOur system produces physics-based fracture
surfaces with high spatial and temporal resolution, taking spatial variation of
material toughness and/or strength into account. It also allows for crack initiation
to be handled separately from crack propagation, which is not only more reasonable
from a physics perspective, but can also be used to control the simulation.\r\n\r\nSeparating
the resolution of the crack-front from the resolution of the computational mesh
increases the efficiency and therefore the amount of visual detail on the resulting
fracture surfaces. The BEM also allows us to re-use previously computed blocks
of the system matrix."
article_number: '151'
author:
- first_name: David
full_name: Hahn, David
id: 357A6A66-F248-11E8-B48F-1D18A9856A87
last_name: Hahn
- first_name: Christopher J
full_name: Wojtan, Christopher J
id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
last_name: Wojtan
orcid: 0000-0001-6646-5546
citation:
ama: 'Hahn D, Wojtan C. High-resolution brittle fracture simulation with boundary
elements. In: Vol 34. ACM; 2015. doi:10.1145/2766896'
apa: 'Hahn, D., & Wojtan, C. (2015). High-resolution brittle fracture simulation
with boundary elements (Vol. 34). Presented at the SIGGRAPH: Special Interest
Group on Computer Graphics and Interactive Techniques, Los Angeles, CA, United
States: ACM. https://doi.org/10.1145/2766896'
chicago: Hahn, David, and Chris Wojtan. “High-Resolution Brittle Fracture Simulation
with Boundary Elements,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766896.
ieee: 'D. Hahn and C. Wojtan, “High-resolution brittle fracture simulation with
boundary elements,” presented at the SIGGRAPH: Special Interest Group on Computer
Graphics and Interactive Techniques, Los Angeles, CA, United States, 2015, vol.
34, no. 4.'
ista: 'Hahn D, Wojtan C. 2015. High-resolution brittle fracture simulation with
boundary elements. SIGGRAPH: Special Interest Group on Computer Graphics and Interactive
Techniques vol. 34, 151.'
mla: Hahn, David, and Chris Wojtan. High-Resolution Brittle Fracture Simulation
with Boundary Elements. Vol. 34, no. 4, 151, ACM, 2015, doi:10.1145/2766896.
short: D. Hahn, C. Wojtan, in:, ACM, 2015.
conference:
end_date: 2015-08-13
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2015-08-09
date_created: 2018-12-11T11:53:09Z
date_published: 2015-07-27T00:00:00Z
date_updated: 2023-09-07T12:02:56Z
day: '27'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1145/2766896
ec_funded: 1
file:
- access_level: open_access
checksum: 955aee971983f6b6152bcc1c9b4a7c20
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:13Z
date_updated: 2020-07-14T12:45:07Z
file_id: '5131'
file_name: IST-2016-609-v1+1_FractureBEM.pdf
file_size: 20154270
relation: main_file
file_date_updated: 2020-07-14T12:45:07Z
has_accepted_license: '1'
intvolume: ' 34'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: 2533E772-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '638176'
name: Efficient Simulation of Natural Phenomena at Extremely Large Scales
publication_status: published
publisher: ACM
publist_id: '5522'
pubrep_id: '609'
quality_controlled: '1'
related_material:
record:
- id: '839'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: High-resolution brittle fracture simulation with boundary elements
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1537'
abstract:
- lang: eng
text: 3D amoeboid cell migration is central to many developmental and disease-related
processes such as cancer metastasis. Here, we identify a unique prototypic amoeboid
cell migration mode in early zebrafish embryos, termed stable-bleb migration.
Stable-bleb cells display an invariant polarized balloon-like shape with exceptional
migration speed and persistence. Progenitor cells can be reversibly transformed
into stable-bleb cells irrespective of their primary fate and motile characteristics
by increasing myosin II activity through biochemical or mechanical stimuli. Using
a combination of theory and experiments, we show that, in stable-bleb cells, cortical
contractility fluctuations trigger a stochastic switch into amoeboid motility,
and a positive feedback between cortical flows and gradients in contractility
maintains stable-bleb cell polarization. We further show that rearward cortical
flows drive stable-bleb cell migration in various adhesive and non-adhesive environments,
unraveling a highly versatile amoeboid migration phenotype.
acknowledged_ssus:
- _id: SSU
acknowledgement: 'We would like to thank R. Hausschild and E. Papusheva for technical
assistance and the service facilities at the IST Austria for continuous support.
The caRhoA plasmid was a kind gift of T. Kudoh and A. Takesono. We thank M. Piel
and E. Paluch for exchanging unpublished data. '
author:
- first_name: Verena
full_name: Ruprecht, Verena
id: 4D71A03A-F248-11E8-B48F-1D18A9856A87
last_name: Ruprecht
orcid: 0000-0003-4088-8633
- first_name: Stefan
full_name: Wieser, Stefan
id: 355AA5A0-F248-11E8-B48F-1D18A9856A87
last_name: Wieser
orcid: 0000-0002-2670-2217
- first_name: Andrew
full_name: Callan Jones, Andrew
last_name: Callan Jones
- first_name: Michael
full_name: Smutny, Michael
id: 3FE6E4E8-F248-11E8-B48F-1D18A9856A87
last_name: Smutny
orcid: 0000-0002-5920-9090
- first_name: Hitoshi
full_name: Morita, Hitoshi
id: 4C6E54C6-F248-11E8-B48F-1D18A9856A87
last_name: Morita
- first_name: Keisuke
full_name: Sako, Keisuke
id: 3BED66BE-F248-11E8-B48F-1D18A9856A87
last_name: Sako
orcid: 0000-0002-6453-8075
- first_name: Vanessa
full_name: Barone, Vanessa
id: 419EECCC-F248-11E8-B48F-1D18A9856A87
last_name: Barone
orcid: 0000-0003-2676-3367
- first_name: Monika
full_name: Ritsch Marte, Monika
last_name: Ritsch Marte
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
- first_name: Raphaël
full_name: Voituriez, Raphaël
last_name: Voituriez
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
citation:
ama: Ruprecht V, Wieser S, Callan Jones A, et al. Cortical contractility triggers
a stochastic switch to fast amoeboid cell motility. Cell. 2015;160(4):673-685.
doi:10.1016/j.cell.2015.01.008
apa: Ruprecht, V., Wieser, S., Callan Jones, A., Smutny, M., Morita, H., Sako, K.,
… Heisenberg, C.-P. J. (2015). Cortical contractility triggers a stochastic switch
to fast amoeboid cell motility. Cell. Cell Press. https://doi.org/10.1016/j.cell.2015.01.008
chicago: Ruprecht, Verena, Stefan Wieser, Andrew Callan Jones, Michael Smutny, Hitoshi
Morita, Keisuke Sako, Vanessa Barone, et al. “Cortical Contractility Triggers
a Stochastic Switch to Fast Amoeboid Cell Motility.” Cell. Cell Press,
2015. https://doi.org/10.1016/j.cell.2015.01.008.
ieee: V. Ruprecht et al., “Cortical contractility triggers a stochastic switch
to fast amoeboid cell motility,” Cell, vol. 160, no. 4. Cell Press, pp.
673–685, 2015.
ista: Ruprecht V, Wieser S, Callan Jones A, Smutny M, Morita H, Sako K, Barone V,
Ritsch Marte M, Sixt MK, Voituriez R, Heisenberg C-PJ. 2015. Cortical contractility
triggers a stochastic switch to fast amoeboid cell motility. Cell. 160(4), 673–685.
mla: Ruprecht, Verena, et al. “Cortical Contractility Triggers a Stochastic Switch
to Fast Amoeboid Cell Motility.” Cell, vol. 160, no. 4, Cell Press, 2015,
pp. 673–85, doi:10.1016/j.cell.2015.01.008.
short: V. Ruprecht, S. Wieser, A. Callan Jones, M. Smutny, H. Morita, K. Sako, V.
Barone, M. Ritsch Marte, M.K. Sixt, R. Voituriez, C.-P.J. Heisenberg, Cell 160
(2015) 673–685.
date_created: 2018-12-11T11:52:35Z
date_published: 2015-02-12T00:00:00Z
date_updated: 2023-09-07T12:05:08Z
day: '12'
ddc:
- '570'
department:
- _id: CaHe
- _id: MiSi
doi: 10.1016/j.cell.2015.01.008
file:
- access_level: open_access
checksum: 228d3edf40627d897b3875088a0ac51f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:21Z
date_updated: 2020-07-14T12:45:01Z
file_id: '5003'
file_name: IST-2016-484-v1+1_1-s2.0-S0092867415000094-main.pdf
file_size: 4362653
relation: main_file
file_date_updated: 2020-07-14T12:45:01Z
has_accepted_license: '1'
intvolume: ' 160'
issue: '4'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 673 - 685
project:
- _id: 2529486C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: T 560-B17
name: Cell- and Tissue Mechanics in Zebrafish Germ Layer Formation
- _id: 2527D5CC-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I 812-B12
name: Cell Cortex and Germ Layer Formation in Zebrafish Gastrulation
publication: Cell
publication_status: published
publisher: Cell Press
publist_id: '5634'
pubrep_id: '484'
quality_controlled: '1'
related_material:
record:
- id: '961'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Cortical contractility triggers a stochastic switch to fast amoeboid cell motility
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: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 160
year: '2015'
...
---
_id: '1591'
abstract:
- lang: eng
text: Auxin participates in a multitude of developmental processes, as well as responses
to environmental cues. Compared with other plant hormones, auxin exhibits a unique
property, as it undergoes directional, cell-to-cell transport facilitated by plasma
membrane-localized transport proteins. Among them, a prominent role has been ascribed
to the PIN family of auxin efflux facilitators. PIN proteins direct polar auxin
transport on account of their asymmetric subcellular localizations. In this review,
we provide an overview of the multiple developmental roles of PIN proteins, including
the atypical endoplasmic reticulum-localized members of the family, and look at
the family from an evolutionary perspective. Next, we cover the cell biological
and molecular aspects of PIN function, in particular the establishment of their
polar subcellular localization. Hormonal and environmental inputs into the regulation
of PIN action are summarized as well.
author:
- first_name: Maciek
full_name: Adamowski, Maciek
id: 45F536D2-F248-11E8-B48F-1D18A9856A87
last_name: Adamowski
orcid: 0000-0001-6463-5257
- first_name: Jirí
full_name: Friml, Jirí
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
citation:
ama: 'Adamowski M, Friml J. PIN-dependent auxin transport: Action, regulation, and
evolution. Plant Cell. 2015;27(1):20-32. doi:10.1105/tpc.114.134874'
apa: 'Adamowski, M., & Friml, J. (2015). PIN-dependent auxin transport: Action,
regulation, and evolution. Plant Cell. American Society of Plant Biologists.
https://doi.org/10.1105/tpc.114.134874'
chicago: 'Adamowski, Maciek, and Jiří Friml. “PIN-Dependent Auxin Transport: Action,
Regulation, and Evolution.” Plant Cell. American Society of Plant Biologists,
2015. https://doi.org/10.1105/tpc.114.134874.'
ieee: 'M. Adamowski and J. Friml, “PIN-dependent auxin transport: Action, regulation,
and evolution,” Plant Cell, vol. 27, no. 1. American Society of Plant Biologists,
pp. 20–32, 2015.'
ista: 'Adamowski M, Friml J. 2015. PIN-dependent auxin transport: Action, regulation,
and evolution. Plant Cell. 27(1), 20–32.'
mla: 'Adamowski, Maciek, and Jiří Friml. “PIN-Dependent Auxin Transport: Action,
Regulation, and Evolution.” Plant Cell, vol. 27, no. 1, American Society
of Plant Biologists, 2015, pp. 20–32, doi:10.1105/tpc.114.134874.'
short: M. Adamowski, J. Friml, Plant Cell 27 (2015) 20–32.
date_created: 2018-12-11T11:52:54Z
date_published: 2015-01-20T00:00:00Z
date_updated: 2023-09-07T12:06:09Z
day: '20'
department:
- _id: JiFr
doi: 10.1105/tpc.114.134874
external_id:
pmid:
- '25604445'
intvolume: ' 27'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4330589/
month: '01'
oa: 1
oa_version: Submitted Version
page: 20 - 32
pmid: 1
publication: Plant Cell
publication_status: published
publisher: American Society of Plant Biologists
publist_id: '5580'
quality_controlled: '1'
related_material:
record:
- id: '938'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: 'PIN-dependent auxin transport: Action, regulation, and evolution'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2015'
...
---
_id: '1677'
abstract:
- lang: eng
text: We consider real symmetric and complex Hermitian random matrices with the
additional symmetry hxy = hN-y,N-x. The matrix elements are independent (up to
the fourfold symmetry) and not necessarily identically distributed. This ensemble
naturally arises as the Fourier transform of a Gaussian orthogonal ensemble. Italso
occurs as the flip matrix model - an approximation of the two-dimensional Anderson
model at small disorder. We show that the density of states converges to the Wigner
semicircle law despite the new symmetry type. We also prove the local version
of the semicircle law on the optimal scale.
article_number: '103301'
author:
- first_name: Johannes
full_name: Alt, Johannes
id: 36D3D8B6-F248-11E8-B48F-1D18A9856A87
last_name: Alt
citation:
ama: Alt J. The local semicircle law for random matrices with a fourfold symmetry.
Journal of Mathematical Physics. 2015;56(10). doi:10.1063/1.4932606
apa: Alt, J. (2015). The local semicircle law for random matrices with a fourfold
symmetry. Journal of Mathematical Physics. American Institute of Physics.
https://doi.org/10.1063/1.4932606
chicago: Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold
Symmetry.” Journal of Mathematical Physics. American Institute of Physics,
2015. https://doi.org/10.1063/1.4932606.
ieee: J. Alt, “The local semicircle law for random matrices with a fourfold symmetry,”
Journal of Mathematical Physics, vol. 56, no. 10. American Institute of
Physics, 2015.
ista: Alt J. 2015. The local semicircle law for random matrices with a fourfold
symmetry. Journal of Mathematical Physics. 56(10), 103301.
mla: Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold
Symmetry.” Journal of Mathematical Physics, vol. 56, no. 10, 103301, American
Institute of Physics, 2015, doi:10.1063/1.4932606.
short: J. Alt, Journal of Mathematical Physics 56 (2015).
date_created: 2018-12-11T11:53:25Z
date_published: 2015-10-09T00:00:00Z
date_updated: 2023-09-07T12:38:08Z
day: '09'
department:
- _id: LaEr
doi: 10.1063/1.4932606
ec_funded: 1
intvolume: ' 56'
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1506.04683
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 258DCDE6-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '338804'
name: Random matrices, universality and disordered quantum systems
publication: Journal of Mathematical Physics
publication_status: published
publisher: American Institute of Physics
publist_id: '5472'
quality_controlled: '1'
related_material:
record:
- id: '149'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: The local semicircle law for random matrices with a fourfold symmetry
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 56
year: '2015'
...
---
_id: '1678'
abstract:
- lang: eng
text: High-throughput live-cell screens are intricate elements of systems biology
studies and drug discovery pipelines. Here, we demonstrate an optogenetics-assisted
method that avoids the need for chemical activators and reporters, reduces the
number of operational steps and increases information content in a cell-based
small-molecule screen against human protein kinases, including an orphan receptor
tyrosine kinase. This blueprint for all-optical screening can be adapted to many
drug targets and cellular processes.
acknowledgement: 'This work was supported by grants from the European Union Seventh
Framework Programme (CIG-303564 to H.J. and ERC-StG-311166 to S.M.B.N.), the Human
Frontier Science Program (RGY0084_2012 to H.J.) and the Herzfelder Foundation (to
M.G.). A.I.-P. was supported by a Ramon Areces fellowship, and E.R. by the graduate
program MolecularDrugTargets (Austrian Science Fund (FWF): W 1232) and a FemTech
fellowship (3580812 Austrian Research Promotion Agency).'
author:
- 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: Eva
full_name: Gschaider-Reichhart, Eva
id: 3FEE232A-F248-11E8-B48F-1D18A9856A87
last_name: Gschaider-Reichhart
orcid: 0000-0002-7218-7738
- first_name: Markus
full_name: Muellner, Markus
last_name: Muellner
- first_name: Matthias
full_name: Nowak, Matthias
id: 30845DAA-F248-11E8-B48F-1D18A9856A87
last_name: Nowak
- first_name: Sebastian
full_name: Nijman, Sebastian
last_name: Nijman
- first_name: Michael
full_name: Grusch, Michael
last_name: Grusch
- first_name: Harald L
full_name: Janovjak, Harald L
id: 33BA6C30-F248-11E8-B48F-1D18A9856A87
last_name: Janovjak
orcid: 0000-0002-8023-9315
citation:
ama: Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, et al. Light-assisted small-molecule
screening against protein kinases. Nature Chemical Biology. 2015;11(12):952-954.
doi:10.1038/nchembio.1933
apa: Inglés Prieto, Á., Gschaider-Reichhart, E., Muellner, M., Nowak, M., Nijman,
S., Grusch, M., & Janovjak, H. L. (2015). Light-assisted small-molecule screening
against protein kinases. Nature Chemical Biology. Nature Publishing Group.
https://doi.org/10.1038/nchembio.1933
chicago: Inglés Prieto, Álvaro, Eva Gschaider-Reichhart, Markus Muellner, Matthias
Nowak, Sebastian Nijman, Michael Grusch, and Harald L Janovjak. “Light-Assisted
Small-Molecule Screening against Protein Kinases.” Nature Chemical Biology.
Nature Publishing Group, 2015. https://doi.org/10.1038/nchembio.1933.
ieee: Á. Inglés Prieto et al., “Light-assisted small-molecule screening against
protein kinases,” Nature Chemical Biology, vol. 11, no. 12. Nature Publishing
Group, pp. 952–954, 2015.
ista: Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, Nowak M, Nijman S, Grusch
M, Janovjak HL. 2015. Light-assisted small-molecule screening against protein
kinases. Nature Chemical Biology. 11(12), 952–954.
mla: Inglés Prieto, Álvaro, et al. “Light-Assisted Small-Molecule Screening against
Protein Kinases.” Nature Chemical Biology, vol. 11, no. 12, Nature Publishing
Group, 2015, pp. 952–54, doi:10.1038/nchembio.1933.
short: Á. Inglés Prieto, E. Gschaider-Reichhart, M. Muellner, M. Nowak, S. Nijman,
M. Grusch, H.L. Janovjak, Nature Chemical Biology 11 (2015) 952–954.
date_created: 2018-12-11T11:53:25Z
date_published: 2015-10-12T00:00:00Z
date_updated: 2023-09-07T12:49:09Z
day: '12'
ddc:
- '571'
department:
- _id: HaJa
- _id: LifeSc
doi: 10.1038/nchembio.1933
ec_funded: 1
file:
- access_level: open_access
checksum: e9fb251dfcb7cd209b83f17867e61321
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:51Z
date_updated: 2020-07-14T12:45:12Z
file_id: '4842'
file_name: IST-2017-837-v1+1_ingles-prieto.pdf
file_size: 1308364
relation: main_file
file_date_updated: 2020-07-14T12:45:12Z
has_accepted_license: '1'
intvolume: ' 11'
issue: '12'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 952 - 954
project:
- _id: 25548C20-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '303564'
name: Microbial Ion Channels for Synthetic Neurobiology
- _id: 255BFFFA-B435-11E9-9278-68D0E5697425
grant_number: RGY0084/2012
name: In situ real-time imaging of neurotransmitter signaling using designer optical
sensors (HFSP Young Investigator)
- _id: 255A6082-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: W1232-B24
name: Molecular Drug Targets
publication: Nature Chemical Biology
publication_status: published
publisher: Nature Publishing Group
publist_id: '5471'
pubrep_id: '837'
quality_controlled: '1'
related_material:
record:
- id: '418'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Light-assisted small-molecule screening against protein kinases
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2015'
...
---
_id: '1576'
abstract:
- lang: eng
text: 'Gene expression is controlled primarily by interactions between transcription
factor proteins (TFs) and the regulatory DNA sequence, a process that can be captured
well by thermodynamic models of regulation. These models, however, neglect regulatory
crosstalk: the possibility that noncognate TFs could initiate transcription, with
potentially disastrous effects for the cell. Here, we estimate the importance
of crosstalk, suggest that its avoidance strongly constrains equilibrium models
of TF binding, and propose an alternative nonequilibrium scheme that implements
kinetic proofreading to suppress erroneous initiation. This proposal is consistent
with the observed covalent modifications of the transcriptional apparatus and
predicts increased noise in gene expression as a trade-off for improved specificity.
Using information theory, we quantify this trade-off to find when optimal proofreading
architectures are favored over their equilibrium counterparts. Such architectures
exhibit significant super-Poisson noise at low expression in steady state.'
article_number: '248101'
author:
- first_name: Sarah A
full_name: Cepeda Humerez, Sarah A
id: 3DEE19A4-F248-11E8-B48F-1D18A9856A87
last_name: Cepeda Humerez
- first_name: Georg
full_name: Rieckh, Georg
id: 34DA8BD6-F248-11E8-B48F-1D18A9856A87
last_name: Rieckh
- first_name: Gasper
full_name: Tkacik, Gasper
id: 3D494DCA-F248-11E8-B48F-1D18A9856A87
last_name: Tkacik
orcid: 0000-0002-6699-1455
citation:
ama: Cepeda Humerez SA, Rieckh G, Tkačik G. Stochastic proofreading mechanism alleviates
crosstalk in transcriptional regulation. Physical Review Letters. 2015;115(24).
doi:10.1103/PhysRevLett.115.248101
apa: Cepeda Humerez, S. A., Rieckh, G., & Tkačik, G. (2015). Stochastic proofreading
mechanism alleviates crosstalk in transcriptional regulation. Physical Review
Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.115.248101
chicago: Cepeda Humerez, Sarah A, Georg Rieckh, and Gašper Tkačik. “Stochastic Proofreading
Mechanism Alleviates Crosstalk in Transcriptional Regulation.” Physical Review
Letters. American Physical Society, 2015. https://doi.org/10.1103/PhysRevLett.115.248101.
ieee: S. A. Cepeda Humerez, G. Rieckh, and G. Tkačik, “Stochastic proofreading mechanism
alleviates crosstalk in transcriptional regulation,” Physical Review Letters,
vol. 115, no. 24. American Physical Society, 2015.
ista: Cepeda Humerez SA, Rieckh G, Tkačik G. 2015. Stochastic proofreading mechanism
alleviates crosstalk in transcriptional regulation. Physical Review Letters. 115(24),
248101.
mla: Cepeda Humerez, Sarah A., et al. “Stochastic Proofreading Mechanism Alleviates
Crosstalk in Transcriptional Regulation.” Physical Review Letters, vol.
115, no. 24, 248101, American Physical Society, 2015, doi:10.1103/PhysRevLett.115.248101.
short: S.A. Cepeda Humerez, G. Rieckh, G. Tkačik, Physical Review Letters 115 (2015).
date_created: 2018-12-11T11:52:49Z
date_published: 2015-12-08T00:00:00Z
date_updated: 2023-09-07T12:55:21Z
day: '08'
department:
- _id: GaTk
doi: 10.1103/PhysRevLett.115.248101
ec_funded: 1
intvolume: ' 115'
issue: '24'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1504.05716
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Physical Review Letters
publication_status: published
publisher: American Physical Society
publist_id: '5595'
quality_controlled: '1'
related_material:
record:
- id: '6473'
relation: part_of_dissertation
status: public
scopus_import: 1
status: public
title: Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 115
year: '2015'
...
---
_id: '8183'
abstract:
- lang: eng
text: "We study conditions under which a finite simplicial complex $K$ can be mapped
to $\\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding
is a map $f: K\\to \\mathbb R^d$ such that the images of any $r$\r\npairwise disjoint
simplices of $K$ do not have a common point. We show that if $r$ is not a prime
power and $d\\geq 2r+1$, then there is a counterexample to the topological Tverberg
conjecture, i.e., there is an almost $r$-embedding of\r\nthe $(d+1)(r-1)$-simplex
in $\\mathbb R^d$. This improves on previous constructions of counterexamples
(for $d\\geq 3r$) based on a series of papers by M. \\\"Ozaydin, M. Gromov, P.
Blagojevi\\'c, F. Frick, G. Ziegler, and the second and fourth present authors.
The counterexamples are obtained by proving the following algebraic criterion
in codimension 2: If $r\\ge3$ and if $K$ is a finite $2(r-1)$-complex then there
exists an almost $r$-embedding $K\\to \\mathbb R^{2r}$ if and only if there exists
a general position PL map $f:K\\to \\mathbb R^{2r}$ such that the algebraic intersection
number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero.
This result can be restated in terms of cohomological obstructions or equivariant
maps, and extends an analogous codimension 3 criterion by the second and fourth
authors. As another application we classify ornaments $f:S^3 \\sqcup S^3\\sqcup
S^3\\to \\mathbb R^5$ up to ornament\r\nconcordance. It follows from work of M.
Freedman, V. Krushkal and P. Teichner that the analogous criterion for $r=2$ is
false. We prove a lemma on singular higher-dimensional Borromean rings, yielding
an elementary proof of the counterexample."
acknowledgement: We would like to thank A. Klyachko, V. Krushkal, S. Melikhov, M.
Tancer, P. Teichner and anonymous referees for helpful discussions.
article_number: '1511.03501'
article_processing_charge: No
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- first_name: A.
full_name: Skopenkov, A.
last_name: Skopenkov
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity
intersections, III. Codimension 2. arXiv.
apa: Avvakumov, S., Mabillard, I., Skopenkov, A., & Wagner, U. (n.d.). Eliminating
higher-multiplicity intersections, III. Codimension 2. arXiv.
chicago: Avvakumov, Sergey, Isaac Mabillard, A. Skopenkov, and Uli Wagner. “Eliminating
Higher-Multiplicity Intersections, III. Codimension 2.” ArXiv, n.d.
ieee: S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity
intersections, III. Codimension 2,” arXiv. .
ista: Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity
intersections, III. Codimension 2. arXiv, 1511.03501.
mla: Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III.
Codimension 2.” ArXiv, 1511.03501.
short: S. Avvakumov, I. Mabillard, A. Skopenkov, U. Wagner, ArXiv (n.d.).
date_created: 2020-07-30T10:45:19Z
date_published: 2015-11-15T00:00:00Z
date_updated: 2023-09-07T13:12:17Z
day: '15'
department:
- _id: UlWa
external_id:
arxiv:
- '1511.03501'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1511.03501
month: '11'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
related_material:
record:
- id: '9308'
relation: later_version
status: public
- id: '10220'
relation: later_version
status: public
- id: '8156'
relation: dissertation_contains
status: public
status: public
title: Eliminating higher-multiplicity intersections, III. Codimension 2
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5441'
abstract:
- lang: eng
text: We study algorithmic questions for concurrent systems where the transitions
are labeled from a complete, closed semiring, and path properties are algebraic
with semiring operations. The algebraic path properties can model dataflow analysis
problems, the shortest path problem, and many other natural problems that arise
in program analysis. We consider that each component of the concurrent system
is a graph with constant treewidth, a property satisfied by the controlflow graphs
of most programs. We allow for multiple possible queries, which arise naturally
in demand driven dataflow analysis. The study of multiple queries allows us to
consider the tradeoff between the resource usage of the one-time preprocessing
and for each individual query. The traditional approach constructs the product
graph of all components and applies the best-known graph algorithm on the product.
In this approach, even the answer to a single query requires the transitive closure
(i.e., the results of all possible queries), which provides no room for tradeoff
between preprocessing and query time. Our main contributions are algorithms that
significantly improve the worst-case running time of the traditional approach,
and provide various tradeoffs depending on the number of queries. For example,
in a concurrent system of two components, the traditional approach requires hexic
time in the worst case for answering one query as well as computing the transitive
closure, whereas we show that with one-time preprocessing in almost cubic time,
each subsequent query can be answered in at most linear time, and even the transitive
closure can be computed in almost quartic time. Furthermore, we establish conditional
optimality results showing that the worst-case running time of our algorithms
cannot be improved without achieving major breakthroughs in graph algorithms (i.e.,
improving the worst-case bound for the shortest path problem in general graphs).
Preliminary experimental results show that our algorithms perform favorably on
several benchmarks.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Amir
full_name: Goharshady, Amir
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components.
IST Austria; 2015. doi:10.15479/AT:IST-2015-340-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., & Pavlogiannis, A.
(2015). Algorithms for algebraic path properties in concurrent systems of constant
treewidth components. IST Austria. https://doi.org/10.15479/AT:IST-2015-340-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady,
and Andreas Pavlogiannis. Algorithms for Algebraic Path Properties in Concurrent
Systems of Constant Treewidth Components. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-340-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, Algorithms
for algebraic path properties in concurrent systems of constant treewidth components.
IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms
for algebraic path properties in concurrent systems of constant treewidth components,
IST Austria, 24p.
mla: Chatterjee, Krishnendu, et al. Algorithms for Algebraic Path Properties
in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015,
doi:10.15479/AT:IST-2015-340-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components,
IST Austria, 2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-07-11T00:00:00Z
date_updated: 2023-09-19T14:36:19Z
day: '11'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-340-v1-1
file:
- access_level: open_access
checksum: df383dc62c94d7b2ea639aba088a76c6
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:09Z
date_updated: 2020-07-14T12:46:56Z
file_id: '5531'
file_name: IST-2015-340-v1+1_main.pdf
file_size: 861396
relation: main_file
file_date_updated: 2020-07-14T12:46:56Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '24'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '340'
related_material:
record:
- id: '1437'
relation: later_version
status: public
- id: '5442'
relation: earlier_version
status: public
- id: '6009'
relation: later_version
status: public
status: public
title: Algorithms for algebraic path properties in concurrent systems of constant
treewidth components
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...