---
_id: '1026'
abstract:
- lang: eng
text: The optogenetic revolution enabled spatially-precise and temporally-precise
control over protein function, signaling pathway activation, and animal behavior
with tremendous success in the dissection of signaling networks and neural circuits.
Very recently, optogenetic methods have been paired with optical reporters in
novel drug screening platforms. In these all-optical platforms, light remotely
activated ion channels and kinases thereby obviating the use of electrophysiology
or reagents. Consequences were remarkable operational simplicity, throughput,
and cost-effectiveness that culminated in the identification of new drug candidates.
These blueprints for all-optical assays also revealed potential pitfalls and inspire
all-optical variants of other screens, such as those that aim at better understanding
dynamic drug action or orphan protein function.
acknowledgement: This work was supported by grants of the European Union Seventh Framework
Programme (CIG-303564), the Human Frontier Science Program (RGY0084_2012), and the
Austrian Science Fund FWF (W1232 MolecularDrugTargets).
article_processing_charge: No
article_type: original
author:
- first_name: Viviana
full_name: Agus, Viviana
last_name: Agus
- first_name: Harald L
full_name: Janovjak, Harald L
id: 33BA6C30-F248-11E8-B48F-1D18A9856A87
last_name: Janovjak
orcid: 0000-0002-8023-9315
citation:
ama: 'Agus V, Janovjak HL. Optogenetic methods in drug screening: Technologies and
applications. Current Opinion in Biotechnology. 2017;48:8-14. doi:10.1016/j.copbio.2017.02.006'
apa: 'Agus, V., & Janovjak, H. L. (2017). Optogenetic methods in drug screening:
Technologies and applications. Current Opinion in Biotechnology. Elsevier.
https://doi.org/10.1016/j.copbio.2017.02.006'
chicago: 'Agus, Viviana, and Harald L Janovjak. “Optogenetic Methods in Drug Screening:
Technologies and Applications.” Current Opinion in Biotechnology. Elsevier,
2017. https://doi.org/10.1016/j.copbio.2017.02.006.'
ieee: 'V. Agus and H. L. Janovjak, “Optogenetic methods in drug screening: Technologies
and applications,” Current Opinion in Biotechnology, vol. 48. Elsevier,
pp. 8–14, 2017.'
ista: 'Agus V, Janovjak HL. 2017. Optogenetic methods in drug screening: Technologies
and applications. Current Opinion in Biotechnology. 48, 8–14.'
mla: 'Agus, Viviana, and Harald L. Janovjak. “Optogenetic Methods in Drug Screening:
Technologies and Applications.” Current Opinion in Biotechnology, vol.
48, Elsevier, 2017, pp. 8–14, doi:10.1016/j.copbio.2017.02.006.'
short: V. Agus, H.L. Janovjak, Current Opinion in Biotechnology 48 (2017) 8–14.
date_created: 2018-12-11T11:49:45Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2023-09-22T09:26:06Z
day: '01'
department:
- _id: HaJa
doi: 10.1016/j.copbio.2017.02.006
ec_funded: 1
external_id:
isi:
- '000418313200003'
intvolume: ' 48'
isi: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 8 - 14
project:
- _id: 255BFFFA-B435-11E9-9278-68D0E5697425
grant_number: RGY0084/2012
name: In situ real-time imaging of neurotransmitter signaling using designer optical
sensors (HFSP Young Investigator)
- _id: 25548C20-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '303564'
name: Microbial Ion Channels for Synthetic Neurobiology
- _id: 255A6082-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: W1232-B24
name: Molecular Drug Targets
publication: Current Opinion in Biotechnology
publication_identifier:
issn:
- '09581669'
publication_status: published
publisher: Elsevier
publist_id: '6365'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Optogenetic methods in drug screening: Technologies and applications'
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 48
year: '2017'
...
---
_id: '1027'
abstract:
- lang: eng
text: The rising prevalence of antibiotic resistant bacteria is an increasingly
serious public health challenge. To address this problem, recent work ranging
from clinical studies to theoretical modeling has provided valuable insights into
the mechanisms of resistance, its emergence and spread, and ways to counteract
it. A deeper understanding of the underlying dynamics of resistance evolution
will require a combination of experimental and theoretical expertise from different
disciplines and new technology for studying evolution in the laboratory. Here,
we review recent advances in the quantitative understanding of the mechanisms
and evolution of antibiotic resistance. We focus on key theoretical concepts and
new technology that enables well-controlled experiments. We further highlight
key challenges that can be met in the near future to ultimately develop effective
strategies for combating resistance.
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Marta
full_name: Lukacisinova, Marta
id: 4342E402-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisinova
orcid: 0000-0002-2519-8004
- first_name: Mark Tobias
full_name: Bollenbach, Mark Tobias
id: 3E6DB97A-F248-11E8-B48F-1D18A9856A87
last_name: Bollenbach
orcid: 0000-0003-4398-476X
citation:
ama: Lukacisinova M, Bollenbach MT. Toward a quantitative understanding of antibiotic
resistance evolution. Current Opinion in Biotechnology. 2017;46:90-97.
doi:10.1016/j.copbio.2017.02.013
apa: Lukacisinova, M., & Bollenbach, M. T. (2017). Toward a quantitative understanding
of antibiotic resistance evolution. Current Opinion in Biotechnology. Elsevier.
https://doi.org/10.1016/j.copbio.2017.02.013
chicago: Lukacisinova, Marta, and Mark Tobias Bollenbach. “Toward a Quantitative
Understanding of Antibiotic Resistance Evolution.” Current Opinion in Biotechnology.
Elsevier, 2017. https://doi.org/10.1016/j.copbio.2017.02.013.
ieee: M. Lukacisinova and M. T. Bollenbach, “Toward a quantitative understanding
of antibiotic resistance evolution,” Current Opinion in Biotechnology,
vol. 46. Elsevier, pp. 90–97, 2017.
ista: Lukacisinova M, Bollenbach MT. 2017. Toward a quantitative understanding of
antibiotic resistance evolution. Current Opinion in Biotechnology. 46, 90–97.
mla: Lukacisinova, Marta, and Mark Tobias Bollenbach. “Toward a Quantitative Understanding
of Antibiotic Resistance Evolution.” Current Opinion in Biotechnology,
vol. 46, Elsevier, 2017, pp. 90–97, doi:10.1016/j.copbio.2017.02.013.
short: M. Lukacisinova, M.T. Bollenbach, Current Opinion in Biotechnology 46 (2017)
90–97.
date_created: 2018-12-11T11:49:45Z
date_published: 2017-08-01T00:00:00Z
date_updated: 2024-03-25T23:30:15Z
day: '01'
ddc:
- '570'
department:
- _id: ToBo
doi: 10.1016/j.copbio.2017.02.013
ec_funded: 1
external_id:
isi:
- '000408077400015'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T09:57:57Z
date_updated: 2019-01-18T09:57:57Z
file_id: '5846'
file_name: 2017_CurrentOpinion_Lukaciinova.pdf
file_size: 858338
relation: main_file
success: 1
file_date_updated: 2019-01-18T09:57:57Z
has_accepted_license: '1'
intvolume: ' 46'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 90 - 97
project:
- _id: 25E9AF9E-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P27201-B22
name: Revealing the mechanisms underlying drug interactions
- _id: 25E83C2C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '303507'
name: Optimality principles in responses to antibiotics
- _id: 25EB3A80-B435-11E9-9278-68D0E5697425
grant_number: RGP0042/2013
name: Revealing the fundamental limits of cell growth
publication: Current Opinion in Biotechnology
publication_status: published
publisher: Elsevier
publist_id: '6364'
pubrep_id: '801'
quality_controlled: '1'
related_material:
record:
- id: '6263'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Toward a quantitative understanding of antibiotic resistance evolution
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 46
year: '2017'
...
---
_id: '1028'
abstract:
- lang: eng
text: Optogenetics and photopharmacology provide spatiotemporally precise control
over protein interactions and protein function in cells and animals. Optogenetic
methods that are sensitive to green light and can be used to break protein complexes
are not broadly available but would enable multichromatic experiments with previously
inaccessible biological targets. Herein, we repurposed cobalamin (vitamin B12)
binding domains of bacterial CarH transcription factors for green-light-induced
receptor dissociation. In cultured cells, we observed oligomerization-induced
cell signaling for the fibroblast growth factor receptor 1 fused to cobalamin-binding
domains in the dark that was rapidly eliminated upon illumination. In zebrafish
embryos expressing fusion receptors, green light endowed control over aberrant
fibroblast growth factor signaling during development. Green-light-induced domain
dissociation and light-inactivated receptors will critically expand the optogenetic
toolbox for control of biological processes.
acknowledgement: "This work was supported by a grant from the European Union\U0010FC1Ds
Seventh Framework Programme (CIG-303564). E.R. was supported by the graduate program
MolecularDrugTargets (Austrian Science Fund (FWF), W1232) and a FemTech fellowship
(Austrian Research Promotion Agency, 3580812)"
article_processing_charge: No
author:
- first_name: Stephanie
full_name: Kainrath, Stephanie
id: 32CFBA64-F248-11E8-B48F-1D18A9856A87
last_name: Kainrath
- first_name: Manuela
full_name: Stadler, Manuela
last_name: Stadler
- first_name: Eva
full_name: Gschaider-Reichhart, Eva
id: 3FEE232A-F248-11E8-B48F-1D18A9856A87
last_name: Gschaider-Reichhart
orcid: 0000-0002-7218-7738
- first_name: Martin
full_name: Distel, Martin
last_name: Distel
- first_name: Harald L
full_name: Janovjak, Harald L
id: 33BA6C30-F248-11E8-B48F-1D18A9856A87
last_name: Janovjak
orcid: 0000-0002-8023-9315
citation:
ama: Kainrath S, Stadler M, Gschaider-Reichhart E, Distel M, Janovjak HL. Green-light-induced
inactivation of receptor signaling using cobalamin-binding domains. Angewandte
Chemie - International Edition. 2017;56(16):4608-4611. doi:10.1002/anie.201611998
apa: Kainrath, S., Stadler, M., Gschaider-Reichhart, E., Distel, M., & Janovjak,
H. L. (2017). Green-light-induced inactivation of receptor signaling using cobalamin-binding
domains. Angewandte Chemie - International Edition. Wiley-Blackwell. https://doi.org/10.1002/anie.201611998
chicago: Kainrath, Stephanie, Manuela Stadler, Eva Gschaider-Reichhart, Martin Distel,
and Harald L Janovjak. “Green-Light-Induced Inactivation of Receptor Signaling
Using Cobalamin-Binding Domains.” Angewandte Chemie - International Edition.
Wiley-Blackwell, 2017. https://doi.org/10.1002/anie.201611998.
ieee: S. Kainrath, M. Stadler, E. Gschaider-Reichhart, M. Distel, and H. L. Janovjak,
“Green-light-induced inactivation of receptor signaling using cobalamin-binding
domains,” Angewandte Chemie - International Edition, vol. 56, no. 16. Wiley-Blackwell,
pp. 4608–4611, 2017.
ista: Kainrath S, Stadler M, Gschaider-Reichhart E, Distel M, Janovjak HL. 2017.
Green-light-induced inactivation of receptor signaling using cobalamin-binding
domains. Angewandte Chemie - International Edition. 56(16), 4608–4611.
mla: Kainrath, Stephanie, et al. “Green-Light-Induced Inactivation of Receptor Signaling
Using Cobalamin-Binding Domains.” Angewandte Chemie - International Edition,
vol. 56, no. 16, Wiley-Blackwell, 2017, pp. 4608–11, doi:10.1002/anie.201611998.
short: S. Kainrath, M. Stadler, E. Gschaider-Reichhart, M. Distel, H.L. Janovjak,
Angewandte Chemie - International Edition 56 (2017) 4608–4611.
date_created: 2018-12-11T11:49:46Z
date_published: 2017-03-20T00:00:00Z
date_updated: 2024-03-25T23:30:08Z
day: '20'
ddc:
- '540'
department:
- _id: CaGu
- _id: HaJa
doi: 10.1002/anie.201611998
ec_funded: 1
external_id:
isi:
- '000398154000038'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T09:39:55Z
date_updated: 2019-01-18T09:39:55Z
file_id: '5845'
file_name: 2017_communications_Kainrath.pdf
file_size: 2614942
relation: main_file
success: 1
file_date_updated: 2019-01-18T09:39:55Z
has_accepted_license: '1'
intvolume: ' 56'
isi: 1
issue: '16'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '03'
oa: 1
oa_version: Published Version
page: 4608-4611
project:
- _id: 25548C20-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '303564'
name: Microbial Ion Channels for Synthetic Neurobiology
- _id: 26AA4EF2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: W1232-B24
name: Molecular Drug Targets [do not use to be deleted]
publication: Angewandte Chemie - International Edition
publication_identifier:
issn:
- '14337851'
publication_status: published
publisher: Wiley-Blackwell
publist_id: '6362'
quality_controlled: '1'
related_material:
record:
- id: '418'
relation: dissertation_contains
status: public
- id: '7680'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: Green-light-induced inactivation of receptor signaling using cobalamin-binding
domains
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: 56
year: '2017'
...
---
_id: '1029'
abstract:
- lang: eng
text: RNA Polymerase II pauses and backtracks during transcription, with many consequences
for gene expression and cellular physiology. Here, we show that the energy required
to melt double-stranded nucleic acids in the transcription bubble predicts pausing
in Saccharomyces cerevisiae far more accurately than nucleosome roadblocks do.
In addition, the same energy difference also determines when the RNA polymerase
backtracks instead of continuing to move forward. This data-driven model corroborates—in
a genome wide and quantitative manner—previous evidence that sequence-dependent
thermodynamic features of nucleic acids influence both transcriptional pausing
and backtracking.
article_number: e0174066
article_processing_charge: Yes
author:
- first_name: Martin
full_name: Lukacisin, Martin
id: 298FFE8C-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisin
orcid: 0000-0001-6549-4177
- first_name: Matthieu
full_name: Landon, Matthieu
last_name: Landon
- first_name: Rishi
full_name: Jajoo, Rishi
last_name: Jajoo
citation:
ama: Lukacisin M, Landon M, Jajoo R. Sequence-specific thermodynamic properties
of nucleic acids influence both transcriptional pausing and backtracking in yeast.
PLoS One. 2017;12(3). doi:10.1371/journal.pone.0174066
apa: Lukacisin, M., Landon, M., & Jajoo, R. (2017). Sequence-specific thermodynamic
properties of nucleic acids influence both transcriptional pausing and backtracking
in yeast. PLoS One. Public Library of Science. https://doi.org/10.1371/journal.pone.0174066
chicago: Lukacisin, Martin, Matthieu Landon, and Rishi Jajoo. “Sequence-Specific
Thermodynamic Properties of Nucleic Acids Influence Both Transcriptional Pausing
and Backtracking in Yeast.” PLoS One. Public Library of Science, 2017.
https://doi.org/10.1371/journal.pone.0174066.
ieee: M. Lukacisin, M. Landon, and R. Jajoo, “Sequence-specific thermodynamic properties
of nucleic acids influence both transcriptional pausing and backtracking in yeast,”
PLoS One, vol. 12, no. 3. Public Library of Science, 2017.
ista: Lukacisin M, Landon M, Jajoo R. 2017. Sequence-specific thermodynamic properties
of nucleic acids influence both transcriptional pausing and backtracking in yeast.
PLoS One. 12(3), e0174066.
mla: Lukacisin, Martin, et al. “Sequence-Specific Thermodynamic Properties of Nucleic
Acids Influence Both Transcriptional Pausing and Backtracking in Yeast.” PLoS
One, vol. 12, no. 3, e0174066, Public Library of Science, 2017, doi:10.1371/journal.pone.0174066.
short: M. Lukacisin, M. Landon, R. Jajoo, PLoS One 12 (2017).
date_created: 2018-12-11T11:49:46Z
date_published: 2017-03-16T00:00:00Z
date_updated: 2024-03-25T23:30:03Z
day: '16'
ddc:
- '570'
department:
- _id: ToBo
doi: 10.1371/journal.pone.0174066
external_id:
isi:
- '000396318300121'
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:47Z
date_updated: 2018-12-12T10:09:47Z
file_id: '4772'
file_name: IST-2017-800-v1+1_journal.pone.0174066.pdf
file_size: 3429381
relation: main_file
file_date_updated: 2018-12-12T10:09:47Z
has_accepted_license: '1'
intvolume: ' 12'
isi: 1
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
publication: PLoS One
publication_identifier:
issn:
- '19326203'
publication_status: published
publisher: Public Library of Science
publist_id: '6361'
pubrep_id: '800'
quality_controlled: '1'
related_material:
record:
- id: '5556'
relation: popular_science
status: public
- id: '6392'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Sequence-specific thermodynamic properties of nucleic acids influence both
transcriptional pausing and backtracking in yeast
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: 12
year: '2017'
...
---
_id: '1030'
abstract:
- lang: ger
text: Auf der Suche nach einem Bibliothekssystem entschied sich die Forschungseinrichtung
IST Austria im Jahr 2014 für das Open-Source-Produkt Koha. In einem ersten Schritt
wurden zunächst Grundfunktionen aktiviert um im Anschluss diverse zusätzliche
Tools zum Einsatz zu bringen. Die große Flexibilität des Systems erlaubt maßgeschneiderte
Lösungen für unterschiedlichste Institutionen. Trotz Herausforderungen kann die
Bibliothek auf eine erfolgreiche Implementierung zurückblicken.
- lang: eng
text: "IST Austria was looking for a new library system until 2014 when the research
institute decided\r\nto implement Koha. The library first activated basic functions
of the open-source product and\r\nthen brought additional tools into operation.
The high flexibility of the system allows customized\r\nsolutions for different
institutions. Although the library faced some challenges, it can now look\r\nback
on a successful implementation."
article_processing_charge: No
article_type: original
author:
- first_name: Márton
full_name: Villányi, Márton
id: 3FFCCD3A-F248-11E8-B48F-1D18A9856A87
last_name: Villányi
orcid: 0000-0001-8126-0426
citation:
ama: Villányi M. Ein freies Bibliothekssystem für wissenschaftliche Bibliotheken
– Werkstattbericht der IST Austria Library. Informationspraxis. 2017;3(1).
doi:10.11588/ip.2017.1.35227
apa: Villányi, M. (2017). Ein freies Bibliothekssystem für wissenschaftliche Bibliotheken
– Werkstattbericht der IST Austria Library. Informationspraxis. Verein
Informationspraxis . https://doi.org/10.11588/ip.2017.1.35227
chicago: Villányi, Márton. “Ein Freies Bibliothekssystem Für Wissenschaftliche Bibliotheken
– Werkstattbericht Der IST Austria Library.” Informationspraxis. Verein
Informationspraxis , 2017. https://doi.org/10.11588/ip.2017.1.35227.
ieee: M. Villányi, “Ein freies Bibliothekssystem für wissenschaftliche Bibliotheken
– Werkstattbericht der IST Austria Library,” Informationspraxis, vol. 3,
no. 1. Verein Informationspraxis , 2017.
ista: Villányi M. 2017. Ein freies Bibliothekssystem für wissenschaftliche Bibliotheken
– Werkstattbericht der IST Austria Library. Informationspraxis. 3(1).
mla: Villányi, Márton. “Ein Freies Bibliothekssystem Für Wissenschaftliche Bibliotheken
– Werkstattbericht Der IST Austria Library.” Informationspraxis, vol. 3,
no. 1, Verein Informationspraxis , 2017, doi:10.11588/ip.2017.1.35227.
short: M. Villányi, Informationspraxis 3 (2017).
date_created: 2018-12-11T11:49:46Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-10-18T07:49:29Z
day: '01'
ddc:
- '020'
department:
- _id: E-Lib
doi: 10.11588/ip.2017.1.35227
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:20Z
date_updated: 2018-12-12T10:08:20Z
file_id: '4680'
file_name: IST-2017-799-v1+1_35227-112025-1-PB.pdf
file_size: 201163
relation: main_file
file_date_updated: 2018-12-12T10:08:20Z
has_accepted_license: '1'
intvolume: ' 3'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
popular_science: '1'
publication: Informationspraxis
publication_identifier:
issn:
- 2297-3249
publication_status: published
publisher: 'Verein Informationspraxis '
publist_id: '6360'
pubrep_id: '799'
status: public
title: Ein freies Bibliothekssystem für wissenschaftliche Bibliotheken – Werkstattbericht
der IST Austria Library
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3
year: '2017'
...
---
_id: '10416'
abstract:
- lang: eng
text: 'A fundamental algorithmic problem at the heart of static analysis is Dyck
reachability. The input is a graph where the edges are labeled with different
types of opening and closing parentheses, and the reachability information is
computed via paths whose parentheses are properly matched. We present new results
for Dyck reachability 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 as follows: First, we consider
Dyck reachability on bidirected graphs, which is the standard way of performing
field-sensitive points-to analysis. Given a bidirected graph with n nodes and
m edges, we present: (i) an algorithm with worst-case running time O(m + n · α(n)),
where α(n) is the inverse Ackermann function, improving the previously known O(n2)
time bound; (ii) a matching lower bound that shows that our algorithm is optimal
wrt to worst-case complexity; and (iii) an optimal average-case upper bound of
O(m) time, improving the previously known O(m · logn) bound. Second, we consider
the problem of context-sensitive data-dependence analysis, where the task is to
obtain analysis summaries of library code in the presence of callbacks. Our algorithm
preprocesses libraries in almost linear 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 Matrix Multiplication,
which is a long-standing open problem. Thus we establish that the existing combinatorial
algorithms for Dyck reachability are (conditionally) optimal for general graphs.
We also show that the same hardness holds for graphs of constant treewidth. Finally,
we provide a prototype implementation of our algorithms for both alias analysis
and data-dependence analysis. Our experimental evaluation demonstrates that the
new algorithms significantly outperform all existing methods on the two problems,
over real-world benchmarks.'
acknowledgement: "The research was partly supported by Austrian Science Fund (FWF)
Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), and ERC Start grant
(279307: Graph Games).\r\n"
article_number: '30'
article_processing_charge: No
article_type: original
arxiv: 1
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. Proceedings of the ACM on Programming Languages. 2017;2(POPL).
doi:10.1145/3158118
apa: 'Chatterjee, K., Choudhary, B., & Pavlogiannis, A. (2017). Optimal Dyck
reachability for data-dependence and Alias analysis. Proceedings of the ACM
on Programming Languages. Los Angeles, CA, United States: Association for
Computing Machinery. https://doi.org/10.1145/3158118'
chicago: Chatterjee, Krishnendu, Bhavya Choudhary, and Andreas Pavlogiannis. “Optimal
Dyck Reachability for Data-Dependence and Alias Analysis.” Proceedings of the
ACM on Programming Languages. Association for Computing Machinery, 2017. https://doi.org/10.1145/3158118.
ieee: K. Chatterjee, B. Choudhary, and A. Pavlogiannis, “Optimal Dyck reachability
for data-dependence and Alias analysis,” Proceedings of the ACM on Programming
Languages, vol. 2, no. POPL. Association for Computing Machinery, 2017.
ista: Chatterjee K, Choudhary B, Pavlogiannis A. 2017. Optimal Dyck reachability
for data-dependence and Alias analysis. Proceedings of the ACM on Programming
Languages. 2(POPL), 30.
mla: Chatterjee, Krishnendu, et al. “Optimal Dyck Reachability for Data-Dependence
and Alias Analysis.” Proceedings of the ACM on Programming Languages, vol.
2, no. POPL, 30, Association for Computing Machinery, 2017, doi:10.1145/3158118.
short: K. Chatterjee, B. Choudhary, A. Pavlogiannis, Proceedings of the ACM on Programming
Languages 2 (2017).
conference:
end_date: 2018-01-13
location: Los Angeles, CA, United States
name: 'POPL: Programming Languages'
start_date: 2018-01-07
date_created: 2021-12-05T23:01:48Z
date_published: 2017-12-27T00:00:00Z
date_updated: 2023-02-23T12:27:13Z
day: '27'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1145/3158118
ec_funded: 1
external_id:
arxiv:
- '1910.00241'
file:
- access_level: open_access
checksum: faa3f7b3fe8aab84b50ed805c26a0ee5
content_type: application/pdf
creator: cchlebak
date_created: 2021-12-07T08:06:28Z
date_updated: 2021-12-07T08:06:28Z
file_id: '10421'
file_name: 2017_ACMProgLang_Chatterjee.pdf
file_size: 460188
relation: main_file
success: 1
file_date_updated: 2021-12-07T08:06:28Z
has_accepted_license: '1'
intvolume: ' 2'
issue: POPL
language:
- iso: eng
month: '12'
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'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '5455'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Optimal Dyck reachability for data-dependence and Alias analysis
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 2
year: '2017'
...
---
_id: '10417'
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\n\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."
acknowledgement: "The research was partly supported by Austrian Science Fund (FWF)
Grant No P23499- N23, FWF\r\nNFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant
(279307: Graph Games), and Czech\r\nScience Foundation grant GBP202/12/G061."
article_number: '31'
article_processing_charge: No
article_type: original
arxiv: 1
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. Proceedings of the ACM on Programming Languages.
2017;2(POPL). doi:10.1145/3158119
apa: 'Chalupa, M., Chatterjee, K., Pavlogiannis, A., Sinha, N., & Vaidya, K.
(2017). Data-centric dynamic partial order reduction. Proceedings of the ACM
on Programming Languages. Los Angeles, CA, United States: Association for
Computing Machinery. https://doi.org/10.1145/3158119'
chicago: Chalupa, Marek, Krishnendu Chatterjee, Andreas Pavlogiannis, Nishant Sinha,
and Kapil Vaidya. “Data-Centric Dynamic Partial Order Reduction.” Proceedings
of the ACM on Programming Languages. Association for Computing Machinery,
2017. https://doi.org/10.1145/3158119.
ieee: M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, and K. Vaidya, “Data-centric
dynamic partial order reduction,” Proceedings of the ACM on Programming Languages,
vol. 2, no. POPL. Association for Computing Machinery, 2017.
ista: Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. 2017. Data-centric
dynamic partial order reduction. Proceedings of the ACM on Programming Languages.
2(POPL), 31.
mla: Chalupa, Marek, et al. “Data-Centric Dynamic Partial Order Reduction.” Proceedings
of the ACM on Programming Languages, vol. 2, no. POPL, 31, Association for
Computing Machinery, 2017, doi:10.1145/3158119.
short: M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Proceedings
of the ACM on Programming Languages 2 (2017).
conference:
end_date: 2018-01-13
location: Los Angeles, CA, United States
name: 'POPL: Programming Languages'
start_date: 2018-01-07
date_created: 2021-12-05T23:01:49Z
date_published: 2017-12-27T00:00:00Z
date_updated: 2023-02-23T12:27:16Z
day: '27'
department:
- _id: KrCh
doi: 10.1145/3158119
ec_funded: 1
external_id:
arxiv:
- '1610.01188'
intvolume: ' 2'
issue: POPL
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/doi/10.1145/3158119
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '5448'
relation: earlier_version
status: public
- id: '5456'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Data-centric dynamic partial order reduction
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 2
year: '2017'
...
---
_id: '10418'
abstract:
- lang: eng
text: We present a new proof rule for proving almost-sure termination of probabilistic
programs, including those that contain demonic non-determinism. An important question
for a probabilistic program is whether the probability mass of all its diverging
runs is zero, that is that it terminates "almost surely". Proving that can be
hard, and this paper presents a new method for doing so. It applies directly to
the program's source code, even if the program contains demonic choice. Like others,
we use variant functions (a.k.a. "super-martingales") that are real-valued and
decrease randomly on each loop iteration; but our key innovation is that the amount
as well as the probability of the decrease are parametric. We prove the soundness
of the new rule, indicate where its applicability goes beyond existing rules,
and explain its connection to classical results on denumerable (non-demonic) Markov
chains.
acknowledgement: "McIver and Morgan are grateful to David Basin and the Information
Security Group at ETH Zürich for hosting a six-month stay in Switzerland, during
part of which this work began. And thanks particularly to Andreas Lochbihler, who
shared with us the probabilistic termination problem that led to it. They acknowledge
the support of ARC grant DP140101119. Part of this work was carried out during the
Workshop on Probabilistic Programming Semantics\r\nat McGill University’s Bellairs
Research Institute on Barbados organised by Alexandra Silva and\r\nPrakash Panangaden.
Kaminski and Katoen are grateful to Sebastian Junges for spotting a flaw in §5.4."
article_number: '33'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Annabelle
full_name: Mciver, Annabelle
last_name: Mciver
- first_name: Carroll
full_name: Morgan, Carroll
last_name: Morgan
- first_name: Benjamin Lucien
full_name: Kaminski, Benjamin Lucien
last_name: Kaminski
- first_name: Joost P
full_name: Katoen, Joost P
id: 4524F760-F248-11E8-B48F-1D18A9856A87
last_name: Katoen
citation:
ama: Mciver A, Morgan C, Kaminski BL, Katoen JP. A new proof rule for almost-sure
termination. Proceedings of the ACM on Programming Languages. 2017;2(POPL).
doi:10.1145/3158121
apa: 'Mciver, A., Morgan, C., Kaminski, B. L., & Katoen, J. P. (2017). A new
proof rule for almost-sure termination. Proceedings of the ACM on Programming
Languages. Los Angeles, CA, United States: Association for Computing Machinery.
https://doi.org/10.1145/3158121'
chicago: Mciver, Annabelle, Carroll Morgan, Benjamin Lucien Kaminski, and Joost
P Katoen. “A New Proof Rule for Almost-Sure Termination.” Proceedings of the
ACM on Programming Languages. Association for Computing Machinery, 2017. https://doi.org/10.1145/3158121.
ieee: A. Mciver, C. Morgan, B. L. Kaminski, and J. P. Katoen, “A new proof rule
for almost-sure termination,” Proceedings of the ACM on Programming Languages,
vol. 2, no. POPL. Association for Computing Machinery, 2017.
ista: Mciver A, Morgan C, Kaminski BL, Katoen JP. 2017. A new proof rule for almost-sure
termination. Proceedings of the ACM on Programming Languages. 2(POPL), 33.
mla: Mciver, Annabelle, et al. “A New Proof Rule for Almost-Sure Termination.” Proceedings
of the ACM on Programming Languages, vol. 2, no. POPL, 33, Association for
Computing Machinery, 2017, doi:10.1145/3158121.
short: A. Mciver, C. Morgan, B.L. Kaminski, J.P. Katoen, Proceedings of the ACM
on Programming Languages 2 (2017).
conference:
end_date: 2018-01-13
location: Los Angeles, CA, United States
name: 'POPL: Programming Languages'
start_date: 2018-01-07
date_created: 2021-12-05T23:01:49Z
date_published: 2017-12-07T00:00:00Z
date_updated: 2021-12-07T08:04:14Z
day: '07'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1145/3158121
external_id:
arxiv:
- '1711.03588'
intvolume: ' 2'
issue: POPL
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/doi/10.1145/3158121
month: '12'
oa: 1
oa_version: Published Version
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A new proof rule for almost-sure termination
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 2
year: '2017'
...
---
_id: '1063'
abstract:
- lang: eng
text: Severe environmental change can drive a population extinct unless the population
adapts in time to the new conditions (“evolutionary rescue”). How does biparental
sexual reproduction influence the chances of population persistence compared to
clonal reproduction or selfing? In this article, we set up a one‐locus two‐allele
model for adaptation in diploid species, where rescue is contingent on the establishment
of the mutant homozygote. Reproduction can occur by random mating, selfing, or
clonally. Random mating generates and destroys the rescue mutant; selfing is efficient
at generating it but at the same time depletes the heterozygote, which can lead
to a low mutant frequency in the standing genetic variation. Due to these (and
other) antagonistic effects, we find a nontrivial dependence of population survival
on the rate of sex/selfing, which is strongly influenced by the dominance coefficient
of the mutation before and after the environmental change. Importantly, since
mating with the wild‐type breaks the mutant homozygote up, a slow decay of the
wild‐type population size can impede rescue in randomly mating populations.
article_processing_charge: No
author:
- first_name: Hildegard
full_name: Uecker, Hildegard
id: 2DB8F68A-F248-11E8-B48F-1D18A9856A87
last_name: Uecker
orcid: 0000-0001-9435-2813
citation:
ama: Uecker H. Evolutionary rescue in randomly mating, selfing, and clonal populations.
Evolution. 2017;71(4):845-858. doi:10.1111/evo.13191
apa: Uecker, H. (2017). Evolutionary rescue in randomly mating, selfing, and clonal
populations. Evolution. Wiley-Blackwell. https://doi.org/10.1111/evo.13191
chicago: Uecker, Hildegard. “Evolutionary Rescue in Randomly Mating, Selfing, and
Clonal Populations.” Evolution. Wiley-Blackwell, 2017. https://doi.org/10.1111/evo.13191.
ieee: H. Uecker, “Evolutionary rescue in randomly mating, selfing, and clonal populations,”
Evolution, vol. 71, no. 4. Wiley-Blackwell, pp. 845–858, 2017.
ista: Uecker H. 2017. Evolutionary rescue in randomly mating, selfing, and clonal
populations. Evolution. 71(4), 845–858.
mla: Uecker, Hildegard. “Evolutionary Rescue in Randomly Mating, Selfing, and Clonal
Populations.” Evolution, vol. 71, no. 4, Wiley-Blackwell, 2017, pp. 845–58,
doi:10.1111/evo.13191.
short: H. Uecker, Evolution 71 (2017) 845–858.
date_created: 2018-12-11T11:49:57Z
date_published: 2017-04-01T00:00:00Z
date_updated: 2025-05-28T11:42:51Z
day: '01'
department:
- _id: NiBa
doi: 10.1111/evo.13191
ec_funded: 1
external_id:
isi:
- '000398545200003'
intvolume: ' 71'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://biorxiv.org/content/early/2016/10/14/081042
month: '04'
oa: 1
oa_version: Submitted Version
page: 845 - 858
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Evolution
publication_identifier:
issn:
- '00143820'
publication_status: published
publisher: Wiley-Blackwell
publist_id: '6327'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Evolutionary rescue in randomly mating, selfing, and clonal populations
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 71
year: '2017'
...
---
_id: '1065'
abstract:
- lang: eng
text: 'We consider the problem of reachability in pushdown graphs. We study the
problem for pushdown graphs with constant treewidth. Even for pushdown graphs
with treewidth 1, for the reachability problem we establish the following: (i)
the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem
would contradict the k-clique conjecture and imply faster combinatorial algorithms
for cliques in graphs.'
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: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
citation:
ama: Chatterjee K, Osang GF. Pushdown reachability with constant treewidth. Information
Processing Letters. 2017;122:25-29. doi:10.1016/j.ipl.2017.02.003
apa: Chatterjee, K., & Osang, G. F. (2017). Pushdown reachability with constant
treewidth. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2017.02.003
chicago: Chatterjee, Krishnendu, and Georg F Osang. “Pushdown Reachability with
Constant Treewidth.” Information Processing Letters. Elsevier, 2017. https://doi.org/10.1016/j.ipl.2017.02.003.
ieee: K. Chatterjee and G. F. Osang, “Pushdown reachability with constant treewidth,”
Information Processing Letters, vol. 122. Elsevier, pp. 25–29, 2017.
ista: Chatterjee K, Osang GF. 2017. Pushdown reachability with constant treewidth.
Information Processing Letters. 122, 25–29.
mla: Chatterjee, Krishnendu, and Georg F. Osang. “Pushdown Reachability with Constant
Treewidth.” Information Processing Letters, vol. 122, Elsevier, 2017, pp.
25–29, doi:10.1016/j.ipl.2017.02.003.
short: K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
date_created: 2018-12-11T11:49:57Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T12:08:18Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
doi: 10.1016/j.ipl.2017.02.003
ec_funded: 1
external_id:
isi:
- '000399506600005'
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:17Z
date_updated: 2019-10-15T07:44:51Z
file_id: '4998'
file_name: IST-2018-991-v1+2_2018_Chatterjee_Pushdown_PREPRINT.pdf
file_size: 247657
relation: main_file
file_date_updated: 2019-10-15T07:44:51Z
has_accepted_license: '1'
intvolume: ' 122'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 25 - 29
project:
- _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
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Information Processing Letters
publication_identifier:
issn:
- '00200190'
publication_status: published
publisher: Elsevier
publist_id: '6323'
pubrep_id: '991'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Pushdown reachability with constant treewidth
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 122
year: '2017'
...
---
_id: '1180'
abstract:
- lang: eng
text: In this article we define an algebraic vertex of a generalized polyhedron
and show that the set of algebraic vertices is the smallest set of points needed
to define the polyhedron. We prove that the indicator function of a generalized
polytope P is a linear combination of indicator functions of simplices whose vertices
are algebraic vertices of P. We also show that the indicator function of any generalized
polyhedron is a linear combination, with integer coefficients, of indicator functions
of cones with apices at algebraic vertices and line-cones. The concept of an algebraic
vertex is closely related to the Fourier–Laplace transform. We show that a point
v is an algebraic vertex of a generalized polyhedron P if and only if the tangent
cone of P, at v, has non-zero Fourier–Laplace transform.
article_processing_charge: No
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Imre
full_name: Bárány, Imre
last_name: Bárány
- first_name: Sinai
full_name: Robins, Sinai
last_name: Robins
citation:
ama: Akopyan A, Bárány I, Robins S. Algebraic vertices of non-convex polyhedra.
Advances in Mathematics. 2017;308:627-644. doi:10.1016/j.aim.2016.12.026
apa: Akopyan, A., Bárány, I., & Robins, S. (2017). Algebraic vertices of non-convex
polyhedra. Advances in Mathematics. Academic Press. https://doi.org/10.1016/j.aim.2016.12.026
chicago: Akopyan, Arseniy, Imre Bárány, and Sinai Robins. “Algebraic Vertices of
Non-Convex Polyhedra.” Advances in Mathematics. Academic Press, 2017. https://doi.org/10.1016/j.aim.2016.12.026.
ieee: A. Akopyan, I. Bárány, and S. Robins, “Algebraic vertices of non-convex polyhedra,”
Advances in Mathematics, vol. 308. Academic Press, pp. 627–644, 2017.
ista: Akopyan A, Bárány I, Robins S. 2017. Algebraic vertices of non-convex polyhedra.
Advances in Mathematics. 308, 627–644.
mla: Akopyan, Arseniy, et al. “Algebraic Vertices of Non-Convex Polyhedra.” Advances
in Mathematics, vol. 308, Academic Press, 2017, pp. 627–44, doi:10.1016/j.aim.2016.12.026.
short: A. Akopyan, I. Bárány, S. Robins, Advances in Mathematics 308 (2017) 627–644.
date_created: 2018-12-11T11:50:34Z
date_published: 2017-02-21T00:00:00Z
date_updated: 2023-09-20T11:21:27Z
day: '21'
department:
- _id: HeEd
doi: 10.1016/j.aim.2016.12.026
ec_funded: 1
external_id:
isi:
- '000409292900015'
intvolume: ' 308'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1508.07594
month: '02'
oa: 1
oa_version: Submitted Version
page: 627 - 644
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Advances in Mathematics
publication_identifier:
issn:
- '00018708'
publication_status: published
publisher: Academic Press
publist_id: '6173'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algebraic vertices of non-convex polyhedra
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 308
year: '2017'
...
---
_id: '1187'
abstract:
- lang: eng
text: We construct efficient authentication protocols and message authentication
codes (MACs) whose security can be reduced to the learning parity with noise (LPN)
problem. Despite a large body of work—starting with the (Formula presented.) protocol
of Hopper and Blum in 2001—until now it was not even known how to construct an
efficient authentication protocol from LPN which is secure against man-in-the-middle
attacks. A MAC implies such a (two-round) protocol.
article_processing_charge: No
article_type: original
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniele
full_name: Venturi, Daniele
last_name: Venturi
- first_name: David
full_name: Cash, David
last_name: Cash
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
citation:
ama: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from
hard learning problems. Journal of Cryptology. 2017;30(4):1238-1275. doi:10.1007/s00145-016-9247-3
apa: Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., & Jain, A. (2017). Efficient
authentication from hard learning problems. Journal of Cryptology. Springer.
https://doi.org/10.1007/s00145-016-9247-3
chicago: Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek
Jain. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology.
Springer, 2017. https://doi.org/10.1007/s00145-016-9247-3.
ieee: E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication
from hard learning problems,” Journal of Cryptology, vol. 30, no. 4. Springer,
pp. 1238–1275, 2017.
ista: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication
from hard learning problems. Journal of Cryptology. 30(4), 1238–1275.
mla: Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.”
Journal of Cryptology, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:10.1007/s00145-016-9247-3.
short: E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology
30 (2017) 1238–1275.
date_created: 2018-12-11T11:50:37Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2023-09-20T11:20:58Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/s00145-016-9247-3
ec_funded: 1
external_id:
isi:
- '000410788600007'
file:
- access_level: open_access
checksum: c647520d115b772a1682fc06fa273eb1
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T16:30:17Z
date_updated: 2020-07-14T12:44:37Z
file_id: '7843'
file_name: 2017_JournalCrypto_Kiltz.pdf
file_size: 516959
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 30'
isi: 1
issue: '4'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1238 - 1275
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Journal of Cryptology
publication_status: published
publisher: Springer
publist_id: '6166'
quality_controlled: '1'
related_material:
record:
- id: '3238'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Efficient authentication from hard learning problems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 30
year: '2017'
...
---
_id: '1191'
abstract:
- lang: eng
text: Variation in genotypes may be responsible for differences in dispersal rates,
directional biases, and growth rates of individuals. These traits may favor certain
genotypes and enhance their spatiotemporal spreading into areas occupied by the
less advantageous genotypes. We study how these factors influence the speed of
spreading in the case of two competing genotypes under the assumption that spatial
variation of the total population is small compared to the spatial variation of
the frequencies of the genotypes in the population. In that case, the dynamics
of the frequency of one of the genotypes is approximately described by a generalized
Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP
equation with (nonlinear) frequency-dependent diffusion and advection terms admits
traveling wave solutions that characterize the invasion of the dominant genotype.
Our existence results generalize the classical theory for traveling waves for
the F–KPP with constant coefficients. Moreover, in the particular case of the
quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we
study in detail the influence of the variance in diffusion and mean displacement
rates of the two genotypes on the minimal wave propagation speed.
acknowledgement: "We thank Nick Barton, Katarína Bod’ová, and Sr\r\n-\r\ndan Sarikas
for constructive feed-\r\nback and support. Furthermore, we would like to express
our deep gratitude to the anonymous referees (one\r\nof whom, Jimmy Garnier, agreed
to reveal his identity) and the editor Max Souza, for very helpful and\r\ndetailed
comments and suggestions that significantly helped us to improve the manuscript.
This project has\r\nreceived funding from the European Union’s Seventh Framework
Programme for research, technological\r\ndevelopment and demonstration under Grant
Agreement 618091 Speed of Adaptation in Population Genet-\r\nics and Evolutionary
Computation (SAGE) and the European Research Council (ERC) Grant No. 250152\r\n(SN),
from the Scientific Grant Agency of the Slovak Republic under the Grant 1/0459/13
and by the Slovak\r\nResearch and Development Agency under the Contract No. APVV-14-0378
(RK). RK would also like to\r\nthank IST Austria for its hospitality during the
work on this project."
author:
- first_name: Richard
full_name: Kollár, Richard
last_name: Kollár
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
orcid: 0000-0002-2519-824X
citation:
ama: Kollár R, Novak S. Existence of traveling waves for the generalized F–KPP equation.
Bulletin of Mathematical Biology. 2017;79(3):525-559. doi:10.1007/s11538-016-0244-3
apa: Kollár, R., & Novak, S. (2017). Existence of traveling waves for the generalized
F–KPP equation. Bulletin of Mathematical Biology. Springer. https://doi.org/10.1007/s11538-016-0244-3
chicago: Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for
the Generalized F–KPP Equation.” Bulletin of Mathematical Biology. Springer,
2017. https://doi.org/10.1007/s11538-016-0244-3.
ieee: R. Kollár and S. Novak, “Existence of traveling waves for the generalized
F–KPP equation,” Bulletin of Mathematical Biology, vol. 79, no. 3. Springer,
pp. 525–559, 2017.
ista: Kollár R, Novak S. 2017. Existence of traveling waves for the generalized
F–KPP equation. Bulletin of Mathematical Biology. 79(3), 525–559.
mla: Kollár, Richard, and Sebastian Novak. “Existence of Traveling Waves for the
Generalized F–KPP Equation.” Bulletin of Mathematical Biology, vol. 79,
no. 3, Springer, 2017, pp. 525–59, doi:10.1007/s11538-016-0244-3.
short: R. Kollár, S. Novak, Bulletin of Mathematical Biology 79 (2017) 525–559.
date_created: 2018-12-11T11:50:38Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2025-05-28T11:42:46Z
day: '01'
department:
- _id: NiBa
doi: 10.1007/s11538-016-0244-3
ec_funded: 1
intvolume: ' 79'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1607.00944
month: '03'
oa: 1
oa_version: Preprint
page: 525-559
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Bulletin of Mathematical Biology
publication_status: published
publisher: Springer
publist_id: '6160'
quality_controlled: '1'
scopus_import: 1
status: public
title: Existence of traveling waves for the generalized F–KPP equation
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 79
year: '2017'
...
---
_id: '1192'
abstract:
- lang: eng
text: The main result of this paper is a generalization of the classical blossom
algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean
CSPs where each variable appears in exactly two constraints (we call it edge CSP)
and all constraints are even Δ-matroid relations (represented by lists of tuples).
As a consequence of this, we settle the complexity classification of planar Boolean
CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even
Δ-matroid constraints allows us to extend the tractability result to a larger
class of Δ-matroids that includes many classes that were known to be tractable
before, namely co-independent, compact, local and binary.
article_processing_charge: No
author:
- first_name: Alexandr
full_name: Kazda, Alexandr
id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
last_name: Kazda
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: 'Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of
planar Boolean CSPs. In: SIAM; 2017:307-326. doi:10.1137/1.9781611974782.20'
apa: 'Kazda, A., Kolmogorov, V., & Rolinek, M. (2017). Even delta-matroids and
the complexity of planar Boolean CSPs (pp. 307–326). Presented at the SODA: Symposium
on Discrete Algorithms, Barcelona, Spain: SIAM. https://doi.org/10.1137/1.9781611974782.20'
chicago: Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids
and the Complexity of Planar Boolean CSPs,” 307–26. SIAM, 2017. https://doi.org/10.1137/1.9781611974782.20.
ieee: 'A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity
of planar Boolean CSPs,” presented at the SODA: Symposium on Discrete Algorithms,
Barcelona, Spain, 2017, pp. 307–326.'
ista: 'Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity
of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.'
mla: Kazda, Alexandr, et al. Even Delta-Matroids and the Complexity of Planar
Boolean CSPs. SIAM, 2017, pp. 307–26, doi:10.1137/1.9781611974782.20.
short: A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.
conference:
end_date: 2017-01019
location: Barcelona, Spain
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2017-01-16
date_created: 2018-12-11T11:50:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-20T11:20:26Z
day: '01'
department:
- _id: VlKo
doi: 10.1137/1.9781611974782.20
ec_funded: 1
external_id:
isi:
- '000426965800020'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.03124
month: '01'
oa: 1
oa_version: Submitted Version
page: 307 - 326
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-161197478-2
publication_status: published
publisher: SIAM
publist_id: '6159'
quality_controlled: '1'
related_material:
record:
- id: '6032'
relation: later_version
status: public
status: public
title: Even delta-matroids and the complexity of planar Boolean CSPs
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '1194'
abstract:
- lang: eng
text: 'Termination is one of the basic liveness properties, and we study the termination
problem for probabilistic programs with real-valued variables. Previous works
focused on the qualitative problem that asks whether an input program terminates
with probability~1 (almost-sure termination). A powerful approach for this qualitative
problem is the notion of ranking supermartingales with respect to a given set
of invariants. The quantitative problem (probabilistic termination) asks for bounds
on the termination probability. A fundamental and conceptual drawback of the existing
approaches to address probabilistic termination is that even though the supermartingales
consider the probabilistic behavior of the programs, the invariants are obtained
completely ignoring the probabilistic aspect. In this work we address the probabilistic
termination problem for linear-arithmetic probabilistic programs with nondeterminism.
We define the notion of {\em stochastic invariants}, which are constraints along
with a probability bound that the constraints hold. We introduce a concept of
{\em repulsing supermartingales}. First, we show that repulsing supermartingales
can be used to obtain bounds on the probability of the stochastic invariants.
Second, we show the effectiveness of repulsing supermartingales in the following
three ways: (1)~With a combination of ranking and repulsing supermartingales we
can compute lower bounds on the probability of termination; (2)~repulsing supermartingales
provide witnesses for refutation of almost-sure termination; and (3)~with a combination
of ranking and repulsing supermartingales we can establish persistence properties
of probabilistic programs. We also present results on related computational problems
and an experimental evaluation of our approach on academic examples. '
alternative_title:
- ACM SIGPLAN Notices
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: Petr
full_name: Novotny, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotny
- first_name: Djordje
full_name: Zikelic, Djordje
last_name: Zikelic
citation:
ama: 'Chatterjee K, Novotný P, Zikelic D. Stochastic invariants for probabilistic
termination. In: Vol 52. ACM; 2017:145-160. doi:10.1145/3009837.3009873'
apa: 'Chatterjee, K., Novotný, P., & Zikelic, D. (2017). Stochastic invariants
for probabilistic termination (Vol. 52, pp. 145–160). Presented at the POPL: Principles
of Programming Languages, Paris, France: ACM. https://doi.org/10.1145/3009837.3009873'
chicago: Chatterjee, Krishnendu, Petr Novotný, and Djordje Zikelic. “Stochastic
Invariants for Probabilistic Termination,” 52:145–60. ACM, 2017. https://doi.org/10.1145/3009837.3009873.
ieee: 'K. Chatterjee, P. Novotný, and D. Zikelic, “Stochastic invariants for probabilistic
termination,” presented at the POPL: Principles of Programming Languages, Paris,
France, 2017, vol. 52, no. 1, pp. 145–160.'
ista: 'Chatterjee K, Novotný P, Zikelic D. 2017. Stochastic invariants for probabilistic
termination. POPL: Principles of Programming Languages, ACM SIGPLAN Notices, vol.
52, 145–160.'
mla: Chatterjee, Krishnendu, et al. Stochastic Invariants for Probabilistic Termination.
Vol. 52, no. 1, ACM, 2017, pp. 145–60, doi:10.1145/3009837.3009873.
short: K. Chatterjee, P. Novotný, D. Zikelic, in:, ACM, 2017, pp. 145–160.
conference:
end_date: 2017-01-21
location: Paris, France
name: 'POPL: Principles of Programming Languages'
start_date: 2017-01-15
date_created: 2018-12-11T11:50:39Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-07-14T09:09:58Z
day: '01'
department:
- _id: KrCh
doi: 10.1145/3009837.3009873
ec_funded: 1
external_id:
isi:
- '000408311200013'
intvolume: ' 52'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.01063
month: '01'
oa: 1
oa_version: Submitted Version
page: 145 - 160
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_identifier:
issn:
- '07308566'
publication_status: published
publisher: ACM
publist_id: '6157'
quality_controlled: '1'
related_material:
record:
- id: '14539'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Stochastic invariants for probabilistic termination
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 52
year: '2017'
...
---
_id: '1196'
abstract:
- lang: eng
text: 'We define the . model-measuring problem: given a model . M and specification
. ϕ, what is the maximal distance . ρ such that all models . M'' within distance
. ρ from . M satisfy (or violate) . ϕ. The model-measuring problem presupposes
a distance function on models. We concentrate on . automatic distance functions,
which are defined by weighted automata. The model-measuring problem subsumes several
generalizations of the classical model-checking problem, in particular, quantitative
model-checking problems that measure the degree of satisfaction of a specification;
robustness problems that measure how much a model can be perturbed without violating
the specification; and parameter synthesis for hybrid systems. We show that for
automatic distance functions, and (a) . ω-regular linear-time, (b) . ω-regular
branching-time, and (c) hybrid specifications, the model-measuring problem can
be solved.We use automata-theoretic model-checking methods for model measuring,
replacing the emptiness question for word, tree, and hybrid automata by the .
optimal-value question for the weighted versions of these automata. For automata
over words and trees, we consider weighted automata that accumulate weights by
maximizing, summing, discounting, and limit averaging. For hybrid automata, we
consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete)
weighted automata.We give several examples of using the model-measuring problem
to compute various notions of robustness and quantitative satisfaction for temporal
specifications. Further, we propose the modeling framework for model measuring
to ease the specification and reduce the likelihood of errors in modeling.Finally,
we present a variant of the model-measuring problem, called the . model-repair
problem. The model-repair problem applies to models that do not satisfy the specification;
it can be used to derive restrictions, under which the model satisfies the specification,
i.e., to repair the model.'
acknowledgement: "This research was supported in part by the European Research Council
(ERC) under grant 267989 (QUAREM), by the Austrian Science Fund1 (FWF) under grants
S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), and by the National Science
Centre (NCN), Poland under grant 2014/15/D/ST6/04543.\r\nA Technical Report of this
article is available via: https://repository.ist.ac.at/171/"
article_processing_charge: No
author:
- 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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: 'Henzinger TA, Otop J. Model measuring for discrete and hybrid systems. Nonlinear
Analysis: Hybrid Systems. 2017;23:166-190. doi:10.1016/j.nahs.2016.09.001'
apa: 'Henzinger, T. A., & Otop, J. (2017). Model measuring for discrete and
hybrid systems. Nonlinear Analysis: Hybrid Systems. Elsevier. https://doi.org/10.1016/j.nahs.2016.09.001'
chicago: 'Henzinger, Thomas A, and Jan Otop. “Model Measuring for Discrete and Hybrid
Systems.” Nonlinear Analysis: Hybrid Systems. Elsevier, 2017. https://doi.org/10.1016/j.nahs.2016.09.001.'
ieee: 'T. A. Henzinger and J. Otop, “Model measuring for discrete and hybrid systems,”
Nonlinear Analysis: Hybrid Systems, vol. 23. Elsevier, pp. 166–190, 2017.'
ista: 'Henzinger TA, Otop J. 2017. Model measuring for discrete and hybrid systems.
Nonlinear Analysis: Hybrid Systems. 23, 166–190.'
mla: 'Henzinger, Thomas A., and Jan Otop. “Model Measuring for Discrete and Hybrid
Systems.” Nonlinear Analysis: Hybrid Systems, vol. 23, Elsevier, 2017,
pp. 166–90, doi:10.1016/j.nahs.2016.09.001.'
short: 'T.A. Henzinger, J. Otop, Nonlinear Analysis: Hybrid Systems 23 (2017) 166–190.'
date_created: 2018-12-11T11:50:39Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2023-09-20T11:18:50Z
day: '01'
department:
- _id: ToHe
doi: 10.1016/j.nahs.2016.09.001
ec_funded: 1
external_id:
isi:
- '000390637000011'
intvolume: ' 23'
isi: 1
language:
- iso: eng
month: '02'
oa_version: None
page: 166 - 190
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
publication: 'Nonlinear Analysis: Hybrid Systems'
publication_status: published
publisher: Elsevier
publist_id: '6154'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Model measuring for discrete and hybrid systems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 23
year: '2017'
...
---
_id: '1198'
abstract:
- lang: eng
text: We consider a model of fermions interacting via point interactions, defined
via a certain weighted Dirichlet form. While for two particles the interaction
corresponds to infinite scattering length, the presence of further particles effectively
decreases the interaction strength. We show that the model becomes trivial in
the thermodynamic limit, in the sense that the free energy density at any given
particle density and temperature agrees with the corresponding expression for
non-interacting particles.
acknowledgement: 'Open access funding provided by Institute of Science and Technology
(IST Austria). '
article_processing_charge: Yes (via OA deal)
author:
- first_name: Thomas
full_name: Moser, Thomas
id: 2B5FC9A4-F248-11E8-B48F-1D18A9856A87
last_name: Moser
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Moser T, Seiringer R. Triviality of a model of particles with point interactions
in the thermodynamic limit. Letters in Mathematical Physics. 2017;107(3):533-552.
doi:10.1007/s11005-016-0915-x
apa: Moser, T., & Seiringer, R. (2017). Triviality of a model of particles with
point interactions in the thermodynamic limit. Letters in Mathematical Physics.
Springer. https://doi.org/10.1007/s11005-016-0915-x
chicago: Moser, Thomas, and Robert Seiringer. “Triviality of a Model of Particles
with Point Interactions in the Thermodynamic Limit.” Letters in Mathematical
Physics. Springer, 2017. https://doi.org/10.1007/s11005-016-0915-x.
ieee: T. Moser and R. Seiringer, “Triviality of a model of particles with point
interactions in the thermodynamic limit,” Letters in Mathematical Physics,
vol. 107, no. 3. Springer, pp. 533–552, 2017.
ista: Moser T, Seiringer R. 2017. Triviality of a model of particles with point
interactions in the thermodynamic limit. Letters in Mathematical Physics. 107(3),
533–552.
mla: Moser, Thomas, and Robert Seiringer. “Triviality of a Model of Particles with
Point Interactions in the Thermodynamic Limit.” Letters in Mathematical Physics,
vol. 107, no. 3, Springer, 2017, pp. 533–52, doi:10.1007/s11005-016-0915-x.
short: T. Moser, R. Seiringer, Letters in Mathematical Physics 107 (2017) 533–552.
date_created: 2018-12-11T11:50:40Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2023-09-20T11:18:13Z
day: '01'
ddc:
- '510'
- '539'
department:
- _id: RoSe
doi: 10.1007/s11005-016-0915-x
external_id:
isi:
- '000394280200007'
file:
- access_level: open_access
checksum: c0c835def162c1bc52f978fad26e3c2f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:40Z
date_updated: 2020-07-14T12:44:38Z
file_id: '5296'
file_name: IST-2016-723-v1+1_s11005-016-0915-x.pdf
file_size: 587207
relation: main_file
file_date_updated: 2020-07-14T12:44:38Z
has_accepted_license: '1'
intvolume: ' 107'
isi: 1
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: ' 533 - 552'
project:
- _id: 25C878CE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P27533_N27
name: Structure of the Excitation Spectrum for Many-Body Quantum Systems
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Letters in Mathematical Physics
publication_identifier:
issn:
- '03779017'
publication_status: published
publisher: Springer
publist_id: '6152'
pubrep_id: '723'
quality_controlled: '1'
related_material:
record:
- id: '52'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Triviality of a model of particles with point interactions in the thermodynamic
limit
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: 107
year: '2017'
...
---
_id: '1199'
abstract:
- lang: eng
text: Much of quantitative genetics is based on the ‘infinitesimal model’, under
which selection has a negligible effect on the genetic variance. This is typically
justified by assuming a very large number of loci with additive effects. However,
it applies even when genes interact, provided that the number of loci is large
enough that selection on each of them is weak relative to random drift. In the
long term, directional selection will change allele frequencies, but even then,
the effects of epistasis on the ultimate change in trait mean due to selection
may be modest. Stabilising selection can maintain many traits close to their optima,
even when the underlying alleles are weakly selected. However, the number of traits
that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this
is hard to reconcile with the apparent complexity of many organisms. Just as for
the mutation load, this limit can be evaded by a particular form of negative epistasis.
A more robust limit is set by the variance in reproductive success. This suggests
that selection accumulates information most efficiently in the infinitesimal regime,
when selection on individual alleles is weak, and comparable with random drift.
A review of evidence on selection strength suggests that although most variance
in fitness may be because of alleles with large Nes, substantial amounts of adaptation
may be because of alleles in the infinitesimal regime, in which epistasis has
modest effects.
article_processing_charge: No
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Barton NH. How does epistasis influence the response to selection? Heredity.
2017;118:96-109. doi:10.1038/hdy.2016.109
apa: Barton, N. H. (2017). How does epistasis influence the response to selection?
Heredity. Nature Publishing Group. https://doi.org/10.1038/hdy.2016.109
chicago: Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?”
Heredity. Nature Publishing Group, 2017. https://doi.org/10.1038/hdy.2016.109.
ieee: N. H. Barton, “How does epistasis influence the response to selection?,” Heredity,
vol. 118. Nature Publishing Group, pp. 96–109, 2017.
ista: Barton NH. 2017. How does epistasis influence the response to selection? Heredity.
118, 96–109.
mla: Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?”
Heredity, vol. 118, Nature Publishing Group, 2017, pp. 96–109, doi:10.1038/hdy.2016.109.
short: N.H. Barton, Heredity 118 (2017) 96–109.
date_created: 2018-12-11T11:50:40Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-05-28T11:42:47Z
day: '01'
department:
- _id: NiBa
doi: 10.1038/hdy.2016.109
ec_funded: 1
external_id:
isi:
- '000392229100011'
intvolume: ' 118'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5176114/
month: '01'
oa: 1
oa_version: Submitted Version
page: 96 - 109
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Heredity
publication_status: published
publisher: Nature Publishing Group
publist_id: '6151'
quality_controlled: '1'
related_material:
record:
- id: '9710'
relation: research_data
status: public
scopus_import: '1'
status: public
title: How does epistasis influence the response to selection?
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 118
year: '2017'
...
---
_id: '1207'
abstract:
- lang: eng
text: The eigenvalue distribution of the sum of two large Hermitian matrices, when
one of them is conjugated by a Haar distributed unitary matrix, is asymptotically
given by the free convolution of their spectral distributions. We prove that this
convergence also holds locally in the bulk of the spectrum, down to the optimal
scales larger than the eigenvalue spacing. The corresponding eigenvectors are
fully delocalized. Similar results hold for the sum of two real symmetric matrices,
when one is conjugated by Haar orthogonal matrix.
article_processing_charge: Yes (via OA deal)
author:
- first_name: Zhigang
full_name: Bao, Zhigang
id: 442E6A6C-F248-11E8-B48F-1D18A9856A87
last_name: Bao
orcid: 0000-0003-3036-1475
- first_name: László
full_name: Erdös, László
id: 4DBD5372-F248-11E8-B48F-1D18A9856A87
last_name: Erdös
orcid: 0000-0001-5366-9603
- first_name: Kevin
full_name: Schnelli, Kevin
id: 434AD0AE-F248-11E8-B48F-1D18A9856A87
last_name: Schnelli
orcid: 0000-0003-0954-3231
citation:
ama: Bao Z, Erdös L, Schnelli K. Local law of addition of random matrices on optimal
scale. Communications in Mathematical Physics. 2017;349(3):947-990. doi:10.1007/s00220-016-2805-6
apa: Bao, Z., Erdös, L., & Schnelli, K. (2017). Local law of addition of random
matrices on optimal scale. Communications in Mathematical Physics. Springer.
https://doi.org/10.1007/s00220-016-2805-6
chicago: Bao, Zhigang, László Erdös, and Kevin Schnelli. “Local Law of Addition
of Random Matrices on Optimal Scale.” Communications in Mathematical Physics.
Springer, 2017. https://doi.org/10.1007/s00220-016-2805-6.
ieee: Z. Bao, L. Erdös, and K. Schnelli, “Local law of addition of random matrices
on optimal scale,” Communications in Mathematical Physics, vol. 349, no.
3. Springer, pp. 947–990, 2017.
ista: Bao Z, Erdös L, Schnelli K. 2017. Local law of addition of random matrices
on optimal scale. Communications in Mathematical Physics. 349(3), 947–990.
mla: Bao, Zhigang, et al. “Local Law of Addition of Random Matrices on Optimal Scale.”
Communications in Mathematical Physics, vol. 349, no. 3, Springer, 2017,
pp. 947–90, doi:10.1007/s00220-016-2805-6.
short: Z. Bao, L. Erdös, K. Schnelli, Communications in Mathematical Physics 349
(2017) 947–990.
date_created: 2018-12-11T11:50:43Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2023-09-20T11:16:57Z
day: '01'
ddc:
- '530'
department:
- _id: LaEr
doi: 10.1007/s00220-016-2805-6
ec_funded: 1
external_id:
isi:
- '000393696700005'
file:
- access_level: open_access
checksum: ddff79154c3daf27237de5383b1264a9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:47Z
date_updated: 2020-07-14T12:44:39Z
file_id: '5102'
file_name: IST-2016-722-v1+1_s00220-016-2805-6.pdf
file_size: 1033743
relation: main_file
file_date_updated: 2020-07-14T12:44:39Z
has_accepted_license: '1'
intvolume: ' 349'
isi: 1
issue: '3'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 947 - 990
project:
- _id: 258DCDE6-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '338804'
name: Random matrices, universality and disordered quantum systems
publication: Communications in Mathematical Physics
publication_identifier:
issn:
- '00103616'
publication_status: published
publisher: Springer
publist_id: '6141'
pubrep_id: '722'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local law of addition of random matrices on optimal scale
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: 349
year: '2017'
...
---
_id: '1208'
abstract:
- lang: eng
text: We study parameter estimation in linear Gaussian covariance models, which
are p-dimensional Gaussian models with linear constraints on the covariance matrix.
Maximum likelihood estimation for this class of models leads to a non-convex optimization
problem which typically has many local maxima. Using recent results on the asymptotic
distribution of extreme eigenvalues of the Wishart distribution, we provide sufficient
conditions for any hill climbing method to converge to the global maximum. Although
we are primarily interested in the case in which n≫p, the proofs of our results
utilize large sample asymptotic theory under the scheme n/p→γ>1. Remarkably,
our numerical simulations indicate that our results remain valid for p as small
as 2. An important consequence of this analysis is that, for sample sizes n≃14p,
maximum likelihood estimation for linear Gaussian covariance models behaves as
if it were a convex optimization problem. © 2016 The Royal Statistical Society
and Blackwell Publishing Ltd.
article_processing_charge: No
author:
- first_name: Piotr
full_name: Zwiernik, Piotr
last_name: Zwiernik
- first_name: Caroline
full_name: Uhler, Caroline
id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
last_name: Uhler
orcid: 0000-0002-7008-0216
- first_name: Donald
full_name: Richards, Donald
last_name: Richards
citation:
ama: 'Zwiernik P, Uhler C, Richards D. Maximum likelihood estimation for linear
Gaussian covariance models. Journal of the Royal Statistical Society Series
B: Statistical Methodology. 2017;79(4):1269-1292. doi:10.1111/rssb.12217'
apa: 'Zwiernik, P., Uhler, C., & Richards, D. (2017). Maximum likelihood estimation
for linear Gaussian covariance models. Journal of the Royal Statistical Society.
Series B: Statistical Methodology. Wiley-Blackwell. https://doi.org/10.1111/rssb.12217'
chicago: 'Zwiernik, Piotr, Caroline Uhler, and Donald Richards. “Maximum Likelihood
Estimation for Linear Gaussian Covariance Models.” Journal of the Royal Statistical
Society. Series B: Statistical Methodology. Wiley-Blackwell, 2017. https://doi.org/10.1111/rssb.12217.'
ieee: 'P. Zwiernik, C. Uhler, and D. Richards, “Maximum likelihood estimation for
linear Gaussian covariance models,” Journal of the Royal Statistical Society.
Series B: Statistical Methodology, vol. 79, no. 4. Wiley-Blackwell, pp. 1269–1292,
2017.'
ista: 'Zwiernik P, Uhler C, Richards D. 2017. Maximum likelihood estimation for
linear Gaussian covariance models. Journal of the Royal Statistical Society. Series
B: Statistical Methodology. 79(4), 1269–1292.'
mla: 'Zwiernik, Piotr, et al. “Maximum Likelihood Estimation for Linear Gaussian
Covariance Models.” Journal of the Royal Statistical Society. Series B: Statistical
Methodology, vol. 79, no. 4, Wiley-Blackwell, 2017, pp. 1269–92, doi:10.1111/rssb.12217.'
short: 'P. Zwiernik, C. Uhler, D. Richards, Journal of the Royal Statistical Society.
Series B: Statistical Methodology 79 (2017) 1269–1292.'
date_created: 2018-12-11T11:50:43Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-09-20T11:17:21Z
day: '01'
department:
- _id: CaUh
doi: 10.1111/rssb.12217
external_id:
isi:
- '000411712300012'
intvolume: ' 79'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1408.5604
month: '09'
oa: 1
oa_version: Submitted Version
page: 1269 - 1292
project:
- _id: 2530CA10-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Y 903-N35
name: 'Gaussian Graphical Models: Theory and Applications'
publication: 'Journal of the Royal Statistical Society. Series B: Statistical Methodology'
publication_identifier:
issn:
- '13697412'
publication_status: published
publisher: Wiley-Blackwell
publist_id: '6142'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maximum likelihood estimation for linear Gaussian covariance models
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 79
year: '2017'
...