---
_id: '818'
abstract:
- lang: eng
text: 'Antibiotics have diverse effects on bacteria, including massive changes in
bacterial gene expression. Whereas the gene expression changes under many antibiotics
have been measured, the temporal organization of these responses and their dependence
on the bacterial growth rate are unclear. As described in Chapter 1, we quantified
the temporal gene expression changes in the bacterium Escherichia coli in response
to the sudden exposure to antibiotics using a fluorescent reporter library and
a robotic system. Our data show temporally structured gene expression responses,
with response times for individual genes ranging from tens of minutes to several
hours. We observed that many stress response genes were activated in response
to antibiotics. As certain stress responses cross-protect bacteria from other
stressors, we then asked whether cellular responses to antibiotics have a similar
protective role in Chapter 2. Indeed, we found that the trimethoprim-induced acid
stress response protects bacteria from subsequent acid stress. We combined microfluidics
with time-lapse imaging to monitor survival, intracellular pH, and acid stress
response in single cells. This approach revealed that the variable expression
of the acid resistance operon gadBC strongly correlates with single-cell survival
time. Cells with higher gadBC expression following trimethoprim maintain higher
intracellular pH and survive the acid stress longer. Overall, we provide a way
to identify single-cell cross-protection between antibiotics and environmental
stressors from temporal gene expression data, and show how antibiotics can increase
bacterial fitness in changing environments. While gene expression changes to antibiotics
show a clear temporal structure at the population-level, it is unclear whether
this clear temporal order is followed by every single cell. Using dual-reporter
strains described in Chapter 3, we measured gene expression dynamics of promoter
pairs in the same cells using microfluidics and microscopy. Chapter 4 shows that
the oxidative stress response and the DNA stress response showed little timing
variability and a clear temporal order under the antibiotic nitrofurantoin. In
contrast, the acid stress response under trimethoprim ran independently from all
other activated response programs including the DNA stress response, which showed
particularly high timing variability in this stress condition. In summary, this
approach provides insight into the temporal organization of gene expression programs
at the single-cell level and suggests dependencies between response programs and
the underlying variability-introducing mechanisms. Altogether, this work advances
our understanding of the diverse effects that antibiotics have on bacteria. These
results were obtained by taking into account gene expression dynamics, which allowed
us to identify general principles, molecular mechanisms, and dependencies between
genes. Our findings may have implications for infectious disease treatments, and
microbial communities in the human body and in nature. '
acknowledgement: 'First of all, I would like to express great gratitude to my PhD
supervisor Tobias Bollenbach. Through his open and trusting attitude I had the freedom
to explore different scientific directions during this project, and follow the research
lines of my interest. I am thankful for constructive and often extensive discussions
and his support and commitment during the different stages of my PhD. I want to
thank my committee members, Călin Guet, Terry Hwa and Nassos Typas for their interest
and their valuable input to this project. Special thanks to Nassos for career guidance,
and for accepting me in his lab. A big thank you goes to the past, present and affiliated
members of the Bollenbach group: Guillaume Chevereau, Marjon de Vos, Marta Lukačišinová,
Veronika Bierbaum, Qi Qin, Marcin Zagórski, Martin Lukačišin, Andreas Angermayr,
Bor Kavčič, Julia Tischler, Dilay Ayhan, Jaroslav Ferenc, and Georg Rieckh. I enjoyed
working and discussing with you very much and I will miss our lengthy group meetings,
our inspiring journal clubs, and our common lunches. Special thanks to Bor for great
mental and professional support during the hard months of thesis writing, and to
Marta for very creative times during the beginning of our PhDs. May the ‘Bacterial
Survival Guide’ decorate the walls of IST forever! A great thanks to my friend and
collaborator Georg Rieckh for his enthusiasm and for getting so involved in these
projects, for his endurance and for his company throughout the years. Thanks to
the FriSBi crowd at IST Austria for interesting meetings and discussions. In particular
I want to thank Magdalena Steinrück, and Anna Andersson for inspiring exchange,
and enjoyable time together. Thanks to everybody who contributed to the cover for
Cell Systems: The constructive input from Tobias Bollenbach, Bor Kavčič, Georg Rieckh,
Marta Lukačišinová, and Sebastian Nozzi, and the professional implementation by
the graphic designer Martina Markus from the University of Cologne. Thanks to all
my office mates in the first floor Bertalanffy building throughout the years: for
ensuring a pleasant working atmosphere, and for your company! In general, I want
to thank all the people that make IST such a great environment, with the many possibilities
to shape our own social and research environment. I want to thank my family for
all kind of practical support during the years, and my second family in Argentina
for their enthusiasm. Thanks to my brother Bernhard and my sister Martina for being
great siblings, and to Helena and Valentin for the joy you brought to my life. My
deep gratitude goes to Sebastian Nozzi, for constant support, patience, love and
for believing in me. '
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Karin
full_name: Mitosch, Karin
id: 39B66846-F248-11E8-B48F-1D18A9856A87
last_name: Mitosch
citation:
ama: Mitosch K. Timing, variability and cross-protection in bacteria – insights
from dynamic gene expression responses to antibiotics. 2017. doi:10.15479/AT:ISTA:th_862
apa: Mitosch, K. (2017). Timing, variability and cross-protection in bacteria
– insights from dynamic gene expression responses to antibiotics. Institute
of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_862
chicago: Mitosch, Karin. “Timing, Variability and Cross-Protection in Bacteria –
Insights from Dynamic Gene Expression Responses to Antibiotics.” Institute of
Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_862.
ieee: K. Mitosch, “Timing, variability and cross-protection in bacteria – insights
from dynamic gene expression responses to antibiotics,” Institute of Science and
Technology Austria, 2017.
ista: Mitosch K. 2017. Timing, variability and cross-protection in bacteria – insights
from dynamic gene expression responses to antibiotics. Institute of Science and
Technology Austria.
mla: Mitosch, Karin. Timing, Variability and Cross-Protection in Bacteria – Insights
from Dynamic Gene Expression Responses to Antibiotics. Institute of Science
and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_862.
short: K. Mitosch, Timing, Variability and Cross-Protection in Bacteria – Insights
from Dynamic Gene Expression Responses to Antibiotics, Institute of Science and
Technology Austria, 2017.
date_created: 2018-12-11T11:48:40Z
date_published: 2017-09-27T00:00:00Z
date_updated: 2023-09-07T12:00:26Z
day: '27'
ddc:
- '571'
- '579'
degree_awarded: PhD
department:
- _id: ToBo
doi: 10.15479/AT:ISTA:th_862
file:
- access_level: closed
checksum: da3993c5f90f59a8e8623cc31ad501dd
content_type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
creator: dernst
date_created: 2019-04-05T08:48:51Z
date_updated: 2020-07-14T12:48:09Z
file_id: '6210'
file_name: Thesis_KarinMitosch.docx
file_size: 6331071
relation: source_file
- access_level: open_access
checksum: 24c3d9e51992f1b721f3df55aa13fcb8
content_type: application/pdf
creator: dernst
date_created: 2019-04-05T08:48:51Z
date_updated: 2020-07-14T12:48:09Z
file_id: '6211'
file_name: Thesis_KarinMitosch.pdf
file_size: 9289852
relation: main_file
file_date_updated: 2020-07-14T12:48:09Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: '113'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6831'
pubrep_id: '862'
related_material:
record:
- id: '2001'
relation: part_of_dissertation
status: public
- id: '666'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Mark Tobias
full_name: Bollenbach, Mark Tobias
id: 3E6DB97A-F248-11E8-B48F-1D18A9856A87
last_name: Bollenbach
orcid: 0000-0003-4398-476X
title: Timing, variability and cross-protection in bacteria – insights from dynamic
gene expression responses to antibiotics
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: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '666'
abstract:
- lang: eng
text: Antibiotics elicit drastic changes in microbial gene expression, including
the induction of stress response genes. While certain stress responses are known
to “cross-protect” bacteria from other stressors, it is unclear whether cellular
responses to antibiotics have a similar protective role. By measuring the genome-wide
transcriptional response dynamics of Escherichia coli to four antibiotics, we
found that trimethoprim induces a rapid acid stress response that protects bacteria
from subsequent exposure to acid. Combining microfluidics with time-lapse imaging
to monitor survival and acid stress response in single cells revealed that the
noisy expression of the acid resistance operon gadBC correlates with single-cell
survival. Cells with higher gadBC expression following trimethoprim maintain higher
intracellular pH and survive the acid stress longer. The seemingly random single-cell
survival under acid stress can therefore be predicted from gadBC expression and
rationalized in terms of GadB/C molecular function. Overall, we provide a roadmap
for identifying the molecular mechanisms of single-cell cross-protection between
antibiotics and other stressors.
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Karin
full_name: Mitosch, Karin
id: 39B66846-F248-11E8-B48F-1D18A9856A87
last_name: Mitosch
- first_name: Georg
full_name: Rieckh, Georg
id: 34DA8BD6-F248-11E8-B48F-1D18A9856A87
last_name: Rieckh
- first_name: Tobias
full_name: Bollenbach, Tobias
id: 3E6DB97A-F248-11E8-B48F-1D18A9856A87
last_name: Bollenbach
orcid: 0000-0003-4398-476X
citation:
ama: Mitosch K, Rieckh G, Bollenbach MT. Noisy response to antibiotic stress predicts
subsequent single cell survival in an acidic environment. Cell Systems.
2017;4(4):393-403. doi:10.1016/j.cels.2017.03.001
apa: Mitosch, K., Rieckh, G., & Bollenbach, M. T. (2017). Noisy response to
antibiotic stress predicts subsequent single cell survival in an acidic environment.
Cell Systems. Cell Press. https://doi.org/10.1016/j.cels.2017.03.001
chicago: Mitosch, Karin, Georg Rieckh, and Mark Tobias Bollenbach. “Noisy Response
to Antibiotic Stress Predicts Subsequent Single Cell Survival in an Acidic Environment.”
Cell Systems. Cell Press, 2017. https://doi.org/10.1016/j.cels.2017.03.001.
ieee: K. Mitosch, G. Rieckh, and M. T. Bollenbach, “Noisy response to antibiotic
stress predicts subsequent single cell survival in an acidic environment,” Cell
Systems, vol. 4, no. 4. Cell Press, pp. 393–403, 2017.
ista: Mitosch K, Rieckh G, Bollenbach MT. 2017. Noisy response to antibiotic stress
predicts subsequent single cell survival in an acidic environment. Cell Systems.
4(4), 393–403.
mla: Mitosch, Karin, et al. “Noisy Response to Antibiotic Stress Predicts Subsequent
Single Cell Survival in an Acidic Environment.” Cell Systems, vol. 4, no.
4, Cell Press, 2017, pp. 393–403, doi:10.1016/j.cels.2017.03.001.
short: K. Mitosch, G. Rieckh, M.T. Bollenbach, Cell Systems 4 (2017) 393–403.
date_created: 2018-12-11T11:47:48Z
date_published: 2017-04-26T00:00:00Z
date_updated: 2023-09-07T12:00:25Z
day: '26'
ddc:
- '576'
- '610'
department:
- _id: ToBo
- _id: GaTk
doi: 10.1016/j.cels.2017.03.001
ec_funded: 1
file:
- access_level: open_access
checksum: 04ff20011c3d9a601c514aa999a5fe1a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:54Z
date_updated: 2020-07-14T12:47:35Z
file_id: '5041'
file_name: IST-2017-901-v1+1_1-s2.0-S2405471217300868-main.pdf
file_size: 2438660
relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '04'
oa: 1
oa_version: Published Version
page: 393 - 403
project:
- _id: 25E83C2C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '303507'
name: Optimality principles in responses to antibiotics
- _id: 25E9AF9E-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P27201-B22
name: Revealing the mechanisms underlying drug interactions
- _id: 25EB3A80-B435-11E9-9278-68D0E5697425
grant_number: RGP0042/2013
name: Revealing the fundamental limits of cell growth
publication: Cell Systems
publication_identifier:
issn:
- '24054712'
publication_status: published
publisher: Cell Press
publist_id: '7061'
pubrep_id: '901'
quality_controlled: '1'
related_material:
record:
- id: '818'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Noisy response to antibiotic stress predicts subsequent single cell survival
in an acidic environment
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2017'
...
---
_id: '821'
abstract:
- lang: eng
text: "This dissertation focuses on algorithmic aspects of program verification,
and presents modeling and complexity advances on several problems related to the\r\nstatic
analysis of programs, the stateless model checking of concurrent programs, and
the competitive analysis of real-time scheduling algorithms.\r\nOur contributions
can be broadly grouped into five categories.\r\n\r\nOur first contribution is
a set of new algorithms and data structures for the quantitative and data-flow
analysis of programs, based on the graph-theoretic notion of treewidth.\r\nIt
has been observed that the control-flow graphs of typical programs have special
structure, and are characterized as graphs of small treewidth.\r\nWe utilize this
structural property to provide faster algorithms for the quantitative and data-flow
analysis of recursive and concurrent programs.\r\nIn most cases we make an algebraic
treatment of the considered problem,\r\nwhere several interesting analyses, such
as the reachability, shortest path, and certain kind of data-flow analysis problems
follow as special cases. \r\nWe exploit the constant-treewidth property to obtain
algorithmic improvements for on-demand versions of the problems, \r\nand provide
data structures with various tradeoffs between the resources spent in the preprocessing
and querying phase.\r\nWe also improve on the algorithmic complexity of quantitative
problems outside the algebraic path framework,\r\nnamely of the minimum mean-payoff,
minimum ratio, and minimum initial credit for energy problems.\r\n\r\n\r\nOur
second contribution is a set of algorithms for Dyck reachability with applications
to data-dependence analysis and alias analysis.\r\nIn particular, we develop an
optimal algorithm for Dyck reachability on bidirected graphs, which are ubiquitous
in context-insensitive, field-sensitive points-to analysis.\r\nAdditionally, we
develop an efficient algorithm for context-sensitive data-dependence analysis
via Dyck reachability,\r\nwhere the task is to obtain analysis summaries of library
code in the presence of callbacks.\r\nOur algorithm preprocesses libraries in
almost linear time, after which the contribution of the library in the complexity
of the client analysis is (i)~linear in the number of call sites and (ii)~only
logarithmic in the size of the whole library, as opposed to linear in the size
of the whole library.\r\nFinally, we prove that Dyck reachability is Boolean Matrix
Multiplication-hard in general, and the hardness also holds for graphs of constant
treewidth.\r\nThis hardness result strongly indicates that there exist no combinatorial
algorithms for Dyck reachability with truly subcubic complexity.\r\n\r\n\r\nOur
third contribution is the formalization and algorithmic treatment of the Quantitative
Interprocedural Analysis framework.\r\nIn this framework, the transitions of a
recursive program are annotated as good, bad or neutral, and receive a weight
which measures\r\nthe magnitude of their respective effect.\r\nThe Quantitative
Interprocedural Analysis problem asks to determine whether there exists an infinite
run of the program where the long-run ratio of the bad weights over the good weights
is above a given threshold.\r\nWe illustrate how several quantitative problems
related to static analysis of recursive programs can be instantiated in this framework,\r\nand
present some case studies to this direction.\r\n\r\n\r\nOur fourth contribution
is a new dynamic partial-order reduction for the stateless model checking of concurrent
programs. Traditional approaches rely on the standard Mazurkiewicz equivalence
between traces, by means of partitioning the trace space into equivalence classes,
and attempting to explore a few representatives from each class.\r\nWe present
a new dynamic partial-order reduction method called the Data-centric Partial
Order Reduction (DC-DPOR).\r\nOur algorithm is based on a new equivalence between
traces, called the observation equivalence.\r\nDC-DPOR explores a coarser partitioning
of the trace space than any exploration method based on the standard Mazurkiewicz
equivalence.\r\nDepending on the program, the new partitioning can be even exponentially
coarser.\r\nAdditionally, DC-DPOR spends only polynomial time in each explored
class.\r\n\r\n\r\nOur fifth contribution is the use of automata and game-theoretic
verification techniques in the competitive analysis and synthesis of real-time
scheduling algorithms for firm-deadline tasks.\r\nOn the analysis side, we leverage
automata on infinite words to compute the competitive ratio of real-time schedulers
subject to various environmental constraints.\r\nOn the synthesis side, we introduce
a new instance of two-player mean-payoff partial-information games, and show\r\nhow
the synthesis of an optimal real-time scheduler can be reduced to computing winning
strategies in this new type of games."
acknowledgement: "First, I am thankful to my advisor, Krishnendu Chatterjee, for offering
me the opportunity to\r\nmaterialize my scientific curiosity in a remarkably wide
range of interesting topics, as well as for his constant availability and continuous
support throughout my doctoral studies. I have had the privilege of collaborating
with, discussing and getting inspired by all members of my committee: Thomas A.
Henzinger, Ulrich Schmid and Martin A. Nowak. The role of the above four people
has been very instrumental both to the research carried out for this dissertation,
and to the researcher I evolved to in the process.\r\nI have greatly enjoyed my
numerous brainstorming sessions with Rasmus Ibsen-Jensen, many\r\nof which led to
results on low-treewidth graphs presented here. I thank Alex Kößler for our\r\ndiscussions
on modeling and analyzing real-time scheduling algorithms, Yaron Velner for our\r\ncollaboration
on the Quantitative Interprocedural Analysis framework, and Nishant Sinha for our
initial discussions on partial order reduction techniques in stateless model checking.
I also thank Jan Otop, Ben Adlam, Bernhard Kragl and Josef Tkadlec for our fruitful
collaborations on\r\ntopics outside the scope of this dissertation, as well as the
interns Prateesh Goyal, Amir Kafshdar Goharshady, Samarth Mishra, Bhavya Choudhary
and Marek Chalupa, with whom I have shared my excitement on various research topics.
Together with my collaborators, I thank officemates and members of the Chatterjee
and Henzinger groups throughout the years, Thorsten Tarrach, Ventsi Chonev, Roopsha
Samanta, Przemek Daca, Mirco Giacobbe, Tanja Petrov, Ashutosh\r\nGupta, Arjun Radhakrishna,
\ Petr Novontý, Christian Hilbe, Jakob Ruess, Martin Chmelik,\r\nCezara Dragoi,
Johannes Reiter, Andrey Kupriyanov, Guy Avni, Sasha Rubin, Jessica Davies, Hongfei
Fu, Thomas Ferrère, Pavol Cerný, Ali Sezgin, Jan Kretínský, Sergiy Bogomolov, Hui\r\nKong,
Benjamin Aminof, Duc-Hiep Chu, and Damien Zufferey. Besides collaborations and
office spaces, with many of the above people I have been fortunate to share numerous
whiteboard\r\ndiscussions, as well as memorable long walks and amicable meals accompanied
by stimulating\r\nconversations. I am highly indebted to Elisabeth Hacker for her
continuous assistance in matters\r\nthat often exceeded her official duties, and
who made my integration in Austria a smooth process."
alternative_title:
- ISTA Thesis
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
citation:
ama: Pavlogiannis A. Algorithmic advances in program analysis and their applications.
2017. doi:10.15479/AT:ISTA:th_854
apa: Pavlogiannis, A. (2017). Algorithmic advances in program analysis and their
applications. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_854
chicago: Pavlogiannis, Andreas. “Algorithmic Advances in Program Analysis and Their
Applications.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_854.
ieee: A. Pavlogiannis, “Algorithmic advances in program analysis and their applications,”
Institute of Science and Technology Austria, 2017.
ista: Pavlogiannis A. 2017. Algorithmic advances in program analysis and their applications.
Institute of Science and Technology Austria.
mla: Pavlogiannis, Andreas. Algorithmic Advances in Program Analysis and Their
Applications. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_854.
short: A. Pavlogiannis, Algorithmic Advances in Program Analysis and Their Applications,
Institute of Science and Technology Austria, 2017.
date_created: 2018-12-11T11:48:41Z
date_published: 2017-08-09T00:00:00Z
date_updated: 2023-09-07T12:01:59Z
day: '09'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: KrCh
doi: 10.15479/AT:ISTA:th_854
ec_funded: 1
file:
- access_level: open_access
checksum: 3a3ec003f6ee73f41f82a544d63dfc77
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:44Z
date_updated: 2020-07-14T12:48:10Z
file_id: '4900'
file_name: IST-2017-854-v1+1_Pavlogiannis_Thesis_PubRep.pdf
file_size: 4103115
relation: main_file
- access_level: closed
checksum: bd2facc45ff8a2e20c5ed313c2ccaa83
content_type: application/zip
creator: dernst
date_created: 2019-04-05T07:59:31Z
date_updated: 2020-07-14T12:48:10Z
file_id: '6201'
file_name: 2017_thesis_Pavlogiannis.zip
file_size: 14744374
relation: source_file
file_date_updated: 2020-07-14T12:48:10Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '08'
oa: 1
oa_version: Published Version
page: '418'
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_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6828'
pubrep_id: '854'
related_material:
record:
- id: '1071'
relation: part_of_dissertation
status: public
- id: '1437'
relation: part_of_dissertation
status: public
- id: '1602'
relation: part_of_dissertation
status: public
- id: '1604'
relation: part_of_dissertation
status: public
- id: '1607'
relation: part_of_dissertation
status: public
- id: '1714'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
title: Algorithmic advances in program analysis and their applications
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '820'
abstract:
- lang: eng
text: "The lac operon is a classic model system for bacterial gene regulation, and
has been studied extensively in E. coli, a classic model organism. However, not
much is known about E. coli’s ecology and life outside the laboratory, in particular
in soil and water environments. The natural diversity of the lac operon outside
the laboratory, its role in the ecology of E. coli and the selection pressures
it is exposed to, are similarly unknown.\r\nIn Chapter Two of this thesis, I explore
the genetic diversity, phylogenetic history and signatures of selection of the
lac operon across 20 natural isolates of E. coli and divergent clades of Escherichia.
I found that complete lac operons were present in all isolates examined, which
in all but one case were functional. The lac operon phylogeny conformed to the
whole-genome phylogeny of the divergent Escherichia clades, which excludes horizontal
gene transfer as an explanation for the presence of functional lac operons in
these clades. All lac operon genes showed a signature of purifying selection;
this signature was strongest for the lacY gene. Lac operon genes of human and
environmental isolates showed similar signatures of selection, except the lacZ
gene, which showed a stronger signature of selection in environmental isolates.\r\nIn
Chapter Three, I try to identify the natural genetic variation relevant for phenotype
and fitness in the lac operon, comparing growth rate on lactose and LacZ activity
of the lac operons of these wild isolates in a common genetic background. Sequence
variation in the lac promoter region, upstream of the -10 and -35 RNA polymerase
binding motif, predicted variation in LacZ activity at full induction, using a
thermodynamic model of polymerase binding (Tugrul, 2016). However, neither variation
in LacZ activity, nor RNA polymerase binding predicted by the model correlated
with variation in growth rate. Lac operons of human and environmental isolates
did not differ systematically in either growth rate on lactose or LacZ protein
activity, suggesting that these lac operons have been exposed to similar selection
pressures. We thus have no evidence that the phenotypic variation we measured
is relevant for fitness.\r\nTo start assessing the effect of genomic background
on the growth phenotype conferred by the lac operon, I compared growth on minimal
medium with lactose between lac operon constructs and the corresponding original
isolates, I found that maximal growth rate was determined by genomic background,
with almost all backgrounds conferring higher growth rates than lab strain K12
MG1655. However, I found no evidence that the lactose concentration at which growth
was half maximal depended on genomic background."
acknowledgement: "ERC H2020 programme (grant agreement no. 648440)\r\nThanks to Jon
Bollback for giving me the chance to do this work, for sharing the ideas that lay
at the basis of this work, for his honesty and openness, showing himself to me as
a person and not just as a boss. Thanks to Nick Barton for his guidance at the last
stage, reading and commenting extensively on several versions of this manuscript,
and for his encouragement; thanks to both Jon and Nick for their kindness and patience.
Thanks to Erik van Nimwegen and Calin Guet for their time and willingness to be
in my thesis committee, and to Erik van Nimwegen especially for agreeing to enter
my thesis committee at the last moment, and for his very sharp, helpful and relevant
comments during and after the defense. Thanks to my collaborators and discussion
partners: Anne Kupczok, for her guidance, ideas and discussions during the construction
of the manuscript of Chapter Two, and her comments on the manuscript; Georg Rieckh
for making me aware of the issue of parameter identifiability, suggesting how to
solve it, and for his unfortunate idea to start the plasmid enterprise in the first
place; Murat Tugrul for sharing his model, for his enthusiasm, and his comments
on Chapter Three; Srdjan Sarikas for his collaboration on the Monod model fitting,
fast forwarding the analysis to turbo speed and making beautiful figures, and making
the discussion fun on top of it all; Vanessa Barone for her last minute comments,
especially on Chapter Three, providing a sharp and very helpful experimentalist
perspective at the last moment; Maros Pleska and Marjon de Vos for their comments
on the manuscript of Chapter Two; Gasper Tkacik for his crucial input on the relation
between growth rate and lactose concentration; Bor Kavcic for his input on growth
rate modeling and error propagation. Thanks to the Bollback, Bollenbach, Barton,
Guet and Tkacik group members for both pro- viding an inspiring and supportive scientific
environment to work in, as well as a lot of warmth and colour to everyday life.
And thanks to the friends I found here, to the people who were there for me and
to the people who changed my life, making it stranger and more beautiful than I
could have imagined, Maros, Vanessa, Tade, Suzi, Andrej, Peter, Tiago, Kristof,
Karin, Irene, Misha, Mato, Guillaume and Zanin. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Fabienne
full_name: Jesse, Fabienne
id: 4C8C26A4-F248-11E8-B48F-1D18A9856A87
last_name: Jesse
citation:
ama: Jesse F. The lac operon in the wild. 2017. doi:10.15479/AT:ISTA:th_857
apa: Jesse, F. (2017). The lac operon in the wild. Institute of Science and
Technology Austria. https://doi.org/10.15479/AT:ISTA:th_857
chicago: Jesse, Fabienne. “The Lac Operon in the Wild.” Institute of Science and
Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_857.
ieee: F. Jesse, “The lac operon in the wild,” Institute of Science and Technology
Austria, 2017.
ista: Jesse F. 2017. The lac operon in the wild. Institute of Science and Technology
Austria.
mla: Jesse, Fabienne. The Lac Operon in the Wild. Institute of Science and
Technology Austria, 2017, doi:10.15479/AT:ISTA:th_857.
short: F. Jesse, The Lac Operon in the Wild, Institute of Science and Technology
Austria, 2017.
date_created: 2018-12-11T11:48:41Z
date_published: 2017-08-25T00:00:00Z
date_updated: 2023-09-07T12:01:21Z
day: '25'
ddc:
- '576'
- '577'
- '579'
degree_awarded: PhD
department:
- _id: JoBo
doi: 10.15479/AT:ISTA:th_857
ec_funded: 1
file:
- access_level: open_access
checksum: c62257a7bff0c5f39e1abffc6bfcca5c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:00Z
date_updated: 2020-07-14T12:48:10Z
file_id: '5252'
file_name: IST-2017-857-v1+1_thesis_fabienne.pdf
file_size: 3417773
relation: main_file
- access_level: closed
checksum: fc87d7d72fce52824a3ae7dcad0413a8
content_type: application/x-tex
creator: dernst
date_created: 2019-04-05T08:51:59Z
date_updated: 2020-07-14T12:48:10Z
file_id: '6212'
file_name: 2017_thesis_Jesse_source.tex
file_size: 215899
relation: source_file
file_date_updated: 2020-07-14T12:48:10Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '87'
project:
- _id: 2578D616-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '648440'
name: Selective Barriers to Horizontal Gene Transfer
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6829'
pubrep_id: '857'
status: public
supervisor:
- first_name: Jonathan P
full_name: Bollback, Jonathan P
id: 2C6FA9CC-F248-11E8-B48F-1D18A9856A87
last_name: Bollback
orcid: 0000-0002-4624-4612
title: The lac operon in the wild
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: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '838'
abstract:
- lang: eng
text: 'In this thesis we discuss the exact security of message authentications codes
HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length
keyed hash function f into a variable input-length function. A practical single-key
variant of NMAC called HMAC is a very popular and widely deployed message authentication
code (MAC). PMAC is a block-cipher based mode of operation, which also happens
to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti
and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF),
and thus also a MAC, under two assumptions. Unfortunately, for many instantiations
of HMAC one of them has been found to be wrong. To restore the provable guarantees
for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC
was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a
pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure
variable input-length PRF. For adversaries making q queries, each of length at
most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves
an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently
best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by
giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one
initially XORs a mask to every message block, where the mask for the i th block
is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is
the i -th codeword of the Gray code. Our attack applies more generally to any
sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As
for NMAC , our first contribution is a simpler and uniform proof: If f is an ε
-secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q
queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length
at most ` blocks each. We also show that this ε + `qδ bound is basically tight
by constructing an f for which an attack with advantage `qδ exists. Moreover,
we analyze the PRF-security of a modification of NMAC called NI by An and Bellare
that avoids the constant rekeying on multi-block messages in NMAC and allows for
an information-theoretic analysis. We carry out such an analysis, obtaining a
tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2
q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved
by using τ i ’s that are k -wise independent, for k > 1 (the original has k
= 1). We observe that the security of PMAC will not increase in general if k =
2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4.
Due to simple extension attacks, this is the best bound one can hope for, using
any distribution on the masks. Whether k = 3 is already sufficient to get this
level of security is left as an open problem. Keywords: Message authentication
codes, Pseudorandom functions, HMAC, PMAC. '
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: Rybar M. (The exact security of) Message authentication codes. 2017. doi:10.15479/AT:ISTA:th_828
apa: Rybar, M. (2017). (The exact security of) Message authentication codes.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_828
chicago: Rybar, Michal. “(The Exact Security of) Message Authentication Codes.”
Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_828.
ieee: M. Rybar, “(The exact security of) Message authentication codes,” Institute
of Science and Technology Austria, 2017.
ista: Rybar M. 2017. (The exact security of) Message authentication codes. Institute
of Science and Technology Austria.
mla: Rybar, Michal. (The Exact Security of) Message Authentication Codes.
Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_828.
short: M. Rybar, (The Exact Security of) Message Authentication Codes, Institute
of Science and Technology Austria, 2017.
date_created: 2018-12-11T11:48:46Z
date_published: 2017-06-26T00:00:00Z
date_updated: 2023-09-07T12:02:28Z
day: '26'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: KrPi
doi: 10.15479/AT:ISTA:th_828
file:
- access_level: open_access
checksum: ff8639ec4bded6186f44c7bd3ee26804
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:13Z
date_updated: 2020-07-14T12:48:12Z
file_id: '4799'
file_name: IST-2017-828-v1+3_2017_Rybar_thesis.pdf
file_size: 847400
relation: main_file
- access_level: closed
checksum: 3462101745ce8ad199c2d0f75dae4a7e
content_type: application/zip
creator: dernst
date_created: 2019-04-05T08:24:11Z
date_updated: 2020-07-14T12:48:12Z
file_id: '6202'
file_name: 2017_Thesis_Rybar_source.zip
file_size: 26054879
relation: source_file
file_date_updated: 2020-07-14T12:48:12Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '86'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6810'
pubrep_id: '828'
related_material:
record:
- id: '2082'
relation: part_of_dissertation
status: public
- id: '6196'
relation: part_of_dissertation
status: public
status: public
title: (The exact security of) Message authentication codes
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '6196'
abstract:
- lang: eng
text: PMAC is a simple and parallel block-cipher mode of operation, which was introduced
by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random
permutation over n-bit strings, PMAC constitutes a provably secure variable input-length
(pseudo)random function. For adversaries making q queries, each of length at most
l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an
upper bound on the distinguishing advantage of Ο(σ2/2n), while the currently
best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving
an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs
a mask to every message block, where the mask for the ith block is computed as
τi := γi·L, where L is a (secret) random value, and γi is the i-th codeword of
the Gray code. Our attack applies more generally to any sequence of γi’s which
contains a large coset of a subgroup of GF(2n). We then investigate if the security
of PMAC can be further improved by using τi’s that are k-wise independent, for
k > 1 (the original distribution is only 1-wise independent). We observe that
the security of PMAC will not increase in general, even if the masks are chosen
from a 2-wise independent distribution, and then prove that the security increases
to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks,
this is the best bound one can hope for, using any distribution on the masks.
Whether 3-wise independence is already sufficient to get this level of security
is left as an open problem.
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- 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: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. IACR Transactions
on Symmetric Cryptology. 2017;2016(2):145-161. doi:10.13154/TOSC.V2016.I2.145-161
apa: Gazi, P., Pietrzak, K. Z., & Rybar, M. (2017). The exact security of PMAC.
IACR Transactions on Symmetric Cryptology. Ruhr University Bochum. https://doi.org/10.13154/TOSC.V2016.I2.145-161
chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security
of PMAC.” IACR Transactions on Symmetric Cryptology. Ruhr University Bochum,
2017. https://doi.org/10.13154/TOSC.V2016.I2.145-161.
ieee: P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” IACR
Transactions on Symmetric Cryptology, vol. 2016, no. 2. Ruhr University Bochum,
pp. 145–161, 2017.
ista: Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions
on Symmetric Cryptology. 2016(2), 145–161.
mla: Gazi, Peter, et al. “The Exact Security of PMAC.” IACR Transactions on Symmetric
Cryptology, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:10.13154/TOSC.V2016.I2.145-161.
short: P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology
2016 (2017) 145–161.
date_created: 2019-04-04T13:48:23Z
date_published: 2017-02-03T00:00:00Z
date_updated: 2023-09-07T12:02:27Z
day: '03'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.13154/TOSC.V2016.I2.145-161
ec_funded: 1
file:
- access_level: open_access
checksum: f23161d685dd957ae8d7274132999684
content_type: application/pdf
creator: dernst
date_created: 2019-04-04T13:53:58Z
date_updated: 2020-07-14T12:47:24Z
file_id: '6197'
file_name: 2017_IACR_Gazi.pdf
file_size: 597335
relation: main_file
file_date_updated: 2020-07-14T12:47:24Z
has_accepted_license: '1'
intvolume: ' 2016'
issue: '2'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 145-161
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: IACR Transactions on Symmetric Cryptology
publication_identifier:
eissn:
- 2519-173X
publication_status: published
publisher: Ruhr University Bochum
quality_controlled: '1'
related_material:
record:
- id: '838'
relation: dissertation_contains
status: public
status: public
title: The exact security of PMAC
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 2016
year: '2017'
...
---
_id: '837'
abstract:
- lang: eng
text: 'The hippocampus is a key brain region for memory and notably for spatial
memory, and is needed for both spatial working and reference memories. Hippocampal
place cells selectively discharge in specific locations of the environment to
form mnemonic represen tations of space. Several behavioral protocols have been
designed to test spatial memory which requires the experimental subject to utilize
working memory and reference memory. However, less is known about how these memory
traces are presented in the hippo campus, especially considering tasks that require
both spatial working and long -term reference memory demand. The aim of my thesis
was to elucidate how spatial working memory, reference memory, and the combination
of both are represented in the hippocampus. In this thesis, using a radial eight
-arm maze, I examined how the combined demand on these memories influenced place
cell assemblies while reference memories were partially updated by changing some
of the reward- arms. This was contrasted with task varian ts requiring working
or reference memories only. Reference memory update led to gradual place field
shifts towards the rewards on the switched arms. Cells developed enhanced firing
in passes between newly -rewarded arms as compared to those containing an unchanged
reward. The working memory task did not show such gradual changes. Place assemblies
on occasions replayed trajectories of the maze; at decision points the next arm
choice was preferentially replayed in tasks needing reference memory while in
the pure working memory task the previously visited arm was replayed. Hence trajectory
replay only reflected the decision of the animal in tasks needing reference memory
update. At the reward locations, in all three tasks outbound trajectories of the
current arm were preferentially replayed, showing the animals’ next path to the
center. At reward locations trajectories were replayed preferentially in reverse
temporal order. Moreover, in the center reverse replay was seen in the working
memory task but in the other tasks forward replay was seen. Hence, the direction
of reactivation was determined by the goal locations so that part of the trajectory
which was closer to the goal was reactivated later in an HSE while places further
away from the goal were reactivated earlier. Altogether my work demonstrated that
reference memory update triggers several levels of reorganization of the hippocampal
cognitive map which are not seen in simpler working memory demand s. Moreover,
hippocampus is likely to be involved in spatial decisions through reactivating
planned trajectories when reference memory recall is required for such a decision. '
acknowledgement: 'I am very grateful for the opportunity I have had as a graduate
student to explore and incredibly interesting branch of neuroscience, and for the
people who made it possible. Firstly, I would like to offer my thanks to my supervisor
Professor Jozsef Csicsvari for his great support, guidance and patience offered
over the years. The door to his office was always open whenever I had questions.
I have learned a lot from him about carefully designing experiments, asking interesting
questions and how to integrate results into a broader picture. I also express my
gratitude to the remarkable post- doc , Dr. Joseph O’Neill. He is a gre at scientific
role model who is always willing to teach , and advice and talk through problems
with his full attention. Many thanks to my wonderful “office mates” over the years
and their support and encouragement, Alice Avernhe, Philipp Schönenberger, Desiree
Dickerson, Karel Blahna, Charlotte Boccara, Igor Gridchyn, Peter Baracskay, Krisztián
Kovács, Dámaris Rangel, Karola Käfer and Federico Stella. They were the ones in
the lab for the many useful discussions about science and for making the laboratory
such a nice and friendly place to work in. A special thank goes to Michael LoBianco
and Jago Wallenschus for wonderful technical support. I would also like to thank
Professor Peter Jonas and Professor David M Bannerman for being my qualifying exam
and thesi s committee members despite their busy schedule. I am also very thankful
to IST Austria for their support all throughout my PhD. '
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Haibing
full_name: Xu, Haibing
id: 310349D0-F248-11E8-B48F-1D18A9856A87
last_name: Xu
citation:
ama: Xu H. Reactivation of the hippocampal cognitive map in goal-directed spatial
tasks. 2017. doi:10.15479/AT:ISTA:th_858
apa: Xu, H. (2017). Reactivation of the hippocampal cognitive map in goal-directed
spatial tasks. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_858
chicago: Xu, Haibing. “Reactivation of the Hippocampal Cognitive Map in Goal-Directed
Spatial Tasks.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_858.
ieee: H. Xu, “Reactivation of the hippocampal cognitive map in goal-directed spatial
tasks,” Institute of Science and Technology Austria, 2017.
ista: Xu H. 2017. Reactivation of the hippocampal cognitive map in goal-directed
spatial tasks. Institute of Science and Technology Austria.
mla: Xu, Haibing. Reactivation of the Hippocampal Cognitive Map in Goal-Directed
Spatial Tasks. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_858.
short: H. Xu, Reactivation of the Hippocampal Cognitive Map in Goal-Directed Spatial
Tasks, Institute of Science and Technology Austria, 2017.
date_created: 2018-12-11T11:48:46Z
date_published: 2017-08-23T00:00:00Z
date_updated: 2023-09-07T12:06:38Z
day: '23'
ddc:
- '571'
degree_awarded: PhD
department:
- _id: JoCs
doi: 10.15479/AT:ISTA:th_858
file:
- access_level: closed
checksum: f11925fbbce31e495124b6bc4f10573c
content_type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
creator: dernst
date_created: 2019-04-05T08:59:51Z
date_updated: 2020-07-14T12:48:12Z
file_id: '6213'
file_name: 2017_Xu_Haibing_Thesis_Source.docx
file_size: 3589490
relation: source_file
- access_level: open_access
checksum: ffb10749a537d615fab1ef0937ccb157
content_type: application/pdf
creator: dernst
date_created: 2019-04-05T08:59:51Z
date_updated: 2020-07-14T12:48:12Z
file_id: '6214'
file_name: 2017_Xu_Thesis_IST.pdf
file_size: 11668613
relation: main_file
file_date_updated: 2020-07-14T12:48:12Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '93'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6811'
pubrep_id: '858'
related_material:
record:
- id: '5828'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Jozsef L
full_name: Csicsvari, Jozsef L
id: 3FA14672-F248-11E8-B48F-1D18A9856A87
last_name: Csicsvari
orcid: 0000-0002-5193-4036
title: Reactivation of the hippocampal cognitive map in goal-directed spatial tasks
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: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '938'
abstract:
- lang: eng
text: The thesis encompasses several topics of plant cell biology which were studied
in the model plant Arabidopsis thaliana. Chapter 1 concerns the plant hormone
auxin and its polar transport through cells and tissues. The highly controlled,
directional transport of auxin is facilitated by plasma membrane-localized transporters.
Transporters from the PIN family direct auxin transport due to their polarized
localizations at cell membranes. Substantial effort has been put into research
on cellular trafficking of PIN proteins, which is thought to underlie their polar
distribution. I participated in a forward genetic screen aimed at identifying
novel regulators of PIN polarity. The screen yielded several genes which may be
involved in PIN polarity regulation or participate in polar auxin transport by
other means. Chapter 2 focuses on the endomembrane system, with particular attention
to clathrin-mediated endocytosis. The project started with identification of several
proteins that interact with clathrin light chains. Among them, I focused on two
putative homologues of auxilin, which in non-plant systems is an endocytotic factor
known for uncoating clathrin-coated vesicles in the final step of endocytosis.
The body of my work consisted of an in-depth characterization of transgenic A.
thaliana lines overexpressing these putative auxilins in an inducible manner.
Overexpression of these proteins leads to an inhibition of endocytosis, as documented
by imaging of cargoes and clathrin-related endocytic machinery. An extension of
this work is an investigation into a concept of homeostatic regulation acting
between distinct transport processes in the endomembrane system. With auxilin
overexpressing lines, where endocytosis is blocked specifically, I made observations
on the mutual relationship between two opposite trafficking processes of secretion
and endocytosis. In Chapter 3, I analyze cortical microtubule arrays and their
relationship to auxin signaling and polarized growth in elongating cells. In plants,
microtubules are organized into arrays just below the plasma membrane, and it
is thought that their function is to guide membrane-docked cellulose synthase
complexes. These, in turn, influence cell wall structure and cell shape by directed
deposition of cellulose fibres. In elongating cells, cortical microtubule arrays
are able to reorient in relation to long cell axis, and these reorientations have
been linked to cell growth and to signaling of growth-regulating factors such
as auxin or light. In this chapter, I am addressing the causal relationship between
microtubule array reorientation, growth, and auxin signaling. I arrive at a model
where array reorientation is not guided by auxin directly, but instead is only
controlled by growth, which, in turn, is regulated by auxin.
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Maciek
full_name: Adamowski, Maciek
id: 45F536D2-F248-11E8-B48F-1D18A9856A87
last_name: Adamowski
orcid: 0000-0001-6463-5257
citation:
ama: Adamowski M. Investigations into cell polarity and trafficking in the plant
model Arabidopsis thaliana . 2017. doi:10.15479/AT:ISTA:th_842
apa: Adamowski, M. (2017). Investigations into cell polarity and trafficking
in the plant model Arabidopsis thaliana . Institute of Science and Technology
Austria. https://doi.org/10.15479/AT:ISTA:th_842
chicago: Adamowski, Maciek. “Investigations into Cell Polarity and Trafficking in
the Plant Model Arabidopsis Thaliana .” Institute of Science and Technology Austria,
2017. https://doi.org/10.15479/AT:ISTA:th_842.
ieee: M. Adamowski, “Investigations into cell polarity and trafficking in the plant
model Arabidopsis thaliana ,” Institute of Science and Technology Austria, 2017.
ista: Adamowski M. 2017. Investigations into cell polarity and trafficking in the
plant model Arabidopsis thaliana . Institute of Science and Technology Austria.
mla: Adamowski, Maciek. Investigations into Cell Polarity and Trafficking in
the Plant Model Arabidopsis Thaliana . Institute of Science and Technology
Austria, 2017, doi:10.15479/AT:ISTA:th_842.
short: M. Adamowski, Investigations into Cell Polarity and Trafficking in the Plant
Model Arabidopsis Thaliana , Institute of Science and Technology Austria, 2017.
date_created: 2018-12-11T11:49:18Z
date_published: 2017-06-02T00:00:00Z
date_updated: 2023-09-07T12:06:09Z
day: '02'
ddc:
- '581'
- '583'
- '580'
degree_awarded: PhD
department:
- _id: JiFr
doi: 10.15479/AT:ISTA:th_842
file:
- access_level: closed
checksum: 193425764d9aaaed3ac57062a867b315
content_type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
creator: dernst
date_created: 2019-04-05T09:03:20Z
date_updated: 2020-07-14T12:48:15Z
file_id: '6215'
file_name: 2017_Adamowski-Thesis_Source.docx
file_size: 46903863
relation: source_file
- access_level: open_access
checksum: df5ab01be81f821e1b958596a1ec8d21
content_type: application/pdf
creator: dernst
date_created: 2019-04-05T09:03:19Z
date_updated: 2020-07-14T12:48:15Z
file_id: '6216'
file_name: 2017_Adamowski-Thesis.pdf
file_size: 8698888
relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '117'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6483'
pubrep_id: '842'
related_material:
record:
- id: '1591'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Jiří
full_name: Friml, Jiří
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
title: 'Investigations into cell polarity and trafficking in the plant model Arabidopsis
thaliana '
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '992'
abstract:
- lang: eng
text: "An instance of the Constraint Satisfaction Problem (CSP) is given by a finite
set of\r\nvariables, a finite domain of labels, and a set of constraints, each
constraint acting on\r\na subset of the variables. The goal is to find an assignment
of labels to its variables\r\nthat satisfies all constraints (or decide whether
one exists). If we allow more general\r\n“soft” constraints, which come with (possibly
infinite) costs of particular assignments,\r\nwe obtain instances from a richer
class called Valued Constraint Satisfaction Problem\r\n(VCSP). There the goal
is to find an assignment with minimum total cost.\r\nIn this thesis, we focus
(assuming that P\r\n6\r\n=\r\nNP) on classifying computational com-\r\nplexity
of CSPs and VCSPs under certain restricting conditions. Two results are the core\r\ncontent
of the work. In one of them, we consider VCSPs parametrized by a constraint\r\nlanguage,
that is the set of “soft” constraints allowed to form the instances, and finish\r\nthe
complexity classification modulo (missing pieces of) complexity classification
for\r\nanalogously parametrized CSP. The other result is a generalization of Edmonds’
perfect\r\nmatching algorithm. This generalization contributes to complexity classfications
in two\r\nways. First, it gives a new (largest known) polynomial-time solvable
class of Boolean\r\nCSPs in which every variable may appear in at most two constraints
and second, it\r\nsettles full classification of Boolean CSPs with planar drawing
(again parametrized by a\r\nconstraint language)."
acknowledgement: FP7/2007-2013/ERC grant agreement no 616160
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Rolinek M. Complexity of constraint satisfaction. 2017. doi:10.15479/AT:ISTA:th_815
apa: Rolinek, M. (2017). Complexity of constraint satisfaction. Institute
of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_815
chicago: Rolinek, Michal. “Complexity of Constraint Satisfaction.” Institute of
Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_815.
ieee: M. Rolinek, “Complexity of constraint satisfaction,” Institute of Science
and Technology Austria, 2017.
ista: Rolinek M. 2017. Complexity of constraint satisfaction. Institute of Science
and Technology Austria.
mla: Rolinek, Michal. Complexity of Constraint Satisfaction. Institute of
Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_815.
short: M. Rolinek, Complexity of Constraint Satisfaction, Institute of Science and
Technology Austria, 2017.
date_created: 2018-12-11T11:49:35Z
date_published: 2017-05-01T00:00:00Z
date_updated: 2023-09-07T12:05:41Z
day: '01'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: VlKo
doi: 10.15479/AT:ISTA:th_815
ec_funded: 1
file:
- access_level: open_access
checksum: 81761fb939acb7585c36629f765b4373
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:55Z
date_updated: 2020-07-14T12:48:18Z
file_id: '4654'
file_name: IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf
file_size: 786145
relation: main_file
- access_level: closed
checksum: 2b2d7e1d6c1c79a9795a7aa0f860baf3
content_type: application/zip
creator: dernst
date_created: 2019-04-05T08:43:24Z
date_updated: 2020-07-14T12:48:18Z
file_id: '6208'
file_name: 2017_Thesis_Rolinek_source.zip
file_size: 5936337
relation: source_file
file_date_updated: 2020-07-14T12:48:18Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '97'
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6407'
pubrep_id: '815'
status: public
supervisor:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
title: Complexity of constraint satisfaction
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '718'
abstract:
- lang: eng
text: Mapping every simplex in the Delaunay mosaic of a discrete point set to the
radius of the smallest empty circumsphere gives a generalized discrete Morse function.
Choosing the points from a Poisson point process in ℝ n , we study the expected
number of simplices in the Delaunay mosaic as well as the expected number of critical
simplices and nonsingular intervals in the corresponding generalized discrete
gradient. Observing connections with other probabilistic models, we obtain precise
expressions for the expected numbers in low dimensions. In particular, we obtain
the expected numbers of simplices in the Poisson–Delaunay mosaic in dimensions
n ≤ 4.
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Anton
full_name: Nikitenko, Anton
id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
last_name: Nikitenko
orcid: 0000-0002-0659-3201
- first_name: Matthias
full_name: Reitzner, Matthias
last_name: Reitzner
citation:
ama: Edelsbrunner H, Nikitenko A, Reitzner M. Expected sizes of poisson Delaunay
mosaics and their discrete Morse functions. Advances in Applied Probability.
2017;49(3):745-767. doi:10.1017/apr.2017.20
apa: Edelsbrunner, H., Nikitenko, A., & Reitzner, M. (2017). Expected sizes
of poisson Delaunay mosaics and their discrete Morse functions. Advances in
Applied Probability. Cambridge University Press. https://doi.org/10.1017/apr.2017.20
chicago: Edelsbrunner, Herbert, Anton Nikitenko, and Matthias Reitzner. “Expected
Sizes of Poisson Delaunay Mosaics and Their Discrete Morse Functions.” Advances
in Applied Probability. Cambridge University Press, 2017. https://doi.org/10.1017/apr.2017.20.
ieee: H. Edelsbrunner, A. Nikitenko, and M. Reitzner, “Expected sizes of poisson
Delaunay mosaics and their discrete Morse functions,” Advances in Applied Probability,
vol. 49, no. 3. Cambridge University Press, pp. 745–767, 2017.
ista: Edelsbrunner H, Nikitenko A, Reitzner M. 2017. Expected sizes of poisson Delaunay
mosaics and their discrete Morse functions. Advances in Applied Probability. 49(3),
745–767.
mla: Edelsbrunner, Herbert, et al. “Expected Sizes of Poisson Delaunay Mosaics and
Their Discrete Morse Functions.” Advances in Applied Probability, vol.
49, no. 3, Cambridge University Press, 2017, pp. 745–67, doi:10.1017/apr.2017.20.
short: H. Edelsbrunner, A. Nikitenko, M. Reitzner, Advances in Applied Probability
49 (2017) 745–767.
date_created: 2018-12-11T11:48:07Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-09-07T12:07:12Z
day: '01'
department:
- _id: HeEd
doi: 10.1017/apr.2017.20
ec_funded: 1
external_id:
arxiv:
- '1607.05915'
intvolume: ' 49'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1607.05915
month: '09'
oa: 1
oa_version: Preprint
page: 745 - 767
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: Advances in Applied Probability
publication_identifier:
issn:
- '00018678'
publication_status: published
publisher: Cambridge University Press
publist_id: '6962'
quality_controlled: '1'
related_material:
record:
- id: '6287'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Expected sizes of poisson Delaunay mosaics and their discrete Morse functions
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 49
year: '2017'
...