---
_id: '14206'
abstract:
- lang: eng
text: Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe
(FW) algorithms regained popularity in recent years due to their simplicity, effectiveness
and theoretical guarantees. MP and FW address optimization over the linear span
and the convex hull of a set of atoms, respectively. In this paper, we consider
the intermediate case of optimization over the convex cone, parametrized as the
conic hull of a generic atom set, leading to the first principled definitions
of non-negative MP algorithms for which we give explicit convergence rates and
demonstrate excellent empirical performance. In particular, we derive sublinear
(O(1/t)) convergence on general smooth and convex objectives, and linear convergence
(O(e−t)) on strongly convex objectives, in both cases for general sets of atoms.
Furthermore, we establish a clear correspondence of our algorithms to known algorithms
from the MP and FW literature. Our novel algorithms and analyses target general
atom sets and general objective functions, and hence are directly applicable to
a large variety of learning settings.
article_processing_charge: No
arxiv: 1
author:
- first_name: Francesco
full_name: Locatello, Francesco
id: 26cfd52f-2483-11ee-8040-88983bcc06d4
last_name: Locatello
orcid: 0000-0002-4850-0683
- first_name: Michael
full_name: Tschannen, Michael
last_name: Tschannen
- first_name: Gunnar
full_name: Rätsch, Gunnar
last_name: Rätsch
- first_name: Martin
full_name: Jaggi, Martin
last_name: Jaggi
citation:
ama: 'Locatello F, Tschannen M, Rätsch G, Jaggi M. Greedy algorithms for cone constrained
optimization with convergence guarantees. In: Advances in Neural Information
Processing Systems. ; 2017.'
apa: Locatello, F., Tschannen, M., Rätsch, G., & Jaggi, M. (2017). Greedy algorithms
for cone constrained optimization with convergence guarantees. In Advances
in Neural Information Processing Systems. Long Beach, CA, United States.
chicago: Locatello, Francesco, Michael Tschannen, Gunnar Rätsch, and Martin Jaggi.
“Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees.”
In Advances in Neural Information Processing Systems, 2017.
ieee: F. Locatello, M. Tschannen, G. Rätsch, and M. Jaggi, “Greedy algorithms for
cone constrained optimization with convergence guarantees,” in Advances in
Neural Information Processing Systems, Long Beach, CA, United States, 2017.
ista: 'Locatello F, Tschannen M, Rätsch G, Jaggi M. 2017. Greedy algorithms for
cone constrained optimization with convergence guarantees. Advances in Neural
Information Processing Systems. NeurIPS: Neural Information Processing Systems.'
mla: Locatello, Francesco, et al. “Greedy Algorithms for Cone Constrained Optimization
with Convergence Guarantees.” Advances in Neural Information Processing Systems,
2017.
short: F. Locatello, M. Tschannen, G. Rätsch, M. Jaggi, in:, Advances in Neural
Information Processing Systems, 2017.
conference:
end_date: 2017-12-09
location: Long Beach, CA, United States
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2017-12-04
date_created: 2023-08-22T14:17:38Z
date_published: 2017-05-31T00:00:00Z
date_updated: 2023-09-13T08:32:23Z
day: '31'
department:
- _id: FrLo
extern: '1'
external_id:
arxiv:
- '1705.11041'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.11041
month: '05'
oa: 1
oa_version: Preprint
publication: Advances in Neural Information Processing Systems
publication_identifier:
isbn:
- '9781510860964'
publication_status: published
quality_controlled: '1'
status: public
title: Greedy algorithms for cone constrained optimization with convergence guarantees
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '14286'
abstract:
- lang: eng
text: 'The bacteriophage M13 has found frequent applications in nanobiotechnology
due to its chemically and genetically tunable protein surface and its ability
to self-assemble into colloidal membranes. Additionally, its single-stranded (ss)
genome is commonly used as scaffold for DNA origami. Despite the manifold uses
of M13, upstream production methods for phage and scaffold ssDNA are underexamined
with respect to future industrial usage. Here, the high-cell-density phage production
with Escherichia coli as host organism was studied in respect of medium composition,
infection time, multiplicity of infection, and specific growth rate. The specific
growth rate and the multiplicity of infection were identified as the crucial state
variables that influence phage amplification rate on one hand and the concentration
of produced ssDNA on the other hand. Using a growth rate of 0.15 h−1 and a multiplicity
of infection of 0.05 pfu cfu−1 in the fed-batch production process, the concentration
of pure isolated M13 ssDNA usable for scaffolded DNA origami could be enhanced
by 54% to 590 mg L−1. Thus, our results help enabling M13 production for industrial
uses in nanobiotechnology. Biotechnol. Bioeng. 2017;114: 777–784.'
article_processing_charge: No
article_type: original
author:
- first_name: Benjamin
full_name: Kick, Benjamin
last_name: Kick
- first_name: Samantha
full_name: Hensler, Samantha
last_name: Hensler
- first_name: Florian M
full_name: Praetorius, Florian M
id: dfec9381-4341-11ee-8fd8-faa02bba7d62
last_name: Praetorius
- first_name: Hendrik
full_name: Dietz, Hendrik
last_name: Dietz
- first_name: Dirk
full_name: Weuster-Botz, Dirk
last_name: Weuster-Botz
citation:
ama: Kick B, Hensler S, Praetorius FM, Dietz H, Weuster-Botz D. Specific growth
rate and multiplicity of infection affect high-cell-density fermentation with
bacteriophage M13 for ssDNA production. Biotechnology and Bioengineering.
2017;114(4):777-784. doi:10.1002/bit.26200
apa: Kick, B., Hensler, S., Praetorius, F. M., Dietz, H., & Weuster-Botz, D.
(2017). Specific growth rate and multiplicity of infection affect high-cell-density
fermentation with bacteriophage M13 for ssDNA production. Biotechnology and
Bioengineering. Wiley. https://doi.org/10.1002/bit.26200
chicago: Kick, Benjamin, Samantha Hensler, Florian M Praetorius, Hendrik Dietz,
and Dirk Weuster-Botz. “Specific Growth Rate and Multiplicity of Infection Affect
High-Cell-Density Fermentation with Bacteriophage M13 for SsDNA Production.” Biotechnology
and Bioengineering. Wiley, 2017. https://doi.org/10.1002/bit.26200.
ieee: B. Kick, S. Hensler, F. M. Praetorius, H. Dietz, and D. Weuster-Botz, “Specific
growth rate and multiplicity of infection affect high-cell-density fermentation
with bacteriophage M13 for ssDNA production,” Biotechnology and Bioengineering,
vol. 114, no. 4. Wiley, pp. 777–784, 2017.
ista: Kick B, Hensler S, Praetorius FM, Dietz H, Weuster-Botz D. 2017. Specific
growth rate and multiplicity of infection affect high-cell-density fermentation
with bacteriophage M13 for ssDNA production. Biotechnology and Bioengineering.
114(4), 777–784.
mla: Kick, Benjamin, et al. “Specific Growth Rate and Multiplicity of Infection
Affect High-Cell-Density Fermentation with Bacteriophage M13 for SsDNA Production.”
Biotechnology and Bioengineering, vol. 114, no. 4, Wiley, 2017, pp. 777–84,
doi:10.1002/bit.26200.
short: B. Kick, S. Hensler, F.M. Praetorius, H. Dietz, D. Weuster-Botz, Biotechnology
and Bioengineering 114 (2017) 777–784.
date_created: 2023-09-06T12:08:29Z
date_published: 2017-04-01T00:00:00Z
date_updated: 2023-11-07T12:36:20Z
day: '01'
doi: 10.1002/bit.26200
extern: '1'
external_id:
pmid:
- '27748519'
intvolume: ' 114'
issue: '4'
keyword:
- Applied Microbiology and Biotechnology
- Bioengineering
- Biotechnology
language:
- iso: eng
month: '04'
oa_version: None
page: 777-784
pmid: 1
publication: Biotechnology and Bioengineering
publication_identifier:
issn:
- 0006-3592
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Specific growth rate and multiplicity of infection affect high-cell-density
fermentation with bacteriophage M13 for ssDNA production
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 114
year: '2017'
...
---
_id: '14287'
abstract:
- lang: eng
text: We describe an approach to bottom-up fabrication that allows integration of
the functional diversity of proteins into designed three-dimensional structural
frameworks. A set of custom staple proteins based on transcription activator–like
effector proteins folds a double-stranded DNA template into a user-defined shape.
Each staple protein is designed to recognize and closely link two distinct double-helical
DNA sequences at separate positions on the template. We present design rules for
constructing megadalton-scale DNA-protein hybrid shapes; introduce various structural
motifs, such as custom curvature, corners, and vertices; and describe principles
for creating multilayer DNA-protein objects with enhanced rigidity. We demonstrate
self-assembly of our hybrid nanostructures in one-pot mixtures that include the
genetic information for the designed proteins, the template DNA, RNA polymerase,
ribosomes, and cofactors for transcription and translation.
article_number: eaam5488
article_processing_charge: No
article_type: original
author:
- first_name: Florian M
full_name: Praetorius, Florian M
id: dfec9381-4341-11ee-8fd8-faa02bba7d62
last_name: Praetorius
- first_name: Hendrik
full_name: Dietz, Hendrik
last_name: Dietz
citation:
ama: Praetorius FM, Dietz H. Self-assembly of genetically encoded DNA-protein hybrid
nanoscale shapes. Science. 2017;355(6331). doi:10.1126/science.aam5488
apa: Praetorius, F. M., & Dietz, H. (2017). Self-assembly of genetically encoded
DNA-protein hybrid nanoscale shapes. Science. American Association for
the Advancement of Science. https://doi.org/10.1126/science.aam5488
chicago: Praetorius, Florian M, and Hendrik Dietz. “Self-Assembly of Genetically
Encoded DNA-Protein Hybrid Nanoscale Shapes.” Science. American Association
for the Advancement of Science, 2017. https://doi.org/10.1126/science.aam5488.
ieee: F. M. Praetorius and H. Dietz, “Self-assembly of genetically encoded DNA-protein
hybrid nanoscale shapes,” Science, vol. 355, no. 6331. American Association
for the Advancement of Science, 2017.
ista: Praetorius FM, Dietz H. 2017. Self-assembly of genetically encoded DNA-protein
hybrid nanoscale shapes. Science. 355(6331), eaam5488.
mla: Praetorius, Florian M., and Hendrik Dietz. “Self-Assembly of Genetically Encoded
DNA-Protein Hybrid Nanoscale Shapes.” Science, vol. 355, no. 6331, eaam5488,
American Association for the Advancement of Science, 2017, doi:10.1126/science.aam5488.
short: F.M. Praetorius, H. Dietz, Science 355 (2017).
date_created: 2023-09-06T12:08:55Z
date_published: 2017-03-24T00:00:00Z
date_updated: 2023-11-07T12:33:05Z
day: '24'
doi: 10.1126/science.aam5488
extern: '1'
external_id:
pmid:
- '28336611'
intvolume: ' 355'
issue: '6331'
language:
- iso: eng
month: '03'
oa_version: None
pmid: 1
publication: Science
publication_identifier:
eissn:
- 1095-9203
issn:
- 0036-8075
publication_status: published
publisher: American Association for the Advancement of Science
quality_controlled: '1'
scopus_import: '1'
status: public
title: Self-assembly of genetically encoded DNA-protein hybrid nanoscale shapes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 355
year: '2017'
...
---
_id: '14290'
abstract:
- lang: eng
text: DNA nanotechnology, in particular DNA origami, enables the bottom-up self-assembly
of micrometre-scale, three-dimensional structures with nanometre-precise features1,2,3,4,5,6,7,8,9,10,11,12.
These structures are customizable in that they can be site-specifically functionalized13
or constructed to exhibit machine-like14,15 or logic-gating behaviour16. Their
use has been limited to applications that require only small amounts of material
(of the order of micrograms), owing to the limitations of current production methods.
But many proposed applications, for example as therapeutic agents or in complex
materials3,16,17,18,19,20,21,22, could be realized if more material could be used.
In DNA origami, a nanostructure is assembled from a very long single-stranded
scaffold molecule held in place by many short single-stranded staple oligonucleotides.
Only the bacteriophage-derived scaffold molecules are amenable to scalable and
efficient mass production23; the shorter staple strands are obtained through costly
solid-phase synthesis24 or enzymatic processes25. Here we show that single strands
of DNA of virtually arbitrary length and with virtually arbitrary sequences can
be produced in a scalable and cost-efficient manner by using bacteriophages to
generate single-stranded precursor DNA that contains target strand sequences interleaved
with self-excising ‘cassettes’, with each cassette comprising two Zn2+-dependent
DNA-cleaving DNA enzymes. We produce all of the necessary single strands of DNA
for several DNA origami using shaker-flask cultures, and demonstrate end-to-end
production of macroscopic amounts of a DNA origami nanorod in a litre-scale stirred-tank
bioreactor. Our method is compatible with existing DNA origami design frameworks
and retains the modularity and addressability of DNA origami objects that are
necessary for implementing custom modifications using functional groups. With
all of the production and purification steps amenable to scaling, we expect that
our method will expand the scope of DNA nanotechnology in many areas of science
and technology.
article_processing_charge: No
article_type: original
author:
- first_name: Florian M
full_name: Praetorius, Florian M
id: dfec9381-4341-11ee-8fd8-faa02bba7d62
last_name: Praetorius
- first_name: Benjamin
full_name: Kick, Benjamin
last_name: Kick
- first_name: Karl L.
full_name: Behler, Karl L.
last_name: Behler
- first_name: Maximilian N.
full_name: Honemann, Maximilian N.
last_name: Honemann
- first_name: Dirk
full_name: Weuster-Botz, Dirk
last_name: Weuster-Botz
- first_name: Hendrik
full_name: Dietz, Hendrik
last_name: Dietz
citation:
ama: Praetorius FM, Kick B, Behler KL, Honemann MN, Weuster-Botz D, Dietz H. Biotechnological
mass production of DNA origami. Nature. 2017;552(7683):84-87. doi:10.1038/nature24650
apa: Praetorius, F. M., Kick, B., Behler, K. L., Honemann, M. N., Weuster-Botz,
D., & Dietz, H. (2017). Biotechnological mass production of DNA origami. Nature.
Springer Nature. https://doi.org/10.1038/nature24650
chicago: Praetorius, Florian M, Benjamin Kick, Karl L. Behler, Maximilian N. Honemann,
Dirk Weuster-Botz, and Hendrik Dietz. “Biotechnological Mass Production of DNA
Origami.” Nature. Springer Nature, 2017. https://doi.org/10.1038/nature24650.
ieee: F. M. Praetorius, B. Kick, K. L. Behler, M. N. Honemann, D. Weuster-Botz,
and H. Dietz, “Biotechnological mass production of DNA origami,” Nature,
vol. 552, no. 7683. Springer Nature, pp. 84–87, 2017.
ista: Praetorius FM, Kick B, Behler KL, Honemann MN, Weuster-Botz D, Dietz H. 2017.
Biotechnological mass production of DNA origami. Nature. 552(7683), 84–87.
mla: Praetorius, Florian M., et al. “Biotechnological Mass Production of DNA Origami.”
Nature, vol. 552, no. 7683, Springer Nature, 2017, pp. 84–87, doi:10.1038/nature24650.
short: F.M. Praetorius, B. Kick, K.L. Behler, M.N. Honemann, D. Weuster-Botz, H.
Dietz, Nature 552 (2017) 84–87.
date_created: 2023-09-06T12:14:20Z
date_published: 2017-12-07T00:00:00Z
date_updated: 2023-11-07T12:24:49Z
day: '07'
doi: 10.1038/nature24650
extern: '1'
external_id:
pmid:
- '29219963'
intvolume: ' 552'
issue: '7683'
language:
- iso: eng
month: '12'
oa_version: None
page: 84-87
pmid: 1
publication: Nature
publication_identifier:
eissn:
- 1476-4687
issn:
- 0028-0836
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Biotechnological mass production of DNA origami
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 552
year: '2017'
...
---
_id: '14308'
abstract:
- lang: eng
text: Here we describe an approach to bottom-up fabrication with nanometer-precision
that allows integrating the functional diversity of proteins in designed three-dimensional
structural frameworks. We reimagined the successful DNA origami design principle
using a set of custom staple proteins to fold a double-stranded DNA template into
a user-defined shape. Each staple protein recognizes two distinct double-helical
DNA sequences and can carry additional functionalities. The staple proteins we
present here are based on the transcription activator-like (TAL) effector proteins.
Due to their repetitive structure these proteins offer a unique programmability
that enables us to construct numerous staple proteins targeting any desired DNA
sequence. Our approach is general, meaning that many different objects may be
created using the same set of rules, and it is modular, because components can
be modified or exchanged individually. We present rules for constructing megadalton-scale
DNA-protein hybrid nanostructures; introduce important structural motifs, such
as curvature, corners, and vertices; describe principles for creating multi-layer
DNA-protein objects with enhanced rigidity; and demonstrate the possibility to
combine our DNA-protein hybrid origami with conventional DNA nanotechnology. Since
all components can be encoded genetically, our structures should be amenable to
biotechnological mass-production. Moreover, since the target objects can self-assemble
at room temperature in near-physiological buffer, our hybrid origami may also
provide an attractive method to realize positioning and scaffolding tasks in vivo.
We expect our method to find application both in scaffolding protein functionalities
and in manipulating the spatial arrangement of genomic DNA.
article_number: 25a
article_processing_charge: No
article_type: original
author:
- first_name: Florian M
full_name: Praetorius, Florian M
id: dfec9381-4341-11ee-8fd8-faa02bba7d62
last_name: Praetorius
- first_name: Hendrik
full_name: Dietz, Hendrik
last_name: Dietz
citation:
ama: Praetorius FM, Dietz H. Genetically encoded DNA-protein hybrid origami. Biophysical
Journal. 2017;112(3). doi:10.1016/j.bpj.2016.11.171
apa: Praetorius, F. M., & Dietz, H. (2017). Genetically encoded DNA-protein
hybrid origami. Biophysical Journal. Elsevier. https://doi.org/10.1016/j.bpj.2016.11.171
chicago: Praetorius, Florian M, and Hendrik Dietz. “Genetically Encoded DNA-Protein
Hybrid Origami.” Biophysical Journal. Elsevier, 2017. https://doi.org/10.1016/j.bpj.2016.11.171.
ieee: F. M. Praetorius and H. Dietz, “Genetically encoded DNA-protein hybrid origami,”
Biophysical Journal, vol. 112, no. 3. Elsevier, 2017.
ista: Praetorius FM, Dietz H. 2017. Genetically encoded DNA-protein hybrid origami.
Biophysical Journal. 112(3), 25a.
mla: Praetorius, Florian M., and Hendrik Dietz. “Genetically Encoded DNA-Protein
Hybrid Origami.” Biophysical Journal, vol. 112, no. 3, 25a, Elsevier, 2017,
doi:10.1016/j.bpj.2016.11.171.
short: F.M. Praetorius, H. Dietz, Biophysical Journal 112 (2017).
date_created: 2023-09-06T13:19:10Z
date_published: 2017-02-03T00:00:00Z
date_updated: 2023-11-07T11:28:58Z
day: '03'
doi: 10.1016/j.bpj.2016.11.171
extern: '1'
intvolume: ' 112'
issue: '3'
keyword:
- Biophysics
language:
- iso: eng
month: '02'
oa_version: None
publication: Biophysical Journal
publication_identifier:
issn:
- 0006-3495
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Genetically encoded DNA-protein hybrid origami
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2017'
...
---
_id: '14309'
abstract:
- lang: eng
text: Establishing precise control over the shape and the interactions of the microscopic
building blocks is essential for design of macroscopic soft materials with novel
structural, optical and mechanical properties. Here, we demonstrate robust assembly
of DNA origami filaments into cholesteric liquid crystals, one-dimensional supramolecular
twisted ribbons and two-dimensional colloidal membranes. The exquisite control
afforded by the DNA origami technology establishes a quantitative relationship
between the microscopic filament structure and the macroscopic cholesteric pitch.
Furthermore, it also enables robust assembly of one-dimensional twisted ribbons,
which behave as effective supramolecular polymers whose structure and elastic
properties can be precisely tuned by controlling the geometry of the elemental
building blocks. Our results demonstrate the potential synergy between DNA origami
technology and colloidal science, in which the former allows for rapid and robust
synthesis of complex particles, and the latter can be used to assemble such particles
into bulk materials.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: M
full_name: Siavashpouri, M
last_name: Siavashpouri
- first_name: CH
full_name: Wachauf, CH
last_name: Wachauf
- first_name: MJ
full_name: Zakhary, MJ
last_name: Zakhary
- first_name: Florian M
full_name: Praetorius, Florian M
id: dfec9381-4341-11ee-8fd8-faa02bba7d62
last_name: Praetorius
- first_name: H
full_name: Dietz, H
last_name: Dietz
- first_name: Z
full_name: Dogic, Z
last_name: Dogic
citation:
ama: Siavashpouri M, Wachauf C, Zakhary M, Praetorius FM, Dietz H, Dogic Z. Molecular
engineering of chiral colloidal liquid crystals using DNA origami. Nature Materials.
2017;16(8):849-856. doi:10.1038/nmat4909
apa: Siavashpouri, M., Wachauf, C., Zakhary, M., Praetorius, F. M., Dietz, H., &
Dogic, Z. (2017). Molecular engineering of chiral colloidal liquid crystals using
DNA origami. Nature Materials. Springer Nature. https://doi.org/10.1038/nmat4909
chicago: Siavashpouri, M, CH Wachauf, MJ Zakhary, Florian M Praetorius, H Dietz,
and Z Dogic. “Molecular Engineering of Chiral Colloidal Liquid Crystals Using
DNA Origami.” Nature Materials. Springer Nature, 2017. https://doi.org/10.1038/nmat4909.
ieee: M. Siavashpouri, C. Wachauf, M. Zakhary, F. M. Praetorius, H. Dietz, and Z.
Dogic, “Molecular engineering of chiral colloidal liquid crystals using DNA origami,”
Nature Materials, vol. 16, no. 8. Springer Nature, pp. 849–856, 2017.
ista: Siavashpouri M, Wachauf C, Zakhary M, Praetorius FM, Dietz H, Dogic Z. 2017.
Molecular engineering of chiral colloidal liquid crystals using DNA origami. Nature
Materials. 16(8), 849–856.
mla: Siavashpouri, M., et al. “Molecular Engineering of Chiral Colloidal Liquid
Crystals Using DNA Origami.” Nature Materials, vol. 16, no. 8, Springer
Nature, 2017, pp. 849–56, doi:10.1038/nmat4909.
short: M. Siavashpouri, C. Wachauf, M. Zakhary, F.M. Praetorius, H. Dietz, Z. Dogic,
Nature Materials 16 (2017) 849–856.
date_created: 2023-09-06T13:37:27Z
date_published: 2017-05-22T00:00:00Z
date_updated: 2023-11-07T11:40:00Z
day: '22'
doi: 10.1038/nmat4909
extern: '1'
external_id:
arxiv:
- '1705.08944'
pmid:
- '28530665'
intvolume: ' 16'
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1705.08944'
month: '05'
oa: 1
oa_version: Preprint
page: 849-856
pmid: 1
publication: Nature Materials
publication_identifier:
eissn:
- 1476-4660
issn:
- 1476-1122
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Molecular engineering of chiral colloidal liquid crystals using DNA origami
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2017'
...
---
_id: '14310'
article_processing_charge: No
author:
- first_name: Mahsa
full_name: Siavashpouri, Mahsa
last_name: Siavashpouri
- first_name: Christian
full_name: Wachauf, Christian
last_name: Wachauf
- first_name: Mark
full_name: Zakhary, Mark
last_name: Zakhary
- first_name: Florian M
full_name: Praetorius, Florian M
id: dfec9381-4341-11ee-8fd8-faa02bba7d62
last_name: Praetorius
- first_name: Hendrik
full_name: Dietz, Hendrik
last_name: Dietz
- first_name: Zvonimir
full_name: Dogic, Zvonimir
last_name: Dogic
citation:
ama: 'Siavashpouri M, Wachauf C, Zakhary M, Praetorius FM, Dietz H, Dogic Z. Molecular
engineering of colloidal liquid crystals using DNA origami. In: APS March Meeting
2017. APS; 2017.'
apa: Siavashpouri, M., Wachauf, C., Zakhary, M., Praetorius, F. M., Dietz, H., &
Dogic, Z. (2017). Molecular engineering of colloidal liquid crystals using DNA
origami. In APS March Meeting 2017. APS.
chicago: Siavashpouri, Mahsa, Christian Wachauf, Mark Zakhary, Florian M Praetorius,
Hendrik Dietz, and Zvonimir Dogic. “Molecular Engineering of Colloidal Liquid
Crystals Using DNA Origami.” In APS March Meeting 2017. APS, 2017.
ieee: M. Siavashpouri, C. Wachauf, M. Zakhary, F. M. Praetorius, H. Dietz, and Z.
Dogic, “Molecular engineering of colloidal liquid crystals using DNA origami,”
in APS March Meeting 2017, 2017.
ista: Siavashpouri M, Wachauf C, Zakhary M, Praetorius FM, Dietz H, Dogic Z. 2017.
Molecular engineering of colloidal liquid crystals using DNA origami. APS March
Meeting 2017. .
mla: Siavashpouri, Mahsa, et al. “Molecular Engineering of Colloidal Liquid Crystals
Using DNA Origami.” APS March Meeting 2017, APS, 2017.
short: M. Siavashpouri, C. Wachauf, M. Zakhary, F.M. Praetorius, H. Dietz, Z. Dogic,
in:, APS March Meeting 2017, APS, 2017.
date_created: 2023-09-06T13:40:20Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2023-11-07T11:36:15Z
day: '01'
extern: '1'
language:
- iso: eng
month: '03'
oa_version: None
publication: APS March Meeting 2017
publication_status: published
publisher: APS
quality_controlled: '1'
status: public
title: Molecular engineering of colloidal liquid crystals using DNA origami
type: conference_abstract
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '1433'
abstract:
- lang: eng
text: Phat is an open-source C. ++ library for the computation of persistent homology
by matrix reduction, targeted towards developers of software for topological data
analysis. We aim for a simple generic design that decouples algorithms from data
structures without sacrificing efficiency or user-friendliness. We provide numerous
different reduction strategies as well as data types to store and manipulate the
boundary matrix. We compare the different combinations through extensive experimental
evaluation and identify optimization techniques that work well in practical situations.
We also compare our software with various other publicly available libraries for
persistent homology.
article_processing_charge: No
article_type: original
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
last_name: Bauer
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
- first_name: Jan
full_name: Reininghaus, Jan
last_name: Reininghaus
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
citation:
ama: Bauer U, Kerber M, Reininghaus J, Wagner H. Phat - Persistent homology algorithms
toolbox. Journal of Symbolic Computation. 2017;78:76-90. doi:10.1016/j.jsc.2016.03.008
apa: Bauer, U., Kerber, M., Reininghaus, J., & Wagner, H. (2017). Phat - Persistent
homology algorithms toolbox. Journal of Symbolic Computation. Academic
Press. https://doi.org/10.1016/j.jsc.2016.03.008
chicago: Bauer, Ulrich, Michael Kerber, Jan Reininghaus, and Hubert Wagner. “Phat
- Persistent Homology Algorithms Toolbox.” Journal of Symbolic Computation.
Academic Press, 2017. https://doi.org/10.1016/j.jsc.2016.03.008.
ieee: U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, “Phat - Persistent homology
algorithms toolbox,” Journal of Symbolic Computation, vol. 78. Academic
Press, pp. 76–90, 2017.
ista: Bauer U, Kerber M, Reininghaus J, Wagner H. 2017. Phat - Persistent homology
algorithms toolbox. Journal of Symbolic Computation. 78, 76–90.
mla: Bauer, Ulrich, et al. “Phat - Persistent Homology Algorithms Toolbox.” Journal
of Symbolic Computation, vol. 78, Academic Press, 2017, pp. 76–90, doi:10.1016/j.jsc.2016.03.008.
short: U. Bauer, M. Kerber, J. Reininghaus, H. Wagner, Journal of Symbolic Computation
78 (2017) 76–90.
date_created: 2018-12-11T11:51:59Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-20T09:42:40Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.jsc.2016.03.008
ec_funded: 1
external_id:
isi:
- '000384396000005'
intvolume: ' 78'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.jsc.2016.03.008
month: '01'
oa: 1
oa_version: Published Version
page: 76 - 90
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Journal of Symbolic Computation
publication_identifier:
issn:
- ' 07477171'
publication_status: published
publisher: Academic Press
publist_id: '5765'
quality_controlled: '1'
related_material:
record:
- id: '10894'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Phat - Persistent homology algorithms toolbox
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 78
year: '2017'
...
---
_id: '540'
abstract:
- lang: eng
text: RNA-dependent RNA polymerases (RdRps) play a key role in the life cycle of
RNA viruses and impact their immunobiology. The arenavirus lymphocytic choriomeningitis
virus (LCMV) strain Clone 13 provides a benchmark model for studying chronic infection.
A major genetic determinant for its ability to persist maps to a single amino
acid exchange in the viral L protein, which exhibits RdRp activity, yet its functional
consequences remain elusive. To unravel the L protein interactions with the host
proteome, we engineered infectious L protein-tagged LCMV virions by reverse genetics.
A subsequent mass-spectrometric analysis of L protein pulldowns from infected
human cells revealed a comprehensive network of interacting host proteins. The
obtained LCMV L protein interactome was bioinformatically integrated with known
host protein interactors of RdRps from other RNA viruses, emphasizing interconnected
modules of human proteins. Functional characterization of selected interactors
highlighted proviral (DDX3X) as well as antiviral (NKRF, TRIM21) host factors.
To corroborate these findings, we infected Trim21-/-mice with LCMV and found impaired
virus control in chronic infection. These results provide insights into the complex
interactions of the arenavirus LCMV and other viral RdRps with the host proteome
and contribute to a better molecular understanding of how chronic viruses interact
with their host.
article_number: e1006758
author:
- first_name: Kseniya
full_name: Khamina, Kseniya
last_name: Khamina
- first_name: Alexander
full_name: Lercher, Alexander
last_name: Lercher
- first_name: Michael
full_name: Caldera, Michael
last_name: Caldera
- first_name: Christopher
full_name: Schliehe, Christopher
last_name: Schliehe
- first_name: Bojan
full_name: Vilagos, Bojan
last_name: Vilagos
- first_name: Mehmet
full_name: Sahin, Mehmet
last_name: Sahin
- first_name: Lindsay
full_name: Kosack, Lindsay
last_name: Kosack
- first_name: Anannya
full_name: Bhattacharya, Anannya
last_name: Bhattacharya
- first_name: Peter
full_name: Májek, Peter
last_name: Májek
- first_name: Alexey
full_name: Stukalov, Alexey
last_name: Stukalov
- first_name: Roberto
full_name: Sacco, Roberto
id: 42C9F57E-F248-11E8-B48F-1D18A9856A87
last_name: Sacco
- first_name: Leo
full_name: James, Leo
last_name: James
- first_name: Daniel
full_name: Pinschewer, Daniel
last_name: Pinschewer
- first_name: Keiryn
full_name: Bennett, Keiryn
last_name: Bennett
- first_name: Jörg
full_name: Menche, Jörg
last_name: Menche
- first_name: Andreas
full_name: Bergthaler, Andreas
last_name: Bergthaler
citation:
ama: Khamina K, Lercher A, Caldera M, et al. Characterization of host proteins interacting
with the lymphocytic choriomeningitis virus L protein. PLoS Pathogens.
2017;13(12). doi:10.1371/journal.ppat.1006758
apa: Khamina, K., Lercher, A., Caldera, M., Schliehe, C., Vilagos, B., Sahin, M.,
… Bergthaler, A. (2017). Characterization of host proteins interacting with the
lymphocytic choriomeningitis virus L protein. PLoS Pathogens. Public Library
of Science. https://doi.org/10.1371/journal.ppat.1006758
chicago: Khamina, Kseniya, Alexander Lercher, Michael Caldera, Christopher Schliehe,
Bojan Vilagos, Mehmet Sahin, Lindsay Kosack, et al. “Characterization of Host
Proteins Interacting with the Lymphocytic Choriomeningitis Virus L Protein.” PLoS
Pathogens. Public Library of Science, 2017. https://doi.org/10.1371/journal.ppat.1006758.
ieee: K. Khamina et al., “Characterization of host proteins interacting with
the lymphocytic choriomeningitis virus L protein,” PLoS Pathogens, vol.
13, no. 12. Public Library of Science, 2017.
ista: Khamina K, Lercher A, Caldera M, Schliehe C, Vilagos B, Sahin M, Kosack L,
Bhattacharya A, Májek P, Stukalov A, Sacco R, James L, Pinschewer D, Bennett K,
Menche J, Bergthaler A. 2017. Characterization of host proteins interacting with
the lymphocytic choriomeningitis virus L protein. PLoS Pathogens. 13(12), e1006758.
mla: Khamina, Kseniya, et al. “Characterization of Host Proteins Interacting with
the Lymphocytic Choriomeningitis Virus L Protein.” PLoS Pathogens, vol.
13, no. 12, e1006758, Public Library of Science, 2017, doi:10.1371/journal.ppat.1006758.
short: K. Khamina, A. Lercher, M. Caldera, C. Schliehe, B. Vilagos, M. Sahin, L.
Kosack, A. Bhattacharya, P. Májek, A. Stukalov, R. Sacco, L. James, D. Pinschewer,
K. Bennett, J. Menche, A. Bergthaler, PLoS Pathogens 13 (2017).
date_created: 2018-12-11T11:47:03Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2021-01-12T08:01:48Z
day: '01'
ddc:
- '576'
- '616'
department:
- _id: GaNo
doi: 10.1371/journal.ppat.1006758
file:
- access_level: open_access
checksum: 1aa20f19a1e90664fadce6e7d5284fdc
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:26Z
date_updated: 2020-07-14T12:46:44Z
file_id: '4944'
file_name: IST-2018-931-v1+1_journal.ppat.1006758.pdf
file_size: 4106772
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
intvolume: ' 13'
issue: '12'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '12'
oa: 1
oa_version: Published Version
publication: PLoS Pathogens
publication_identifier:
issn:
- '15537366'
publication_status: published
publisher: Public Library of Science
publist_id: '7276'
pubrep_id: '931'
quality_controlled: '1'
scopus_import: 1
status: public
title: Characterization of host proteins interacting with the lymphocytic choriomeningitis
virus L protein
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: 13
year: '2017'
...
---
_id: '541'
abstract:
- lang: eng
text: 'While we have good understanding of bacterial metabolism at the population
level, we know little about the metabolic behavior of individual cells: do single
cells in clonal populations sometimes specialize on different metabolic pathways?
Such metabolic specialization could be driven by stochastic gene expression and
could provide individual cells with growth benefits of specialization. We measured
the degree of phenotypic specialization in two parallel metabolic pathways, the
assimilation of glucose and arabinose. We grew Escherichia coli in chemostats,
and used isotope-labeled sugars in combination with nanometer-scale secondary
ion mass spectrometry and mathematical modeling to quantify sugar assimilation
at the single-cell level. We found large variation in metabolic activities between
single cells, both in absolute assimilation and in the degree to which individual
cells specialize in the assimilation of different sugars. Analysis of transcriptional
reporters indicated that this variation was at least partially based on cell-to-cell
variation in gene expression. Metabolic differences between cells in clonal populations
could potentially reduce metabolic incompatibilities between different pathways,
and increase the rate at which parallel reactions can be performed.'
article_number: e1007122
author:
- first_name: Nela
full_name: Nikolic, Nela
id: 42D9CABC-F248-11E8-B48F-1D18A9856A87
last_name: Nikolic
orcid: 0000-0001-9068-6090
- first_name: Frank
full_name: Schreiber, Frank
last_name: Schreiber
- first_name: Alma
full_name: Dal Co, Alma
last_name: Dal Co
- first_name: Daniel
full_name: Kiviet, Daniel
last_name: Kiviet
- first_name: Tobias
full_name: Bergmiller, Tobias
id: 2C471CFA-F248-11E8-B48F-1D18A9856A87
last_name: Bergmiller
orcid: 0000-0001-5396-4346
- first_name: Sten
full_name: Littmann, Sten
last_name: Littmann
- first_name: Marcel
full_name: Kuypers, Marcel
last_name: Kuypers
- first_name: Martin
full_name: Ackermann, Martin
last_name: Ackermann
citation:
ama: Nikolic N, Schreiber F, Dal Co A, et al. Cell-to-cell variation and specialization
in sugar metabolism in clonal bacterial populations. PLoS Genetics. 2017;13(12).
doi:10.1371/journal.pgen.1007122
apa: Nikolic, N., Schreiber, F., Dal Co, A., Kiviet, D., Bergmiller, T., Littmann,
S., … Ackermann, M. (2017). Cell-to-cell variation and specialization in sugar
metabolism in clonal bacterial populations. PLoS Genetics. Public Library
of Science. https://doi.org/10.1371/journal.pgen.1007122
chicago: Nikolic, Nela, Frank Schreiber, Alma Dal Co, Daniel Kiviet, Tobias Bergmiller,
Sten Littmann, Marcel Kuypers, and Martin Ackermann. “Cell-to-Cell Variation and
Specialization in Sugar Metabolism in Clonal Bacterial Populations.” PLoS Genetics.
Public Library of Science, 2017. https://doi.org/10.1371/journal.pgen.1007122.
ieee: N. Nikolic et al., “Cell-to-cell variation and specialization in sugar
metabolism in clonal bacterial populations,” PLoS Genetics, vol. 13, no.
12. Public Library of Science, 2017.
ista: Nikolic N, Schreiber F, Dal Co A, Kiviet D, Bergmiller T, Littmann S, Kuypers
M, Ackermann M. 2017. Cell-to-cell variation and specialization in sugar metabolism
in clonal bacterial populations. PLoS Genetics. 13(12), e1007122.
mla: Nikolic, Nela, et al. “Cell-to-Cell Variation and Specialization in Sugar Metabolism
in Clonal Bacterial Populations.” PLoS Genetics, vol. 13, no. 12, e1007122,
Public Library of Science, 2017, doi:10.1371/journal.pgen.1007122.
short: N. Nikolic, F. Schreiber, A. Dal Co, D. Kiviet, T. Bergmiller, S. Littmann,
M. Kuypers, M. Ackermann, PLoS Genetics 13 (2017).
date_created: 2018-12-11T11:47:04Z
date_published: 2017-12-18T00:00:00Z
date_updated: 2023-02-23T14:10:34Z
day: '18'
ddc:
- '576'
- '579'
department:
- _id: CaGu
doi: 10.1371/journal.pgen.1007122
ec_funded: 1
file:
- access_level: open_access
checksum: 22426d9382f21554bad5fa5967afcfd0
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:35Z
date_updated: 2020-07-14T12:46:46Z
file_id: '5088'
file_name: IST-2018-959-v1+1_2017_Nikolic_Cell-to-cell.pdf
file_size: 1308475
relation: main_file
file_date_updated: 2020-07-14T12:46:46Z
has_accepted_license: '1'
intvolume: ' 13'
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: PLoS Genetics
publication_identifier:
issn:
- '15537390'
publication_status: published
publisher: Public Library of Science
publist_id: '7275'
pubrep_id: '959'
quality_controlled: '1'
related_material:
record:
- id: '9844'
relation: research_data
status: public
- id: '9845'
relation: research_data
status: public
- id: '9846'
relation: research_data
status: public
scopus_import: 1
status: public
title: Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial
populations
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: 13
year: '2017'
...
---
_id: '545'
abstract:
- lang: eng
text: Development of vascular tissue is a remarkable example of intercellular communication
and coordinated development involving hormonal signaling and tissue polarity.
Thus far, studies on vascular patterning and regeneration have been conducted
mainly in trees—woody plants—with a well-developed layer of vascular cambium and
secondary tissues. Trees are difficult to use as genetic models, i.e., due to
long generation time, unstable environmental conditions, and lack of available
mutants and transgenic lines. Therefore, the use of the main genetic model plant
Arabidopsis thaliana (L.) Heynh., with a wealth of available marker and transgenic
lines, provides a unique opportunity to address molecular mechanism of vascular
tissue formation and regeneration. With specific treatments, the tiny weed Arabidopsis
can serve as a model to understand the growth of mighty trees and interconnect
a tree physiology with molecular genetics and cell biology of Arabidopsis.
alternative_title:
- Agricultural and Biological Sciences
author:
- first_name: Ewa
full_name: Mazur, Ewa
last_name: Mazur
- first_name: Jirí
full_name: Friml, Jirí
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
citation:
ama: 'Mazur E, Friml J. Vascular tissue development and regeneration in the model
plant arabidopsis. In: Jurić S, ed. Plant Engineering. Plant Engineering.
InTech; 2017:113-140. doi:10.5772/intechopen.69712'
apa: Mazur, E., & Friml, J. (2017). Vascular tissue development and regeneration
in the model plant arabidopsis. In S. Jurić (Ed.), Plant Engineering (pp.
113–140). InTech. https://doi.org/10.5772/intechopen.69712
chicago: Mazur, Ewa, and Jiří Friml. “Vascular Tissue Development and Regeneration
in the Model Plant Arabidopsis.” In Plant Engineering, edited by Snježana
Jurić, 113–40. Plant Engineering. InTech, 2017. https://doi.org/10.5772/intechopen.69712.
ieee: E. Mazur and J. Friml, “Vascular tissue development and regeneration in the
model plant arabidopsis,” in Plant Engineering, S. Jurić, Ed. InTech, 2017,
pp. 113–140.
ista: 'Mazur E, Friml J. 2017.Vascular tissue development and regeneration in the
model plant arabidopsis. In: Plant Engineering. Agricultural and Biological Sciences,
, 113–140.'
mla: Mazur, Ewa, and Jiří Friml. “Vascular Tissue Development and Regeneration in
the Model Plant Arabidopsis.” Plant Engineering, edited by Snježana Jurić,
InTech, 2017, pp. 113–40, doi:10.5772/intechopen.69712.
short: E. Mazur, J. Friml, in:, S. Jurić (Ed.), Plant Engineering, InTech, 2017,
pp. 113–140.
date_created: 2018-12-11T11:47:05Z
date_published: 2017-11-17T00:00:00Z
date_updated: 2024-02-12T12:03:42Z
day: '17'
ddc:
- '581'
department:
- _id: JiFr
doi: 10.5772/intechopen.69712
ec_funded: 1
editor:
- first_name: Snježana
full_name: Jurić, Snježana
last_name: Jurić
file:
- access_level: open_access
checksum: e1f05e5850dfd9f9434d2d373ca61941
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:49Z
date_updated: 2020-07-14T12:46:58Z
file_id: '4969'
file_name: IST-2018-929-v1+1_56106.pdf
file_size: 7443683
relation: main_file
file_date_updated: 2020-07-14T12:46:58Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 113 - 140
project:
- _id: 25716A02-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '282300'
name: Polarity and subcellular dynamics in plants
publication: Plant Engineering
publication_status: published
publisher: InTech
publist_id: '7269'
pubrep_id: '929'
quality_controlled: '1'
related_material:
record:
- id: '1274'
relation: earlier_version
status: public
series_title: Plant Engineering
status: public
title: Vascular tissue development and regeneration in the model plant arabidopsis
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: book_chapter
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '5450'
abstract:
- lang: eng
text: 'In this report the implementation of the institutional data repository IST
DataRep at IST Austria will be covered: Starting with the research phase when
requirements for a repository were established, the procedure of choosing a repository-software
and its customization based on the results of user-testings will be discussed.
Followed by reflections on the marketing strategies in regard of impact, and at
the end sharing some experiences of one year operating IST DataRep.'
author:
- first_name: Barbara
full_name: Barbara Petritsch
id: 406048EC-F248-11E8-B48F-1D18A9856A87
last_name: Petritsch
orcid: 0000-0003-2724-4614
citation:
ama: Petritsch B. Implementing the Institutional Data Repository IST DataRep.
IST Austria; 2017.
apa: Petritsch, B. (2017). Implementing the institutional data repository IST
DataRep. IST Austria.
chicago: Petritsch, Barbara. Implementing the Institutional Data Repository IST
DataRep. IST Austria, 2017.
ieee: B. Petritsch, Implementing the institutional data repository IST DataRep.
IST Austria, 2017.
ista: Petritsch B. 2017. Implementing the institutional data repository IST DataRep,
IST Austria,p.
mla: Petritsch, Barbara. Implementing the Institutional Data Repository IST DataRep.
IST Austria, 2017.
short: B. Petritsch, Implementing the Institutional Data Repository IST DataRep,
IST Austria, 2017.
date_created: 2018-12-12T11:39:24Z
date_published: 2017-06-26T00:00:00Z
date_updated: 2020-07-14T23:05:03Z
day: '26'
department:
- _id: E-Lib
extern: 0
file:
- access_level: open_access
checksum: 6321792dcfa82bf490f17615a9b22355
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:22Z
date_updated: 2020-07-14T12:46:59Z
file_id: '5483'
file_name: IST-2017-724-v1+1_DataRep_Project_Report_2017.pdf
file_size: 3460985
relation: main_file
file_date_updated: 2020-07-14T12:46:59Z
main_file_link:
- open_access: '1'
url: https://repository.ist.ac.at/id/eprint/724.
month: '06'
oa: 1
publication_date: 2017-06-26
publisher: IST Austria
pubrep_id: '724'
status: public
title: Implementing the institutional data repository IST DataRep
type: report
year: '2017'
...
---
_id: '5455'
abstract:
- lang: eng
text: 'A fundamental algorithmic problem at the heart of static analysis is Dyck
reachability. The input is a graphwhere the edges are labeled with different types
of opening and closing parentheses, and the reachabilityinformation is computed
via paths whose parentheses are properly matched. We present new results for Dyckreachability
problems with applications to alias analysis and data-dependence analysis. Our
main contributions,that include improved upper bounds as well as lower bounds
that establish optimality guarantees, are asfollows:First, we consider Dyck reachability
on bidirected graphs, which is the standard way of performing field-sensitive
points-to analysis. Given a bidirected graph withnnodes andmedges, we present:
(i) an algorithmwith worst-case running timeO(m+n·α(n)), whereα(n)is the inverse
Ackermann function, improving thepreviously knownO(n2)time bound; (ii) a matching
lower bound that shows that our algorithm is optimalwrt to worst-case complexity;
and (iii) an optimal average-case upper bound ofO(m)time, improving thepreviously
knownO(m·logn)bound.Second, we consider the problem of context-sensitive data-dependence
analysis, where the task is to obtainanalysis summaries of library code in the
presence of callbacks. Our algorithm preprocesses libraries in almostlinear time,
after which the contribution of the library in the complexity of the client analysis
is only linear,and only wrt the number of call sites.Third, we prove that combinatorial
algorithms for Dyck reachability on general graphs with truly sub-cubic bounds
cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean
MatrixMultiplication, which is a long-standing open problem. Thus we establish
that the existing combinatorialalgorithms for Dyck reachability are (conditionally)
optimal for general graphs. We also show that the samehardness holds for graphs
of constant treewidth.Finally, we provide a prototype implementation of our algorithms
for both alias analysis and data-dependenceanalysis. Our experimental evaluation
demonstrates that the new algorithms significantly outperform allexisting methods
on the two problems, over real-world benchmarks.'
alternative_title:
- IST Austria Technical Report
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: Bhavya
full_name: Choudhary, Bhavya
last_name: Choudhary
- 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, Choudhary B, Pavlogiannis A. Optimal Dyck Reachability for
Data-Dependence and Alias Analysis. IST Austria; 2017. doi:10.15479/AT:IST-2017-870-v1-1
apa: Chatterjee, K., Choudhary, B., & Pavlogiannis, A. (2017). Optimal Dyck
reachability for data-dependence and alias analysis. IST Austria. https://doi.org/10.15479/AT:IST-2017-870-v1-1
chicago: Chatterjee, Krishnendu, Bhavya Choudhary, and Andreas Pavlogiannis. Optimal
Dyck Reachability for Data-Dependence and Alias Analysis. IST Austria, 2017.
https://doi.org/10.15479/AT:IST-2017-870-v1-1.
ieee: K. Chatterjee, B. Choudhary, and A. Pavlogiannis, Optimal Dyck reachability
for data-dependence and alias analysis. IST Austria, 2017.
ista: Chatterjee K, Choudhary B, Pavlogiannis A. 2017. Optimal Dyck reachability
for data-dependence and alias analysis, IST Austria, 37p.
mla: Chatterjee, Krishnendu, et al. Optimal Dyck Reachability for Data-Dependence
and Alias Analysis. IST Austria, 2017, doi:10.15479/AT:IST-2017-870-v1-1.
short: K. Chatterjee, B. Choudhary, A. Pavlogiannis, Optimal Dyck Reachability for
Data-Dependence and Alias Analysis, IST Austria, 2017.
date_created: 2018-12-12T11:39:26Z
date_published: 2017-10-23T00:00:00Z
date_updated: 2023-02-21T15:54:10Z
day: '23'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2017-870-v1-1
file:
- access_level: open_access
checksum: 177a84a46e3ac17e87b31534ad16a4c9
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:02Z
date_updated: 2020-07-14T12:46:59Z
file_id: '5524'
file_name: IST-2017-870-v1+1_main.pdf
file_size: 960491
relation: main_file
file_date_updated: 2020-07-14T12:46:59Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: '37'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '870'
related_material:
record:
- id: '10416'
relation: later_version
status: public
status: public
title: Optimal Dyck reachability for data-dependence and alias analysis
type: technical_report
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2017'
...
---
_id: '5456'
abstract:
- lang: eng
text: "We present a new dynamic partial-order reduction method for stateless model
checking of concurrent programs. A common approach for exploring program behaviors
relies on enumerating the traces of the program, without storing the visited states
(aka stateless exploration). As the number of distinct traces grows exponentially,
dynamic partial-order reduction (DPOR) techniques have been successfully used
to partition the space of traces into equivalence classes (Mazurkiewicz partitioning),
with the goal of exploring only few representative traces from each class.\r\nWe
introduce a new equivalence on traces under sequential consistency semantics,
which we call the observation equivalence. Two traces are observationally equivalent
if every read event observes the same write event in both traces. While the traditional
Mazurkiewicz equivalence is control-centric, our new definition is data-centric.
We show that our observation equivalence is coarser than the Mazurkiewicz equivalence,
and in many cases even exponentially coarser. We devise a DPOR exploration of
the trace space, called data-centric DPOR, based on the observation equivalence.\r\n1.
For acyclic architectures, our algorithm is guaranteed to explore exactly one
representative trace from each observation class, while spending polynomial time
per class. Hence, our algorithm is optimal wrt the observation equivalence, and
in several cases explores exponentially fewer traces than any enumerative method
based on the Mazurkiewicz equivalence.\r\n2. For cyclic architectures, we consider
an equivalence between traces which is finer than the observation equivalence;
but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially
coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence.
\r\nFinally, we perform a basic experimental comparison between the existing Mazurkiewicz-based
DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show
a significant reduction in both running time and the number of explored equivalence
classes."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Marek
full_name: Chalupa, Marek
last_name: Chalupa
- 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: Nishant
full_name: Sinha, Nishant
last_name: Sinha
- first_name: Kapil
full_name: Vaidya, Kapil
last_name: Vaidya
citation:
ama: Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. Data-Centric
Dynamic Partial Order Reduction. IST Austria; 2017. doi:10.15479/AT:IST-2017-872-v1-1
apa: Chalupa, M., Chatterjee, K., Pavlogiannis, A., Sinha, N., & Vaidya, K.
(2017). Data-centric dynamic partial order reduction. IST Austria. https://doi.org/10.15479/AT:IST-2017-872-v1-1
chicago: Chalupa, Marek, Krishnendu Chatterjee, Andreas Pavlogiannis, Nishant Sinha,
and Kapil Vaidya. Data-Centric Dynamic Partial Order Reduction. IST Austria,
2017. https://doi.org/10.15479/AT:IST-2017-872-v1-1.
ieee: M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, and K. Vaidya, Data-centric
dynamic partial order reduction. IST Austria, 2017.
ista: Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. 2017. Data-centric
dynamic partial order reduction, IST Austria, 36p.
mla: Chalupa, Marek, et al. Data-Centric Dynamic Partial Order Reduction.
IST Austria, 2017, doi:10.15479/AT:IST-2017-872-v1-1.
short: M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Data-Centric
Dynamic Partial Order Reduction, IST Austria, 2017.
date_created: 2018-12-12T11:39:26Z
date_published: 2017-10-23T00:00:00Z
date_updated: 2023-02-23T12:26:54Z
day: '23'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2017-872-v1-1
file:
- access_level: open_access
checksum: d2635c4cf013000f0a1b09e80f9e4ab7
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:26Z
date_updated: 2020-07-14T12:46:59Z
file_id: '5487'
file_name: IST-2017-872-v1+1_main.pdf
file_size: 910347
relation: main_file
file_date_updated: 2020-07-14T12:46:59Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: '36'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '872'
related_material:
record:
- id: '10417'
relation: later_version
status: public
- id: '5448'
relation: earlier_version
status: public
status: public
title: Data-centric dynamic partial order reduction
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '548'
abstract:
- lang: eng
text: In this work maximum entropy distributions in the space of steady states of
metabolic networks are considered upon constraining the first and second moments
of the growth rate. Coexistence of fast and slow phenotypes, with bimodal flux
distributions, emerges upon considering control on the average growth (optimization)
and its fluctuations (heterogeneity). This is applied to the carbon catabolic
core of Escherichia coli where it quantifies the metabolic activity of slow growing
phenotypes and it provides a quantitative map with metabolic fluxes, opening the
possibility to detect coexistence from flux data. A preliminary analysis on data
for E. coli cultures in standard conditions shows degeneracy for the inferred
parameters that extend in the coexistence region.
alternative_title:
- Rapid Communications
article_number: '060401'
article_processing_charge: No
author:
- first_name: Daniele
full_name: De Martino, Daniele
id: 3FF5848A-F248-11E8-B48F-1D18A9856A87
last_name: De Martino
orcid: 0000-0002-5214-4706
citation:
ama: De Martino D. Maximum entropy modeling of metabolic networks by constraining
growth-rate moments predicts coexistence of phenotypes. Physical Review E.
2017;96(6). doi:10.1103/PhysRevE.96.060401
apa: De Martino, D. (2017). Maximum entropy modeling of metabolic networks by constraining
growth-rate moments predicts coexistence of phenotypes. Physical Review E.
American Physical Society. https://doi.org/10.1103/PhysRevE.96.060401
chicago: De Martino, Daniele. “Maximum Entropy Modeling of Metabolic Networks by
Constraining Growth-Rate Moments Predicts Coexistence of Phenotypes.” Physical
Review E. American Physical Society, 2017. https://doi.org/10.1103/PhysRevE.96.060401.
ieee: D. De Martino, “Maximum entropy modeling of metabolic networks by constraining
growth-rate moments predicts coexistence of phenotypes,” Physical Review E,
vol. 96, no. 6. American Physical Society, 2017.
ista: De Martino D. 2017. Maximum entropy modeling of metabolic networks by constraining
growth-rate moments predicts coexistence of phenotypes. Physical Review E. 96(6),
060401.
mla: De Martino, Daniele. “Maximum Entropy Modeling of Metabolic Networks by Constraining
Growth-Rate Moments Predicts Coexistence of Phenotypes.” Physical Review E,
vol. 96, no. 6, 060401, American Physical Society, 2017, doi:10.1103/PhysRevE.96.060401.
short: D. De Martino, Physical Review E 96 (2017).
date_created: 2018-12-11T11:47:06Z
date_published: 2017-12-21T00:00:00Z
date_updated: 2023-10-10T13:29:38Z
day: '21'
department:
- _id: GaTk
doi: 10.1103/PhysRevE.96.060401
ec_funded: 1
intvolume: ' 96'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1707.00320
month: '12'
oa: 1
oa_version: Submitted Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Physical Review E
publication_identifier:
issn:
- 2470-0045
publication_status: published
publisher: American Physical Society
publist_id: '7266'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maximum entropy modeling of metabolic networks by constraining growth-rate
moments predicts coexistence of phenotypes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 96
year: '2017'
...
---
_id: '549'
abstract:
- lang: eng
text: Model checking is usually based on a comprehensive traversal of the state
space. Causality-based model checking is a radically different approach that instead
analyzes the cause-effect relationships in a program. We give an overview on a
new class of model checking algorithms that capture the causal relationships in
a special data structure called concurrent traces. Concurrent traces identify
key events in an execution history and link them through their cause-effect relationships.
The model checker builds a tableau of concurrent traces, where the case splits
represent different causal explanations of a hypothetical error. Causality-based
model checking has been implemented in the ARCTOR tool, and applied to previously
intractable multi-threaded benchmarks.
alternative_title:
- EPTCS
article_processing_charge: No
author:
- first_name: Bernd
full_name: Finkbeiner, Bernd
last_name: Finkbeiner
- first_name: Andrey
full_name: Kupriyanov, Andrey
id: 2C311BF8-F248-11E8-B48F-1D18A9856A87
last_name: Kupriyanov
citation:
ama: 'Finkbeiner B, Kupriyanov A. Causality-based model checking. In: Electronic
Proceedings in Theoretical Computer Science. Vol 259. Open Publishing Association;
2017:31-38. doi:10.4204/EPTCS.259.3'
apa: 'Finkbeiner, B., & Kupriyanov, A. (2017). Causality-based model checking.
In Electronic Proceedings in Theoretical Computer Science (Vol. 259, pp.
31–38). Uppsala, Sweden: Open Publishing Association. https://doi.org/10.4204/EPTCS.259.3'
chicago: Finkbeiner, Bernd, and Andrey Kupriyanov. “Causality-Based Model Checking.”
In Electronic Proceedings in Theoretical Computer Science, 259:31–38. Open
Publishing Association, 2017. https://doi.org/10.4204/EPTCS.259.3.
ieee: B. Finkbeiner and A. Kupriyanov, “Causality-based model checking,” in Electronic
Proceedings in Theoretical Computer Science, Uppsala, Sweden, 2017, vol. 259,
pp. 31–38.
ista: 'Finkbeiner B, Kupriyanov A. 2017. Causality-based model checking. Electronic
Proceedings in Theoretical Computer Science. CREST: Causal Reasoning for Embedded
and Safety-Critical Systems Technologies, EPTCS, vol. 259, 31–38.'
mla: Finkbeiner, Bernd, and Andrey Kupriyanov. “Causality-Based Model Checking.”
Electronic Proceedings in Theoretical Computer Science, vol. 259, Open
Publishing Association, 2017, pp. 31–38, doi:10.4204/EPTCS.259.3.
short: B. Finkbeiner, A. Kupriyanov, in:, Electronic Proceedings in Theoretical
Computer Science, Open Publishing Association, 2017, pp. 31–38.
conference:
end_date: 2017-04-29
location: Uppsala, Sweden
name: 'CREST: Causal Reasoning for Embedded and Safety-Critical Systems Technologies'
start_date: 2017-04-29
date_created: 2018-12-11T11:47:07Z
date_published: 2017-10-10T00:00:00Z
date_updated: 2023-10-17T12:02:46Z
day: '10'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.4204/EPTCS.259.3
file:
- access_level: open_access
checksum: 6274f6c0da3376a7b079180d81568518
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:21Z
date_updated: 2020-07-14T12:47:00Z
file_id: '4939'
file_name: IST-2018-925-v1+1_1710.03391v1.pdf
file_size: 209294
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
intvolume: ' 259'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1710.03391v1
month: '10'
oa: 1
oa_version: Submitted Version
page: 31 - 38
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: Electronic Proceedings in Theoretical Computer Science
publication_identifier:
issn:
- 2075-2180
publication_status: published
publisher: Open Publishing Association
publist_id: '7264'
pubrep_id: '925'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Causality-based model checking
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 259
year: '2017'
...
---
_id: '550'
abstract:
- lang: eng
text: For large random matrices X with independent, centered entries but not necessarily
identical variances, the eigenvalue density of XX* is well-approximated by a deterministic
measure on ℝ. We show that the density of this measure has only square and cubic-root
singularities away from zero. We also extend the bulk local law in [5] to the
vicinity of these singularities.
article_number: '63'
author:
- first_name: Johannes
full_name: Alt, Johannes
id: 36D3D8B6-F248-11E8-B48F-1D18A9856A87
last_name: Alt
citation:
ama: Alt J. Singularities of the density of states of random Gram matrices. Electronic
Communications in Probability. 2017;22. doi:10.1214/17-ECP97
apa: Alt, J. (2017). Singularities of the density of states of random Gram matrices.
Electronic Communications in Probability. Institute of Mathematical Statistics.
https://doi.org/10.1214/17-ECP97
chicago: Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.”
Electronic Communications in Probability. Institute of Mathematical Statistics,
2017. https://doi.org/10.1214/17-ECP97.
ieee: J. Alt, “Singularities of the density of states of random Gram matrices,”
Electronic Communications in Probability, vol. 22. Institute of Mathematical
Statistics, 2017.
ista: Alt J. 2017. Singularities of the density of states of random Gram matrices.
Electronic Communications in Probability. 22, 63.
mla: Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.”
Electronic Communications in Probability, vol. 22, 63, Institute of Mathematical
Statistics, 2017, doi:10.1214/17-ECP97.
short: J. Alt, Electronic Communications in Probability 22 (2017).
date_created: 2018-12-11T11:47:07Z
date_published: 2017-11-21T00:00:00Z
date_updated: 2023-09-07T12:38:08Z
day: '21'
ddc:
- '539'
department:
- _id: LaEr
doi: 10.1214/17-ECP97
ec_funded: 1
file:
- access_level: open_access
checksum: 0ec05303a0de190de145654237984c79
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:04Z
date_updated: 2020-07-14T12:47:00Z
file_id: '4663'
file_name: IST-2018-926-v1+1_euclid.ecp.1511233247.pdf
file_size: 470876
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
intvolume: ' 22'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 258DCDE6-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '338804'
name: Random matrices, universality and disordered quantum systems
publication: Electronic Communications in Probability
publication_identifier:
issn:
- 1083589X
publication_status: published
publisher: Institute of Mathematical Statistics
publist_id: '7265'
pubrep_id: '926'
quality_controlled: '1'
related_material:
record:
- id: '149'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Singularities of the density of states of random Gram matrices
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2017'
...
---
_id: '551'
abstract:
- lang: eng
text: 'Evolutionary graph theory studies the evolutionary dynamics in a population
structure given as a connected graph. Each node of the graph represents an individual
of the population, and edges determine how offspring are placed. We consider the
classical birth-death Moran process where there are two types of individuals,
namely, the residents with fitness 1 and mutants with fitness r. The fitness indicates
the reproductive strength. The evolutionary dynamics happens as follows: in the
initial step, in a population of all resident individuals a mutant is introduced,
and then at each step, an individual is chosen proportional to the fitness of
its type to reproduce, and the offspring replaces a neighbor uniformly at random.
The process stops when all individuals are either residents or mutants. The probability
that all individuals in the end are mutants is called the fixation probability,
which is a key factor in the rate of evolution. We consider the problem of approximating
the fixation probability. The class of algorithms that is extremely relevant for
approximation of the fixation probabilities is the Monte-Carlo simulation of the
process. Previous results present a polynomial-time Monte-Carlo algorithm for
undirected graphs when r is given in unary. First, we present a simple modification:
instead of simulating each step, we discard ineffective steps, where no node changes
type (i.e., either residents replace residents, or mutants replace mutants). Using
the above simple modification and our result that the number of effective steps
is concentrated around the expected number of effective steps, we present faster
polynomial-time Monte-Carlo algorithms for undirected graphs. Our algorithms are
always at least a factor O(n2/ log n) faster as compared to the previous algorithms,
where n is the number of nodes, and is polynomial even if r is given in binary.
We also present lower bounds showing that the upper bound on the expected number
of effective steps we present is asymptotically tight for undirected graphs. '
alternative_title:
- LIPIcs
article_number: '61'
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: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: 'Chatterjee K, Ibsen-Jensen R, Nowak M. Faster Monte Carlo algorithms for fixation
probability of the Moran process on undirected graphs. In: Leibniz International
Proceedings in Informatics. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.61'
apa: 'Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2017). Faster Monte Carlo
algorithms for fixation probability of the Moran process on undirected graphs.
In Leibniz International Proceedings in Informatics (Vol. 83). Aalborg,
Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2017.61'
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. “Faster
Monte Carlo Algorithms for Fixation Probability of the Moran Process on Undirected
Graphs.” In Leibniz International Proceedings in Informatics, Vol. 83.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.61.
ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, “Faster Monte Carlo algorithms
for fixation probability of the Moran process on undirected graphs,” in Leibniz
International Proceedings in Informatics, Aalborg, Denmark, 2017, vol. 83.
ista: 'Chatterjee K, Ibsen-Jensen R, Nowak M. 2017. Faster Monte Carlo algorithms
for fixation probability of the Moran process on undirected graphs. Leibniz International
Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science
(SG), LIPIcs, vol. 83, 61.'
mla: Chatterjee, Krishnendu, et al. “Faster Monte Carlo Algorithms for Fixation
Probability of the Moran Process on Undirected Graphs.” Leibniz International
Proceedings in Informatics, vol. 83, 61, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.61.
short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, in:, Leibniz International Proceedings
in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-08-25
location: Aalborg, Denmark
name: 'MFCS: Mathematical Foundations of Computer Science (SG)'
start_date: 2017-08-21
date_created: 2018-12-11T11:47:08Z
date_published: 2017-11-01T00:00:00Z
date_updated: 2021-01-12T08:02:34Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2017.61
file:
- access_level: open_access
checksum: 2eed5224c0e4e259484a1d71acb8ba6a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:04Z
date_updated: 2020-07-14T12:47:00Z
file_id: '5322'
file_name: IST-2018-924-v1+1_LIPIcs-MFCS-2017-61.pdf
file_size: 535077
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
intvolume: ' 83'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication: Leibniz International Proceedings in Informatics
publication_identifier:
isbn:
- 978-395977046-0
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7263'
pubrep_id: '924'
quality_controlled: '1'
scopus_import: 1
status: public
title: Faster Monte Carlo algorithms for fixation probability of the Moran process
on undirected 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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 83
year: '2017'
...
---
_id: '552'
abstract:
- lang: eng
text: 'Graph games provide the foundation for modeling and synthesis of reactive
processes. Such games are played over graphs where the vertices are controlled
by two adversarial players. We consider graph games where the objective of the
first player is the conjunction of a qualitative objective (specified as a parity
condition) and a quantitative objective (specified as a meanpayoff condition).
There are two variants of the problem, namely, the threshold problem where the
quantitative goal is to ensure that the mean-payoff value is above a threshold,
and the value problem where the quantitative goal is to ensure the optimal mean-payoff
value; in both cases ensuring the qualitative parity objective. The previous best-known
algorithms for game graphs with n vertices, m edges, parity objectives with d
priorities, and maximal absolute reward value W for mean-payoff objectives, are
as follows: O(nd+1 . m . w) for the threshold problem, and O(nd+2 · m · W) for
the value problem. Our main contributions are faster algorithms, and the running
times of our algorithms are as follows: O(nd-1 · m ·W) for the threshold problem,
and O(nd · m · W · log(n · W)) for the value problem. For mean-payoff parity objectives
with two priorities, our algorithms match the best-known bounds of the algorithms
for mean-payoff games (without conjunction with parity objectives). Our results
are relevant in synthesis of reactive systems with both functional requirement
(given as a qualitative objective) and performance requirement (given as a quantitative
objective).'
alternative_title:
- LIPIcs
article_number: '39'
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: Alexander
full_name: Svozil, Alexander
last_name: Svozil
citation:
ama: 'Chatterjee K, Henzinger MH, Svozil A. Faster algorithms for mean-payoff parity
games. In: Leibniz International Proceedings in Informatics. Vol 83. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.39'
apa: 'Chatterjee, K., Henzinger, M. H., & Svozil, A. (2017). Faster algorithms
for mean-payoff parity games. In Leibniz International Proceedings in Informatics
(Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.MFCS.2017.39'
chicago: Chatterjee, Krishnendu, Monika H Henzinger, and Alexander Svozil. “Faster
Algorithms for Mean-Payoff Parity Games.” In Leibniz International Proceedings
in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.39.
ieee: K. Chatterjee, M. H. Henzinger, and A. Svozil, “Faster algorithms for mean-payoff
parity games,” in Leibniz International Proceedings in Informatics, Aalborg,
Denmark, 2017, vol. 83.
ista: 'Chatterjee K, Henzinger MH, Svozil A. 2017. Faster algorithms for mean-payoff
parity games. Leibniz International Proceedings in Informatics. MFCS: Mathematical
Foundations of Computer Science (SG), LIPIcs, vol. 83, 39.'
mla: Chatterjee, Krishnendu, et al. “Faster Algorithms for Mean-Payoff Parity Games.”
Leibniz International Proceedings in Informatics, vol. 83, 39, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.39.
short: K. Chatterjee, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings
in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-08-25
location: Aalborg, Denmark
name: 'MFCS: Mathematical Foundations of Computer Science (SG)'
start_date: 2017-08-21
date_created: 2018-12-11T11:47:08Z
date_published: 2017-11-01T00:00:00Z
date_updated: 2023-02-14T10:06:46Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2017.39
ec_funded: 1
file:
- access_level: open_access
checksum: c67f4866ddbfd555afef1f63ae9a8fc7
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:57Z
date_updated: 2020-07-14T12:47:00Z
file_id: '5248'
file_name: IST-2018-923-v1+1_LIPIcs-MFCS-2017-39.pdf
file_size: 610339
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
intvolume: ' 83'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Leibniz International Proceedings in Informatics
publication_identifier:
isbn:
- 978-395977046-0
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7262'
pubrep_id: '923'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster algorithms for mean-payoff parity games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 83
year: '2017'
...
---
_id: '553'
abstract:
- lang: eng
text: 'We consider two player, zero-sum, finite-state concurrent reachability games,
played for an infinite number of rounds, where in every round, each player simultaneously
and independently of the other players chooses an action, whereafter the successor
state is determined by a probability distribution given by the current state and
the chosen actions. Player 1 wins iff a designated goal state is eventually visited.
We are interested in the complexity of stationary strategies measured by their
patience, which is defined as the inverse of the smallest non-zero probability
employed. Our main results are as follows: We show that: (i) the optimal bound
on the patience of optimal and -optimal strategies, for both players is doubly
exponential; and (ii) even in games with a single non-absorbing state exponential
(in the number of actions) patience is necessary. '
alternative_title:
- LIPIcs
article_number: '55'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Kristofer
full_name: Hansen, Kristofer
last_name: Hansen
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
citation:
ama: 'Chatterjee K, Hansen K, Ibsen-Jensen R. Strategy complexity of concurrent
safety games. In: Leibniz International Proceedings in Informatics. Vol
83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.55'
apa: 'Chatterjee, K., Hansen, K., & Ibsen-Jensen, R. (2017). Strategy complexity
of concurrent safety games. In Leibniz International Proceedings in Informatics
(Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.MFCS.2017.55'
chicago: Chatterjee, Krishnendu, Kristofer Hansen, and Rasmus Ibsen-Jensen. “Strategy
Complexity of Concurrent Safety Games.” In Leibniz International Proceedings
in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.55.
ieee: K. Chatterjee, K. Hansen, and R. Ibsen-Jensen, “Strategy complexity of concurrent
safety games,” in Leibniz International Proceedings in Informatics, Aalborg,
Denmark, 2017, vol. 83.
ista: 'Chatterjee K, Hansen K, Ibsen-Jensen R. 2017. Strategy complexity of concurrent
safety games. Leibniz International Proceedings in Informatics. MFCS: Mathematical
Foundations of Computer Science (SG), LIPIcs, vol. 83, 55.'
mla: Chatterjee, Krishnendu, et al. “Strategy Complexity of Concurrent Safety Games.”
Leibniz International Proceedings in Informatics, vol. 83, 55, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.55.
short: K. Chatterjee, K. Hansen, R. Ibsen-Jensen, in:, Leibniz International Proceedings
in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-08-25
location: Aalborg, Denmark
name: 'MFCS: Mathematical Foundations of Computer Science (SG)'
start_date: 2017-08-21
date_created: 2018-12-11T11:47:08Z
date_published: 2017-11-01T00:00:00Z
date_updated: 2021-01-12T08:02:35Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2017.55
file:
- access_level: open_access
checksum: 7101facb56ade363205c695d72dbd173
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:29Z
date_updated: 2020-07-14T12:47:00Z
file_id: '4753'
file_name: IST-2018-922-v1+1_LIPIcs-MFCS-2017-55.pdf
file_size: 549967
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
intvolume: ' 83'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1506.02434
month: '11'
oa: 1
oa_version: Published Version
publication: Leibniz International Proceedings in Informatics
publication_identifier:
isbn:
- 978-395977046-0
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7261'
pubrep_id: '922'
quality_controlled: '1'
scopus_import: 1
status: public
title: Strategy complexity of concurrent safety games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 83
year: '2017'
...