@phdthesis{821,
abstract = {This dissertation focuses on algorithmic aspects of program verification, and presents modeling and complexity advances on several problems related to the
static analysis of programs, the stateless model checking of concurrent programs, and the competitive analysis of real-time scheduling algorithms.
Our contributions can be broadly grouped into five categories.
Our 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.
It has been observed that the control-flow graphs of typical programs have special structure, and are characterized as graphs of small treewidth.
We utilize this structural property to provide faster algorithms for the quantitative and data-flow analysis of recursive and concurrent programs.
In most cases we make an algebraic treatment of the considered problem,
where several interesting analyses, such as the reachability, shortest path, and certain kind of data-flow analysis problems follow as special cases.
We exploit the constant-treewidth property to obtain algorithmic improvements for on-demand versions of the problems,
and provide data structures with various tradeoffs between the resources spent in the preprocessing and querying phase.
We also improve on the algorithmic complexity of quantitative problems outside the algebraic path framework,
namely of the minimum mean-payoff, minimum ratio, and minimum initial credit for energy problems.
Our second contribution is a set of algorithms for Dyck reachability with applications to data-dependence analysis and alias analysis.
In particular, we develop an optimal algorithm for Dyck reachability on bidirected graphs, which are ubiquitous in context-insensitive, field-sensitive points-to analysis.
Additionally, we develop an efficient algorithm for context-sensitive data-dependence analysis via Dyck reachability,
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 (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.
Finally, we prove that Dyck reachability is Boolean Matrix Multiplication-hard in general, and the hardness also holds for graphs of constant treewidth.
This hardness result strongly indicates that there exist no combinatorial algorithms for Dyck reachability with truly subcubic complexity.
Our third contribution is the formalization and algorithmic treatment of the Quantitative Interprocedural Analysis framework.
In this framework, the transitions of a recursive program are annotated as good, bad or neutral, and receive a weight which measures
the magnitude of their respective effect.
The 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.
We illustrate how several quantitative problems related to static analysis of recursive programs can be instantiated in this framework,
and present some case studies to this direction.
Our 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.
We present a new dynamic partial-order reduction method called the Data-centric Partial Order Reduction (DC-DPOR).
Our algorithm is based on a new equivalence between traces, called the observation equivalence.
DC-DPOR explores a coarser partitioning of the trace space than any exploration method based on the standard Mazurkiewicz equivalence.
Depending on the program, the new partitioning can be even exponentially coarser.
Additionally, DC-DPOR spends only polynomial time in each explored class.
Our 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.
On the analysis side, we leverage automata on infinite words to compute the competitive ratio of real-time schedulers subject to various environmental constraints.
On the synthesis side, we introduce a new instance of two-player mean-payoff partial-information games, and show
how the synthesis of an optimal real-time scheduler can be reduced to computing winning strategies in this new type of games.},
author = {Pavlogiannis, Andreas},
pages = {418},
publisher = {IST Austria},
title = {{Algorithmic advances in program analysis and their applications}},
doi = {10.15479/AT:ISTA:th_854},
year = {2017},
}
@phdthesis{837,
abstract = {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. },
author = {Xu, Haibing},
pages = {93},
publisher = {IST Austria},
title = {{Reactivation of the hippocampal cognitive map in goal-directed spatial tasks}},
doi = {10.15479/AT:ISTA:th_858},
year = {2017},
}
@phdthesis{839,
abstract = {This thesis describes a brittle fracture simulation method for visual effects applications. Building upon a symmetric Galerkin boundary element method, we first compute stress intensity factors following the theory of linear elastic fracture mechanics. We then use these stress intensities to simulate the motion of a propagating crack front at a significantly higher resolution than the overall deformation of the breaking object. Allowing for spatial variations of the material's toughness during crack propagation produces visually realistic, highly-detailed fracture surfaces. Furthermore, we introduce approximations for stress intensities and crack opening displacements, resulting in both practical speed-up and theoretically superior runtime complexity compared to previous methods. While we choose a quasi-static approach to fracture mechanics, ignoring dynamic deformations, we also couple our fracture simulation framework to a standard rigid-body dynamics solver, enabling visual effects artists to simulate both large scale motion, as well as fracturing due to collision forces in a combined system. As fractures inside of an object grow, their geometry must be represented both in the coarse boundary element mesh, as well as at the desired fine output resolution. Using a boundary element method, we avoid complicated volumetric meshing operations. Instead we describe a simple set of surface meshing operations that allow us to progressively add cracks to the mesh of an object and still re-use all previously computed entries of the linear boundary element system matrix. On the high resolution level, we opt for an implicit surface representation. We then describe how to capture fracture surfaces during crack propagation, as well as separate the individual fragments resulting from the fracture process, based on this implicit representation. We show results obtained with our method, either solving the full boundary element system in every time step, or alternatively using our fast approximations. These results demonstrate that both of these methods perform well in basic test cases and produce realistic fracture surfaces. Furthermore we show that our fast approximations substantially out-perform the standard approach in more demanding scenarios. Finally, these two methods naturally combine, using the full solution while the problem size is manageably small and switching to the fast approximations later on. The resulting hybrid method gives the user a direct way to choose between speed and accuracy of the simulation. },
author = {Hahn, David},
pages = {124},
publisher = {IST Austria},
title = {{Brittle fracture simulation with boundary elements for computer graphics}},
doi = {10.15479/AT:ISTA:th_855},
year = {2017},
}
@phdthesis{6287,
abstract = {The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's.},
author = {Nikitenko, Anton},
pages = {86},
publisher = {IST Austria},
title = {{Discrete Morse theory for random complexes }},
doi = {10.15479/AT:ISTA:th_873},
year = {2017},
}
@phdthesis{838,
abstract = {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. },
author = {Rybar, Michal},
pages = {86},
publisher = {IST Austria},
title = {{(The exact security of) Message authentication codes}},
doi = {10.15479/AT:ISTA:th_828},
year = {2017},
}
@phdthesis{938,
abstract = {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.},
author = {Adamowski, Maciek},
pages = {117},
publisher = {IST Austria},
title = {{Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana }},
doi = {10.15479/AT:ISTA:th_842},
year = {2017},
}
@phdthesis{961,
abstract = {Cell-cell contact formation constitutes the first step in the emergence of multicellularity in evolution, thereby allowing the differentiation of specialized cell types. In metazoan development, cell-cell contact formation is thought to influence cell fate specification, and cell fate specification has been implicated in cell-cell contact formation. However, remarkably little is yet known about whether and how the interaction and feedback between cell-cell contact formation and cell fate specification affect development. Here we identify a positive feedback loop between cell-cell contact duration, morphogen signaling and mesendoderm cell fate specification during zebrafish gastrulation. We show that long lasting cell-cell contacts enhance the competence of prechordal plate (ppl) progenitor cells to respond to Nodal signaling, required for proper ppl cell fate specification. We further show that Nodal signalling romotes ppl cell-cell contact duration, thereby generating an effective positive feedback loop between ppl cell-cell contact duration and cell fate specification. Finally, by using a combination of theoretical modeling and experimentation, we show that this feedback loop determines whether anterior axial mesendoderm cells become ppl progenitors or, instead, turn into endoderm progenitors. Our findings reveal that the gene regulatory networks leading to cell fate diversification within the developing embryo are controlled by the interdependent activities of cell-cell signaling and contact formation.},
author = {Barone, Vanessa},
pages = {109},
publisher = {IST Austria},
title = {{Cell adhesion and cell fate: An effective feedback loop during zebrafish gastrulation}},
doi = {10.15479/AT:ISTA:th_825},
year = {2017},
}
@phdthesis{992,
abstract = {An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of
variables, a finite domain of labels, and a set of constraints, each constraint acting on
a subset of the variables. The goal is to find an assignment of labels to its variables
that satisfies all constraints (or decide whether one exists). If we allow more general
“soft” constraints, which come with (possibly infinite) costs of particular assignments,
we obtain instances from a richer class called Valued Constraint Satisfaction Problem
(VCSP). There the goal is to find an assignment with minimum total cost.
In this thesis, we focus (assuming that P
6
=
NP) on classifying computational com-
plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core
content of the work. In one of them, we consider VCSPs parametrized by a constraint
language, that is the set of “soft” constraints allowed to form the instances, and finish
the complexity classification modulo (missing pieces of) complexity classification for
analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect
matching algorithm. This generalization contributes to complexity classfications in two
ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean
CSPs in which every variable may appear in at most two constraints and second, it
settles full classification of Boolean CSPs with planar drawing (again parametrized by a
constraint language).},
author = {Rolinek, Michal},
pages = {97},
publisher = {IST Austria},
title = {{Complexity of constraint satisfaction}},
doi = {10.15479/AT:ISTA:th_815},
year = {2017},
}
@phdthesis{1121,
abstract = {Horizontal gene transfer (HGT), the lateral acquisition of genes across existing species
boundaries, is a major evolutionary force shaping microbial genomes that facilitates
adaptation to new environments as well as resistance to antimicrobial drugs. As such,
understanding the mechanisms and constraints that determine the outcomes of HGT
events is crucial to understand the dynamics of HGT and to design better strategies to
overcome the challenges that originate from it.
Following the insertion and expression of a newly transferred gene, the success of an
HGT event will depend on the fitness effect it has on the recipient (host) cell. Therefore,
predicting the impact of HGT on the genetic composition of a population critically
depends on the distribution of fitness effects (DFE) of horizontally transferred genes.
However, to date, we have little knowledge of the DFE of newly transferred genes, and
hence little is known about the shape and scale of this distribution.
It is particularly important to better understand the selective barriers that determine
the fitness effects of newly transferred genes. In spite of substantial bioinformatics
efforts to identify horizontally transferred genes and selective barriers, a systematic
experimental approach to elucidate the roles of different selective barriers in defining
the fate of a transfer event has largely been absent. Similarly, although the fact that
environment might alter the fitness effect of a horizontally transferred gene may seem
obvious, little attention has been given to it in a systematic experimental manner.
In this study, we developed a systematic experimental approach that consists of
transferring 44 arbitrarily selected Salmonella typhimurium orthologous genes into an
Escherichia coli host, and estimating the fitness effects of these transferred genes at a
constant expression level by performing competition assays against the wild type.
In chapter 2, we performed one-to-one competition assays between a mutant strain
carrying a transferred gene and the wild type strain. By using flow cytometry we
estimated selection coefficients for the transferred genes with a precision level of 10-3,and obtained the DFE of horizontally transferred genes. We then investigated if these
fitness effects could be predicted by any of the intrinsic properties of the genes, namely,
functional category, degree of complexity (protein-protein interactions), GC content,
codon usage and length. Our analyses revealed that the functional category and length
of the genes act as potential selective barriers. Finally, using the same procedure with
the endogenous E. coli orthologs of these 44 genes, we demonstrated that gene dosage is
the most prominent selective barrier to HGT.
In chapter 3, using the same set of genes we investigated the role of environment on the
success of HGT events. Under six different environments with different levels of stress
we performed more complex competition assays, where we mixed all 44 mutant strains
carrying transferred genes with the wild type strain. To estimate the fitness effects of
genes relative to wild type we used next generation sequencing. We found that the DFEs
of horizontally transferred genes are highly dependent on the environment, with
abundant gene–by-environment interactions. Furthermore, we demonstrated a
relationship between average fitness effect of a gene across all environments and its
environmental variance, and thus its predictability. Finally, in spite of the fitness effects
of genes being highly environment-dependent, we still observed a common shape of
DFEs across all tested environments.},
author = {Acar, Hande},
pages = {75},
publisher = {IST Austria},
title = {{Selective barriers to horizontal gene transfer}},
year = {2016},
}
@phdthesis{1128,
abstract = {The process of gene expression is central to the modern understanding of how cellular systems
function. In this process, a special kind of regulatory proteins, called transcription factors,
are important to determine how much protein is produced from a given gene. As biological
information is transmitted from transcription factor concentration to mRNA levels to amounts of
protein, various sources of noise arise and pose limits to the fidelity of intracellular signaling.
This thesis concerns itself with several aspects of stochastic gene expression: (i) the mathematical
description of complex promoters responsible for the stochastic production of biomolecules,
(ii) fundamental limits to information processing the cell faces due to the interference from multiple
fluctuating signals, (iii) how the presence of gene expression noise influences the evolution
of regulatory sequences, (iv) and tools for the experimental study of origins and consequences
of cell-cell heterogeneity, including an application to bacterial stress response systems.},
author = {Rieckh, Georg},
pages = {114},
publisher = {IST Austria},
title = {{Studying the complexities of transcriptional regulation}},
year = {2016},
}
@phdthesis{1129,
abstract = {Directed cell migration is a hallmark feature, present in almost all multi-cellular
organisms. Despite its importance, basic questions regarding force transduction
or directional sensing are still heavily investigated. Directed migration of cells
guided by immobilized guidance cues - haptotaxis - occurs in key-processes,
such as embryonic development and immunity (Middleton et al., 1997; Nguyen
et al., 2000; Thiery, 1984; Weber et al., 2013). Immobilized guidance cues
comprise adhesive ligands, such as collagen and fibronectin (Barczyk et al.,
2009), or chemokines - the main guidance cues for migratory leukocytes
(Middleton et al., 1997; Weber et al., 2013). While adhesive ligands serve as
attachment sites guiding cell migration (Carter, 1965), chemokines instruct
haptotactic migration by inducing adhesion to adhesive ligands and directional
guidance (Rot and Andrian, 2004; Schumann et al., 2010). Quantitative analysis
of the cellular response to immobilized guidance cues requires in vitro assays
that foster cell migration, offer accurate control of the immobilized cues on a
subcellular scale and in the ideal case closely reproduce in vivo conditions. The
exploration of haptotactic cell migration through design and employment of such
assays represents the main focus of this work.
Dendritic cells (DCs) are leukocytes, which after encountering danger
signals such as pathogens in peripheral organs instruct naïve T-cells and
consequently the adaptive immune response in the lymph node (Mellman and
Steinman, 2001). To reach the lymph node from the periphery, DCs follow
haptotactic gradients of the chemokine CCL21 towards lymphatic vessels
(Weber et al., 2013). Questions about how DCs interpret haptotactic CCL21
gradients have not yet been addressed. The main reason for this is the lack of
an assay that offers diverse haptotactic environments, hence allowing the study
of DC migration as a response to different signals of immobilized guidance cue.
In this work, we developed an in vitro assay that enables us to
quantitatively assess DC haptotaxis, by combining precisely controllable
chemokine photo-patterning with physically confining migration conditions. With this tool at hand, we studied the influence of CCL21 gradient properties and
concentration on DC haptotaxis. We found that haptotactic gradient sensing
depends on the absolute CCL21 concentration in combination with the local
steepness of the gradient. Our analysis suggests that the directionality of
migrating DCs is governed by the signal-to-noise ratio of CCL21 binding to its
receptor CCR7. Moreover, the haptotactic CCL21 gradient formed in vivo
provides an optimal shape for DCs to recognize haptotactic guidance cue.
By reconstitution of the CCL21 gradient in vitro we were also able to
study the influence of CCR7 signal termination on DC haptotaxis. To this end,
we used DCs lacking the G-protein coupled receptor kinase GRK6, which is
responsible for CCL21 induced CCR7 receptor phosphorylation and
desensitization (Zidar et al., 2009). We found that CCR7 desensitization by
GRK6 is crucial for maintenance of haptotactic CCL21 gradient sensing in vitro
and confirm those observations in vivo.
In the context of the organism, immobilized haptotactic guidance cues
often coincide and compete with soluble chemotactic guidance cues. During
wound healing, fibroblasts are exposed and influenced by adhesive cues and
soluble factors at the same time (Wu et al., 2012; Wynn, 2008). Similarly,
migrating DCs are exposed to both, soluble chemokines (CCL19 and truncated
CCL21) inducing chemotactic behavior as well as the immobilized CCL21. To
quantitatively assess these complex coinciding immobilized and soluble
guidance cues, we implemented our chemokine photo-patterning technique in a
microfluidic system allowing for chemotactic gradient generation. To validate
the assay, we observed DC migration in competing CCL19/CCL21
environments.
Adhesiveness guided haptotaxis has been studied intensively over the
last century. However, quantitative studies leading to conceptual models are
largely missing, again due to the lack of a precisely controllable in vitro assay. A
requirement for such an in vitro assay is that it must prevent any uncontrolled
cell adhesion. This can be accomplished by stable passivation of the surface. In
addition, controlled adhesion must be sustainable, quantifiable and dose
dependent in order to create homogenous gradients. Therefore, we developed a novel covalent photo-patterning technique satisfying all these needs. In
combination with a sustainable poly-vinyl alcohol (PVA) surface coating we
were able to generate gradients of adhesive cue to direct cell migration. This
approach allowed us to characterize the haptotactic migratory behavior of
zebrafish keratocytes in vitro. Furthermore, defined patterns of adhesive cue
allowed us to control for cell shape and growth on a subcellular scale.},
author = {Schwarz, Jan},
pages = {178},
publisher = {IST Austria},
title = {{Quantitative analysis of haptotactic cell migration}},
year = {2016},
}
@phdthesis{1126,
abstract = {Traditionally machine learning has been focusing on the problem of solving a single
task in isolation. While being quite well understood, this approach disregards an
important aspect of human learning: when facing a new problem, humans are able to
exploit knowledge acquired from previously learned tasks. Intuitively, access to several
problems simultaneously or sequentially could also be advantageous for a machine
learning system, especially if these tasks are closely related. Indeed, results of many
empirical studies have provided justification for this intuition. However, theoretical
justifications of this idea are rather limited.
The focus of this thesis is to expand the understanding of potential benefits of information
transfer between several related learning problems. We provide theoretical
analysis for three scenarios of multi-task learning - multiple kernel learning, sequential
learning and active task selection. We also provide a PAC-Bayesian perspective on
lifelong learning and investigate how the task generation process influences the generalization
guarantees in this scenario. In addition, we show how some of the obtained
theoretical results can be used to derive principled multi-task and lifelong learning
algorithms and illustrate their performance on various synthetic and real-world datasets.},
author = {Pentina, Anastasia},
pages = {127},
publisher = {IST Austria},
title = {{Theoretical foundations of multi-task lifelong learning}},
doi = {10.15479/AT:ISTA:TH_776},
year = {2016},
}
@phdthesis{1124,
author = {Morri, Maurizio},
pages = {129},
publisher = {IST Austria},
title = {{Optical functionalization of human class A orphan G-protein coupled receptors}},
year = {2016},
}
@phdthesis{1397,
abstract = {We study partially observable Markov decision processes (POMDPs) with objectives used in verification and artificial intelligence. The qualitative analysis problem given a POMDP and an objective asks whether there is a strategy (policy) to ensure that the objective is satisfied almost surely (with probability 1), resp. with positive probability (with probability greater than 0). For POMDPs with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards, we consider two types of path constraints: (i) a quantitative limit-average constraint defines the set of paths where the payoff is at least a given threshold L1 = 1. Our main results for qualitative limit-average constraint under almost-sure winning are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative limit-average constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We present a prototype implementation of our EXPTIME algorithm. For POMDPs with w-regular conditions specified as parity objectives, while the qualitative analysis problems are known to be undecidable even for very special case of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. Based on our theoretical algorithms we also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of well-known POMDP examples for robotics applications. For POMDPs with a set of target states and an integer cost associated with every transition, we study the optimization objective that asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely. We show that for general integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double and exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms that extend existing algorithms for POMDPs with finite-horizon objectives. We show experimentally that it performs well in many examples of interest. We study more deeply the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a strategy to ensure that the target set is reached almost surely. While in general the problem EXPTIME-complete, in many practical cases strategies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. We first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. Decentralized POMDPs (DEC-POMDPs) extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. In this work we consider Goal DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the real-time dynamic programming approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. In the end we present a short summary of a few other results related to verification of MDPs and POMDPs.},
author = {Chmelik, Martin},
pages = {232},
publisher = {IST Austria},
title = {{Algorithms for partially observable markov decision processes}},
year = {2016},
}
@phdthesis{1396,
abstract = {CA3 pyramidal neurons are thought to pay a key role in memory storage and pattern completion by activity-dependent synaptic plasticity between CA3-CA3 recurrent excitatory synapses. To examine the induction rules of synaptic plasticity at CA3-CA3 synapses, we performed whole-cell patch-clamp recordings in acute hippocampal slices from rats (postnatal 21-24 days) at room temperature. Compound excitatory postsynaptic potentials (ESPSs) were recorded by tract stimulation in stratum oriens in the presence of 10 µM gabazine. High-frequency stimulation (HFS) induced N-methyl-D-aspartate (NMDA) receptor-dependent long-term potentiation (LTP). Although LTP by HFS did not requier postsynaptic spikes, it was blocked by Na+-channel blockers suggesting that local active processes (e.g.) dendritic spikes) may contribute to LTP induction without requirement of a somatic action potential (AP). We next examined the properties of spike timing-dependent plasticity (STDP) at CA3-CA3 synapses. Unexpectedly, low-frequency pairing of EPSPs and backpropagated action potentialy (bAPs) induced LTP, independent of temporal order. The STDP curve was symmetric and broad, with a half-width of ~150 ms. Consistent with these specific STDP induction properties, post-presynaptic sequences led to a supralinear summation of spine [Ca2+] transients. Furthermore, in autoassociative network models, storage and recall was substantially more robust with symmetric than with asymmetric STDP rules. In conclusion, we found associative forms of LTP at CA3-CA3 recurrent collateral synapses with distinct induction rules. LTP induced by HFS may be associated with dendritic spikes. In contrast, low frequency pairing of pre- and postsynaptic activity induced LTP only if EPSP-AP were temporally very close. Together, these induction mechanisms of synaptiic plasticity may contribute to memory storage in the CA3-CA3 microcircuit at different ranges of activity.},
author = {Mishra, Rajiv Kumar},
pages = {83},
publisher = {IST Austria},
title = {{Synaptic plasticity rules at CA3-CA3 recurrent synapses in hippocampus}},
year = {2016},
}
@phdthesis{1122,
abstract = {Computer graphics is an extremely exciting field for two reasons. On the one hand,
there is a healthy injection of pragmatism coming from the visual effects industry
that want robust algorithms that work so they can produce results at an increasingly
frantic pace. On the other hand, they must always try to push the envelope and
achieve the impossible to wow their audiences in the next blockbuster, which means
that the industry has not succumb to conservatism, and there is plenty of room to
try out new and crazy ideas if there is a chance that it will pan into something
useful.
Water simulation has been in visual effects for decades, however it still remains
extremely challenging because of its high computational cost and difficult artdirectability.
The work in this thesis tries to address some of these difficulties.
Specifically, we make the following three novel contributions to the state-of-the-art
in water simulation for visual effects.
First, we develop the first algorithm that can convert any sequence of closed
surfaces in time into a moving triangle mesh. State-of-the-art methods at the time
could only handle surfaces with fixed connectivity, but we are the first to be able to
handle surfaces that merge and split apart. This is important for water simulation
practitioners, because it allows them to convert splashy water surfaces extracted
from particles or simulated using grid-based level sets into triangle meshes that can
be either textured and enhanced with extra surface dynamics as a post-process.
We also apply our algorithm to other phenomena that merge and split apart, such
as morphs and noisy reconstructions of human performances.
Second, we formulate a surface-based energy that measures the deviation of a
water surface froma physically valid state. Such discrepancies arise when there is a
mismatch in the degrees of freedom between the water surface and the underlying
physics solver. This commonly happens when practitioners use a moving triangle
mesh with a grid-based physics solver, or when high-resolution grid-based surfaces
are combined with low-resolution physics. Following the direction of steepest
descent on our surface-based energy, we can either smooth these artifacts or turn
them into high-resolution waves by interpreting the energy as a physical potential.
Third, we extend state-of-the-art techniques in non-reflecting boundaries to handle spatially and time-varying background flows. This allows a novel new
workflow where practitioners can re-simulate part of an existing simulation, such
as removing a solid obstacle, adding a new splash or locally changing the resolution.
Such changes can easily lead to new waves in the re-simulated region that would
reflect off of the new simulation boundary, effectively ruining the illusion of a
seamless simulation boundary between the existing and new simulations. Our
non-reflecting boundaries makes sure that such waves are absorbed.},
author = {Bojsen-Hansen, Morten},
pages = {114},
publisher = {IST Austria},
title = {{Tracking, correcting and absorbing water surface waves}},
doi = {10.15479/AT:ISTA:th_640},
year = {2016},
}
@phdthesis{1131,
abstract = {Evolution of gene regulation is important for phenotypic evolution and diversity. Sequence-specific binding of regulatory proteins is one of the key regulatory mechanisms determining gene expression. Although there has been intense interest in evolution of regulatory binding sites in the last decades, a theoretical understanding is far from being complete. In this thesis, I aim at a better understanding of the evolution of transcriptional regulatory binding sequences by using biophysical and population genetic models.
In the first part of the thesis, I discuss how to formulate the evolutionary dynamics of binding se- quences in a single isolated binding site and in promoter/enhancer regions. I develop a theoretical framework bridging between a thermodynamical model for transcription and a mutation-selection-drift model for monomorphic populations. I mainly address the typical evolutionary rates, and how they de- pend on biophysical parameters (e.g. binding length and specificity) and population genetic parameters (e.g. population size and selection strength).
In the second part of the thesis, I analyse empirical data for a better evolutionary and biophysical understanding of sequence-specific binding of bacterial RNA polymerase. First, I infer selection on regulatory and non-regulatory binding sites of RNA polymerase in the E. coli K12 genome. Second, I infer the chemical potential of RNA polymerase, an important but unknown physical parameter defining the threshold energy for strong binding. Furthermore, I try to understand the relation between the lac promoter sequence diversity and the LacZ activity variation among 20 bacterial isolates by constructing a simple but biophysically motivated gene expression model. Lastly, I lay out a statistical framework to predict adaptive point mutations in de novo promoter evolution in a selection experiment.},
author = {Tugrul, Murat},
pages = {89},
publisher = {IST Austria},
title = {{Evolution of transcriptional regulatory sequences}},
year = {2016},
}
@phdthesis{1125,
abstract = {Natural environments are never constant but subject to spatial and temporal change on
all scales, increasingly so due to human activity. Hence, it is crucial to understand the
impact of environmental variation on evolutionary processes. In this thesis, I present
three topics that share the common theme of environmental variation, yet illustrate its
effect from different perspectives.
First, I show how a temporally fluctuating environment gives rise to second-order
selection on a modifier for stress-induced mutagenesis. Without fluctuations, when
populations are adapted to their environment, mutation rates are minimized. I argue
that a stress-induced mutator mechanism may only be maintained if the population is
repeatedly subjected to diverse environmental challenges, and I outline implications of
the presented results to antibiotic treatment strategies.
Second, I discuss my work on the evolution of dispersal. Besides reproducing
known results about the effect of heterogeneous habitats on dispersal, it identifies
spatial changes in dispersal type frequencies as a source for selection for increased
propensities to disperse. This concept contains effects of relatedness that are known
to promote dispersal, and I explain how it identifies other forces selecting for dispersal
and puts them on a common scale.
Third, I analyse genetic variances of phenotypic traits under multivariate stabilizing
selection. For the case of constant environments, I generalize known formulae of
equilibrium variances to multiple traits and discuss how the genetic variance of a focal
trait is influenced by selection on background traits. I conclude by presenting ideas and
preliminary work aiming at including environmental fluctuations in the form of moving
trait optima into the model.},
author = {Novak, Sebastian},
pages = {124},
publisher = {IST Austria},
title = {{Evolutionary proccesses in variable emvironments}},
year = {2016},
}
@phdthesis{1123,
abstract = {Motivated by topological Tverberg-type problems in topological combinatorics and by classical
results about embeddings (maps without double points), we study the question whether a finite
simplicial complex K can be mapped into Rd without triple, quadruple, or, more generally, r-fold points (image points with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint simplices of K , and we seek necessary and sufficient conditions for the existence of such maps.
We present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction for embeddability of k -dimensional
complexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK = (r ≥ 1)k and d = rk \ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3.
An important guiding idea for our work was that suffciency of the DPC, together with an old
result of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime power and
N = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K = σN .
In 2015, Frick [16] found a very elegant way to overcome this \codimension 3 obstacle" and
to construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime power, by a reduction1 to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC.
In this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r not a prime power. },
author = {Mabillard, Isaac},
pages = {55},
publisher = {IST Austria},
title = {{Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture}},
year = {2016},
}
@phdthesis{1130,
abstract = {In this thesis we present a computer-aided programming approach to concurrency. Our approach
helps the programmer by automatically fixing concurrency-related bugs, i.e. bugs that occur
when the program is executed using an aggressive preemptive scheduler, but not when using a
non-preemptive (cooperative) scheduler. Bugs are program behaviours that are incorrect w.r.t.
a specification. We consider both user-provided explicit specifications in the form of assertion
statements in the code as well as an implicit specification. The implicit specification is inferred
from the non-preemptive behaviour. Let us consider sequences of calls that the program makes
to an external interface. The implicit specification requires that any such sequence produced
under a preemptive scheduler should be included in the set of sequences produced under a
non-preemptive scheduler.
We consider several semantics-preserving fixes that go beyond atomic sections typically
explored in the synchronisation synthesis literature. Our synthesis is able to place locks, barriers
and wait-signal statements and last, but not least reorder independent statements. The latter
may be useful if a thread is released to early, e.g., before some initialisation is completed. We
guarantee that our synthesis does not introduce deadlocks and that the synchronisation inserted
is optimal w.r.t. a given objective function.
We dub our solution trace-based synchronisation synthesis and it is loosely based on
counterexample-guided inductive synthesis (CEGIS). The synthesis works by discovering a
trace that is incorrect w.r.t. the specification and identifying ordering constraints crucial to trigger
the specification violation. Synchronisation may be placed immediately (greedy approach) or
delayed until all incorrect traces are found (non-greedy approach). For the non-greedy approach
we construct a set of global constraints over synchronisation placements. Each model of the
global constraints set corresponds to a correctness-ensuring synchronisation placement. The
placement that is optimal w.r.t. the given objective function is chosen as the synchronisation
solution.
We evaluate our approach on a number of realistic (albeit simplified) Linux device-driver
benchmarks. The benchmarks are versions of the drivers with known concurrency-related bugs.
For the experiments with an explicit specification we added assertions that would detect the bugs
in the experiments. Device drivers lend themselves to implicit specification, where the device and
the operating system are the external interfaces. Our experiments demonstrate that our synthesis
method is precise and efficient. We implemented objective functions for coarse-grained and
fine-grained locking and observed that different synchronisation placements are produced for
our experiments, favouring e.g. a minimal number of synchronisation operations or maximum
concurrency.},
author = {Tarrach, Thorsten},
pages = {151},
publisher = {IST Austria},
title = {{Automatic synthesis of synchronisation primitives for concurrent programs}},
year = {2016},
}