---
_id: '1338'
abstract:
- lang: eng
text: We present a computer-aided programming approach to concurrency. The approach
allows programmers to program assuming a friendly, non-preemptive scheduler, and
our synthesis procedure inserts synchronization to ensure that the final program
works even with a preemptive scheduler. The correctness specification is implicit,
inferred from the non-preemptive behavior. Let us consider sequences of calls
that the program makes to an external interface. The specification requires that
any such sequence produced under a preemptive scheduler should be included in
the set of sequences produced under a non-preemptive scheduler. We guarantee that
our synthesis does not introduce deadlocks and that the synchronization inserted
is optimal w.r.t. a given objective function. The solution is based on a finitary
abstraction, an algorithm for bounded language inclusion modulo an independence
relation, and generation of a set of global constraints over synchronization placements.
Each model of the global constraints set corresponds to a correctness-ensuring
synchronization placement. The placement that is optimal w.r.t. the given objective
function is chosen as the synchronization solution. We apply the approach to device-driver
programming, where the driver threads call the software interface of the device
and the API provided by the operating system. Our experiments demonstrate that
our synthesis method is precise and efficient. The implicit specification helped
us find one concurrency bug previously missed when model-checking using an explicit,
user-provided specification. We implemented objective functions for coarse-grained
and fine-grained locking and observed that different synchronization placements
are produced for our experiments, favoring a minimal number of synchronization
operations or maximum concurrency, respectively.
article_processing_charge: No
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- first_name: Edmund
full_name: Clarke, Edmund
last_name: Clarke
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
- first_name: Leonid
full_name: Ryzhyk, Leonid
last_name: Ryzhyk
- first_name: Roopsha
full_name: Samanta, Roopsha
id: 3D2AAC08-F248-11E8-B48F-1D18A9856A87
last_name: Samanta
- first_name: Thorsten
full_name: Tarrach, Thorsten
id: 3D6E8F2C-F248-11E8-B48F-1D18A9856A87
last_name: Tarrach
orcid: 0000-0003-4409-8487
citation:
ama: Cerny P, Clarke E, Henzinger TA, et al. From non-preemptive to preemptive scheduling
using synchronization synthesis. Formal Methods in System Design. 2017;50(2-3):97-139.
doi:10.1007/s10703-016-0256-5
apa: Cerny, P., Clarke, E., Henzinger, T. A., Radhakrishna, A., Ryzhyk, L., Samanta,
R., & Tarrach, T. (2017). From non-preemptive to preemptive scheduling using
synchronization synthesis. Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-016-0256-5
chicago: Cerny, Pavol, Edmund Clarke, Thomas A Henzinger, Arjun Radhakrishna, Leonid
Ryzhyk, Roopsha Samanta, and Thorsten Tarrach. “From Non-Preemptive to Preemptive
Scheduling Using Synchronization Synthesis.” Formal Methods in System Design.
Springer, 2017. https://doi.org/10.1007/s10703-016-0256-5.
ieee: P. Cerny et al., “From non-preemptive to preemptive scheduling using
synchronization synthesis,” Formal Methods in System Design, vol. 50, no.
2–3. Springer, pp. 97–139, 2017.
ista: Cerny P, Clarke E, Henzinger TA, Radhakrishna A, Ryzhyk L, Samanta R, Tarrach
T. 2017. From non-preemptive to preemptive scheduling using synchronization synthesis.
Formal Methods in System Design. 50(2–3), 97–139.
mla: Cerny, Pavol, et al. “From Non-Preemptive to Preemptive Scheduling Using Synchronization
Synthesis.” Formal Methods in System Design, vol. 50, no. 2–3, Springer,
2017, pp. 97–139, doi:10.1007/s10703-016-0256-5.
short: P. Cerny, E. Clarke, T.A. Henzinger, A. Radhakrishna, L. Ryzhyk, R. Samanta,
T. Tarrach, Formal Methods in System Design 50 (2017) 97–139.
date_created: 2018-12-11T11:51:27Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T11:13:51Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/s10703-016-0256-5
ec_funded: 1
external_id:
isi:
- '000399888900001'
file:
- access_level: open_access
checksum: 1163dfd997e8212c789525d4178b1653
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:05Z
date_updated: 2020-07-14T12:44:44Z
file_id: '4985'
file_name: IST-2016-656-v1+1_s10703-016-0256-5.pdf
file_size: 1416170
relation: main_file
file_date_updated: 2020-07-14T12:44:44Z
has_accepted_license: '1'
intvolume: ' 50'
isi: 1
issue: 2-3
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 97 - 139
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Formal Methods in System Design
publication_status: published
publisher: Springer
publist_id: '5929'
pubrep_id: '656'
quality_controlled: '1'
related_material:
record:
- id: '1729'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: From non-preemptive to preemptive scheduling using synchronization synthesis
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 50
year: '2017'
...
---
_id: '1351'
abstract:
- lang: eng
text: The behaviour of gene regulatory networks (GRNs) is typically analysed using
simulation-based statistical testing-like methods. In this paper, we demonstrate
that we can replace this approach by a formal verification-like method that gives
higher assurance and scalability. We focus on Wagner’s weighted GRN model with
varying weights, which is used in evolutionary biology. In the model, weight parameters
represent the gene interaction strength that may change due to genetic mutations.
For a property of interest, we synthesise the constraints over the parameter space
that represent the set of GRNs satisfying the property. We experimentally show
that our parameter synthesis procedure computes the mutational robustness of GRNs—an
important problem of interest in evolutionary biology—more efficiently than the
classical simulation method. We specify the property in linear temporal logic.
We employ symbolic bounded model checking and SMT solving to compute the space
of GRNs that satisfy the property, which amounts to synthesizing a set of linear
constraints on the weights.
article_processing_charge: No
author:
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
citation:
ama: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. Model checking
the evolution of gene regulatory networks. Acta Informatica. 2017;54(8):765-787.
doi:10.1007/s00236-016-0278-x
apa: Giacobbe, M., Guet, C. C., Gupta, A., Henzinger, T. A., Paixao, T., & Petrov,
T. (2017). Model checking the evolution of gene regulatory networks. Acta Informatica.
Springer. https://doi.org/10.1007/s00236-016-0278-x
chicago: Giacobbe, Mirco, Calin C Guet, Ashutosh Gupta, Thomas A Henzinger, Tiago
Paixao, and Tatjana Petrov. “Model Checking the Evolution of Gene Regulatory Networks.”
Acta Informatica. Springer, 2017. https://doi.org/10.1007/s00236-016-0278-x.
ieee: M. Giacobbe, C. C. Guet, A. Gupta, T. A. Henzinger, T. Paixao, and T. Petrov,
“Model checking the evolution of gene regulatory networks,” Acta Informatica,
vol. 54, no. 8. Springer, pp. 765–787, 2017.
ista: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. 2017. Model
checking the evolution of gene regulatory networks. Acta Informatica. 54(8), 765–787.
mla: Giacobbe, Mirco, et al. “Model Checking the Evolution of Gene Regulatory Networks.”
Acta Informatica, vol. 54, no. 8, Springer, 2017, pp. 765–87, doi:10.1007/s00236-016-0278-x.
short: M. Giacobbe, C.C. Guet, A. Gupta, T.A. Henzinger, T. Paixao, T. Petrov, Acta
Informatica 54 (2017) 765–787.
date_created: 2018-12-11T11:51:32Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2025-05-28T11:57:04Z
day: '01'
ddc:
- '006'
- '576'
department:
- _id: ToHe
- _id: CaGu
- _id: NiBa
doi: 10.1007/s00236-016-0278-x
ec_funded: 1
external_id:
isi:
- '000414343200003'
file:
- access_level: open_access
checksum: 4e661d9135d7f8c342e8e258dee76f3e
content_type: application/pdf
creator: dernst
date_created: 2019-01-17T15:57:29Z
date_updated: 2020-07-14T12:44:46Z
file_id: '5841'
file_name: 2017_ActaInformatica_Giacobbe.pdf
file_size: 755241
relation: main_file
file_date_updated: 2020-07-14T12:44:46Z
has_accepted_license: '1'
intvolume: ' 54'
isi: 1
issue: '8'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 765 - 787
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Acta Informatica
publication_identifier:
issn:
- '00015903'
publication_status: published
publisher: Springer
publist_id: '5898'
pubrep_id: '649'
quality_controlled: '1'
related_material:
record:
- id: '1835'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Model checking the evolution of gene regulatory networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 54
year: '2017'
...
---
_id: '1367'
abstract:
- lang: eng
text: One of the major challenges in physically based modelling is making simulations
efficient. Adaptive models provide an essential solution to these efficiency goals.
These models are able to self-adapt in space and time, attempting to provide the
best possible compromise between accuracy and speed. This survey reviews the adaptive
solutions proposed so far in computer graphics. Models are classified according
to the strategy they use for adaptation, from time-stepping and freezing techniques
to geometric adaptivity in the form of structured grids, meshes and particles.
Applications range from fluids, through deformable bodies, to articulated solids.
acknowledgement: This work was partly supported by the starting grants ADAPT and BigSplash,
as well as the advanced grant EXPRESSIVE from the European Research Council (ERC-2012-StG_20111012,
ERC-2014-StG_638176 and ERC-2011-ADG_20110209).
article_processing_charge: No
author:
- first_name: Pierre
full_name: Manteaux, Pierre
last_name: Manteaux
- first_name: Christopher J
full_name: Wojtan, Christopher J
id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87
last_name: Wojtan
orcid: 0000-0001-6646-5546
- first_name: Rahul
full_name: Narain, Rahul
last_name: Narain
- first_name: Stéphane
full_name: Redon, Stéphane
last_name: Redon
- first_name: François
full_name: Faure, François
last_name: Faure
- first_name: Marie
full_name: Cani, Marie
last_name: Cani
citation:
ama: Manteaux P, Wojtan C, Narain R, Redon S, Faure F, Cani M. Adaptive physically
based models in computer graphics. Computer Graphics Forum. 2017;36(6):312-337.
doi:10.1111/cgf.12941
apa: Manteaux, P., Wojtan, C., Narain, R., Redon, S., Faure, F., & Cani, M.
(2017). Adaptive physically based models in computer graphics. Computer Graphics
Forum. Wiley-Blackwell. https://doi.org/10.1111/cgf.12941
chicago: Manteaux, Pierre, Chris Wojtan, Rahul Narain, Stéphane Redon, François
Faure, and Marie Cani. “Adaptive Physically Based Models in Computer Graphics.”
Computer Graphics Forum. Wiley-Blackwell, 2017. https://doi.org/10.1111/cgf.12941.
ieee: P. Manteaux, C. Wojtan, R. Narain, S. Redon, F. Faure, and M. Cani, “Adaptive
physically based models in computer graphics,” Computer Graphics Forum,
vol. 36, no. 6. Wiley-Blackwell, pp. 312–337, 2017.
ista: Manteaux P, Wojtan C, Narain R, Redon S, Faure F, Cani M. 2017. Adaptive physically
based models in computer graphics. Computer Graphics Forum. 36(6), 312–337.
mla: Manteaux, Pierre, et al. “Adaptive Physically Based Models in Computer Graphics.”
Computer Graphics Forum, vol. 36, no. 6, Wiley-Blackwell, 2017, pp. 312–37,
doi:10.1111/cgf.12941.
short: P. Manteaux, C. Wojtan, R. Narain, S. Redon, F. Faure, M. Cani, Computer
Graphics Forum 36 (2017) 312–337.
date_created: 2018-12-11T11:51:37Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-09-20T11:05:36Z
day: '01'
ddc:
- '000'
department:
- _id: ChWo
doi: 10.1111/cgf.12941
external_id:
isi:
- '000408634200019'
file:
- access_level: open_access
checksum: 7676e9a9ead6d58c3000988c97deb2ef
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:21Z
date_updated: 2020-07-14T12:44:47Z
file_id: '5208'
file_name: IST-2016-634-v1+1_starAdaptivity-cgf.pdf
file_size: 1434439
relation: main_file
file_date_updated: 2020-07-14T12:44:47Z
has_accepted_license: '1'
intvolume: ' 36'
isi: 1
issue: '6'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 312 - 337
publication: Computer Graphics Forum
publication_identifier:
issn:
- '01677055'
publication_status: published
publisher: Wiley-Blackwell
publist_id: '5873'
pubrep_id: '634'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Adaptive physically based models in computer graphics
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 36
year: '2017'
...
---
_id: '1407'
abstract:
- lang: eng
text: We consider the problem of computing the set of initial states of a dynamical
system such that there exists a control strategy to ensure that the trajectories
satisfy a temporal logic specification with probability 1 (almost-surely). We
focus on discrete-time, stochastic linear dynamics and specifications given as
formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over
linear predicates in the states of the system. We propose a solution based on
iterative abstraction-refinement, and turn-based 2-player probabilistic games.
While the theoretical guarantee of our algorithm after any finite number of iterations
is only a partial solution, we show that if our algorithm terminates, then the
result is the set of all satisfying initial states. Moreover, for any (partial)
solution our algorithm synthesizes witness control strategies to ensure almost-sure
satisfaction of the temporal logic specification. While the proposed algorithm
guarantees progress and soundness in every iteration, it is computationally demanding.
We offer an alternative, more efficient solution for the reachability properties
that decomposes the problem into a series of smaller problems of the same type.
All algorithms are demonstrated on an illustrative case study.
article_processing_charge: No
arxiv: 1
author:
- first_name: Mária
full_name: Svoreňová, Mária
last_name: Svoreňová
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ivana
full_name: Cěrná, Ivana
last_name: Cěrná
- first_name: Cǎlin
full_name: Belta, Cǎlin
last_name: Belta
citation:
ama: 'Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. Temporal
logic control for stochastic linear systems using abstraction refinement of probabilistic
games. Nonlinear Analysis: Hybrid Systems. 2017;23(2):230-253. doi:10.1016/j.nahs.2016.04.006'
apa: 'Svoreňová, M., Kretinsky, J., Chmelik, M., Chatterjee, K., Cěrná, I., &
Belta, C. (2017). Temporal logic control for stochastic linear systems using abstraction
refinement of probabilistic games. Nonlinear Analysis: Hybrid Systems.
Elsevier. https://doi.org/10.1016/j.nahs.2016.04.006'
chicago: 'Svoreňová, Mária, Jan Kretinsky, Martin Chmelik, Krishnendu Chatterjee,
Ivana Cěrná, and Cǎlin Belta. “Temporal Logic Control for Stochastic Linear Systems
Using Abstraction Refinement of Probabilistic Games.” Nonlinear Analysis: Hybrid
Systems. Elsevier, 2017. https://doi.org/10.1016/j.nahs.2016.04.006.'
ieee: 'M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, and C. Belta,
“Temporal logic control for stochastic linear systems using abstraction refinement
of probabilistic games,” Nonlinear Analysis: Hybrid Systems, vol. 23, no.
2. Elsevier, pp. 230–253, 2017.'
ista: 'Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. 2017.
Temporal logic control for stochastic linear systems using abstraction refinement
of probabilistic games. Nonlinear Analysis: Hybrid Systems. 23(2), 230–253.'
mla: 'Svoreňová, Mária, et al. “Temporal Logic Control for Stochastic Linear Systems
Using Abstraction Refinement of Probabilistic Games.” Nonlinear Analysis: Hybrid
Systems, vol. 23, no. 2, Elsevier, 2017, pp. 230–53, doi:10.1016/j.nahs.2016.04.006.'
short: 'M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta,
Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.'
date_created: 2018-12-11T11:51:50Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2023-09-20T09:43:09Z
day: '01'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1016/j.nahs.2016.04.006
ec_funded: 1
external_id:
arxiv:
- '1410.5387'
isi:
- '000390637000014'
intvolume: ' 23'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1410.5387
month: '02'
oa: 1
oa_version: Preprint
page: 230 - 253
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: 'Nonlinear Analysis: Hybrid Systems'
publication_status: published
publisher: Elsevier
publist_id: '5800'
quality_controlled: '1'
related_material:
record:
- id: '1689'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Temporal logic control for stochastic linear systems using abstraction refinement
of probabilistic games
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 23
year: '2017'
...
---
_id: '14205'
abstract:
- lang: eng
text: Two of the most fundamental prototypes of greedy optimization are the matching
pursuit and Frank-Wolfe algorithms. In this paper, we take a unified view on both
classes of methods, leading to the first explicit convergence rates of matching
pursuit methods in an optimization sense, for general sets of atoms. We derive
sublinear (1/t) convergence for both classes on general smooth objectives, and
linear convergence on strongly convex objectives, as well as a clear correspondence
of algorithm variants. Our presented algorithms and rates are affine invariant,
and do not need any incoherence or sparsity assumptions.
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: Rajiv
full_name: Khanna, Rajiv
last_name: Khanna
- first_name: Michael
full_name: Tschannen, Michael
last_name: Tschannen
- first_name: Martin
full_name: Jaggi, Martin
last_name: Jaggi
citation:
ama: 'Locatello F, Khanna R, Tschannen M, Jaggi M. A unified optimization view on
generalized matching pursuit and Frank-Wolfe. In: Proceedings of the 20th International
Conference on Artificial Intelligence and Statistics. Vol 54. ML Research
Press; 2017:860-868.'
apa: 'Locatello, F., Khanna, R., Tschannen, M., & Jaggi, M. (2017). A unified
optimization view on generalized matching pursuit and Frank-Wolfe. In Proceedings
of the 20th International Conference on Artificial Intelligence and Statistics
(Vol. 54, pp. 860–868). Fort Lauderdale, FL, United States: ML Research Press.'
chicago: Locatello, Francesco, Rajiv Khanna, Michael Tschannen, and Martin Jaggi.
“A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe.”
In Proceedings of the 20th International Conference on Artificial Intelligence
and Statistics, 54:860–68. ML Research Press, 2017.
ieee: F. Locatello, R. Khanna, M. Tschannen, and M. Jaggi, “A unified optimization
view on generalized matching pursuit and Frank-Wolfe,” in Proceedings of the
20th International Conference on Artificial Intelligence and Statistics, Fort
Lauderdale, FL, United States, 2017, vol. 54, pp. 860–868.
ista: 'Locatello F, Khanna R, Tschannen M, Jaggi M. 2017. A unified optimization
view on generalized matching pursuit and Frank-Wolfe. Proceedings of the 20th
International Conference on Artificial Intelligence and Statistics. AISTATS: Conference
on Artificial Intelligence and Statistics vol. 54, 860–868.'
mla: Locatello, Francesco, et al. “A Unified Optimization View on Generalized Matching
Pursuit and Frank-Wolfe.” Proceedings of the 20th International Conference
on Artificial Intelligence and Statistics, vol. 54, ML Research Press, 2017,
pp. 860–68.
short: F. Locatello, R. Khanna, M. Tschannen, M. Jaggi, in:, Proceedings of the
20th International Conference on Artificial Intelligence and Statistics, ML Research
Press, 2017, pp. 860–868.
conference:
end_date: 2017-04-22
location: Fort Lauderdale, FL, United States
name: 'AISTATS: Conference on Artificial Intelligence and Statistics'
start_date: 2017-04-20
date_created: 2023-08-22T14:17:19Z
date_published: 2017-02-21T00:00:00Z
date_updated: 2023-09-13T09:49:10Z
day: '21'
department:
- _id: FrLo
extern: '1'
external_id:
arxiv:
- '1702.06457'
intvolume: ' 54'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1702.06457
month: '02'
oa: 1
oa_version: Preprint
page: 860-868
publication: Proceedings of the 20th International Conference on Artificial Intelligence
and Statistics
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: A unified optimization view on generalized matching pursuit and Frank-Wolfe
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 54
year: '2017'
...
---
_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: '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
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'
...
---
_id: '5559'
abstract:
- lang: eng
text: Strong amplifiers of natural selection
article_processing_charge: No
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak , Martin
last_name: 'Nowak '
citation:
ama: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Strong amplifiers of natural
selection. 2017. doi:10.15479/AT:ISTA:51
apa: Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak , M. (2017). Strong
amplifiers of natural selection. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT:ISTA:51
chicago: Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin
Nowak . “Strong Amplifiers of Natural Selection.” Institute of Science and Technology
Austria, 2017. https://doi.org/10.15479/AT:ISTA:51.
ieee: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak , “Strong amplifiers
of natural selection.” Institute of Science and Technology Austria, 2017.
ista: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2017. Strong amplifiers
of natural selection, Institute of Science and Technology Austria, 10.15479/AT:ISTA:51.
mla: Pavlogiannis, Andreas, et al. Strong Amplifiers of Natural Selection.
Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:51.
short: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak , (2017).
datarep_id: '51'
date_created: 2018-12-12T12:31:32Z
date_published: 2017-01-02T00:00:00Z
date_updated: 2024-02-21T13:48:42Z
day: '02'
ddc:
- '519'
department:
- _id: KrCh
doi: 10.15479/AT:ISTA:51
ec_funded: 1
file:
- access_level: open_access
checksum: b427dd46a30096a1911b245640c47af8
content_type: video/mp4
creator: system
date_created: 2018-12-12T13:05:18Z
date_updated: 2020-07-14T12:47:02Z
file_id: '5644'
file_name: IST-2017-51-v1+2_illustration.mp4
file_size: 32987015
relation: main_file
file_date_updated: 2020-07-14T12:47:02Z
has_accepted_license: '1'
keyword:
- natural selection
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '5452'
relation: research_paper
status: public
- id: '5751'
relation: research_paper
status: public
status: public
title: Strong amplifiers of natural selection
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...