TY - GEN
AB - Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing.
In this paper, we study compositional properties of the IOCO-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the IOCO conformance relation, the resulting methodology can be applied to a broader class of systems.
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Krenn, Willibald
AU - Nickovic, Dejan
ID - 5411
SN - 2664-1690
TI - Compositional specifications for IOCO testing
ER -
TY - GEN
AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.
We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.
We present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.
AU - Chatterjee, Krishnendu
AU - Daca, Przemyslaw
AU - Chmelik, Martin
ID - 5412
SN - 2664-1690
TI - CEGAR for qualitative analysis of probabilistic systems
ER -
TY - GEN
AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.
We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.
We present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.
AU - Chatterjee, Krishnendu
AU - Daca, Przemyslaw
AU - Chmelik, Martin
ID - 5413
SN - 2664-1690
TI - CEGAR for qualitative analysis of probabilistic systems
ER -
TY - GEN
AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.
We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.
We present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation.
We have implemented our algorithms and show that the compositional analysis leads to significant improvements.
AU - Chatterjee, Krishnendu
AU - Daca, Przemyslaw
AU - Chmelik, Martin
ID - 5414
SN - 2664-1690
TI - CEGAR for qualitative analysis of probabilistic systems
ER -
TY - GEN
AB - Recently there has been a significant effort to add quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5415
SN - 2664-1690
TI - Nested weighted automata
ER -
TY - GEN
AB - As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem.
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5416
SN - 2664-1690
TI - Model measuring for hybrid systems
ER -
TY - GEN
AB - We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.
The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.
We show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.
We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging.
We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5417
SN - 2664-1690
TI - From model checking to model measuring
ER -
TY - GEN
AB - We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 5418
SN - 2664-1690
TI - Games with a weak adversary
ER -
TY - GEN
AB - We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:
1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).
2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.
3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.
Our algorithms improve all existing results, and use very simple data structures.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5419
SN - 2664-1690
TI - Improved algorithms for reachability and shortest path on low tree-width graphs
ER -
TY - GEN
AB - We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
ID - 5420
SN - 2664-1690
TI - The value 1 problem for concurrent mean-payoff games
ER -
TY - GEN
AB - Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Nowak, Martin
ID - 5421
SN - 2664-1690
TI - The complexity of evolution on graphs
ER -
TY - GEN
AB - Notes from the Third Plenary for the Research Data Alliance in Dublin, Ireland on March 26 to 28, 2014 with focus on starting an institutional research data repository.
AU - Porsche, Jana
ID - 5422
TI - Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland
ER -
TY - GEN
AB - We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application.
AU - Chatterjee, Krishnendu
AU - Kössler, Alexander
AU - Pavlogiannis, Andreas
AU - Schmid, Ulrich
ID - 5423
SN - 2664-1690
TI - A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks
ER -
TY - GEN
AB - We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Raghav
AU - Kanodia, Ayush
ID - 5424
SN - 2664-1690
TI - Qualitative analysis of POMDPs with temporal logic specifications for robotics applications
ER -
TY - GEN
AB - We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Raghav
AU - Kanodia, Ayush
ID - 5426
SN - 2664-1690
TI - Qualitative analysis of POMDPs with temporal logic specifications for robotics applications
ER -
TY - GEN
AB - We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5427
SN - 2664-1690
TI - Optimal tree-decomposition balancing and reachability on low treewidth graphs
ER -
TY - GEN
AB - Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms.
In this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
AU - Velner, Yaron
ID - 5428
SN - 2664-1690
TI - Quantitative fair simulation games
ER -
TY - CHAP
AB - Mechanically coupled cells can generate forces driving cell and tissue morphogenesis during development. Visualization and measuring of these forces is of major importance to better understand the complexity of the biomechanic processes that shape cells and tissues. Here, we describe how UV laser ablation can be utilized to quantitatively assess mechanical tension in different tissues of the developing zebrafish and in cultures of primary germ layer progenitor cells ex vivo.
AU - Smutny, Michael
AU - Behrndt, Martin
AU - Campinho, Pedro
AU - Ruprecht, Verena
AU - Heisenberg, Carl-Philipp J
ED - Nelson, Celeste
ID - 6178
SN - 1064-3745
T2 - Tissue Morphogenesis
TI - UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo
VL - 1189
ER -
TY - BOOK
AB - This monograph presents a short course in computational geometry and topology. In the first part the book covers Voronoi diagrams and Delaunay triangulations, then it presents the theory of alpha complexes which play a crucial role in biology. The central part of the book is the homology theory and their computation, including the theory of persistence which is indispensable for applications, e.g. shape reconstruction. The target audience comprises researchers and practitioners in mathematics, biology, neuroscience and computer science, but the book may also be beneficial to graduate students of these fields.
AU - Edelsbrunner, Herbert
ID - 6853
SN - 2191-530X
TI - A Short Course in Computational Geometry and Topology
ER -
TY - GEN
AU - Huszár, Kristóf
AU - Rolinek, Michal
ID - 7038
TI - Playful Math - An introduction to mathematical games
ER -
TY - JOUR
AB - We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n×n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1+ε)-approximation algorithm for the problem and the running time of our algorithm is Õ(nωlog3(nW/ε)/ε),1 where O(nω) is the time required for the classic n×n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ε)) factor in space a cycle with approximately optimal weight can be computed within the same time bound.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika
AU - Krinninger, Sebastian
AU - Loitzenbauer, Veronika
AU - Raskin, Michael
ID - 1375
IS - C
JF - Theoretical Computer Science
TI - Approximating the minimum cycle mean
VL - 547
ER -
TY - CONF
AB - Fault-tolerant distributed algorithms play an important role in ensuring the reliability of many software applications. In this paper we consider distributed algorithms whose computations are organized in rounds. To verify the correctness of such algorithms, we reason about (i) properties (such as invariants) of the state, (ii) the transitions controlled by the algorithm, and (iii) the communication graph. We introduce a logic that addresses these points, and contains set comprehensions with cardinality constraints, function symbols to describe the local states of each process, and a limited form of quantifier alternation to express the verification conditions. We show its use in automating the verification of consensus algorithms. In particular, we give a semi-decision procedure for the unsatisfiability problem of the logic and identify a decidable fragment. We successfully applied our framework to verify the correctness of a variety of consensus algorithms tolerant to both benign faults (message loss, process crashes) and value faults (message corruption).
AU - Dragoi, Cezara
AU - Henzinger, Thomas A
AU - Veith, Helmut
AU - Widder, Josef
AU - Zufferey, Damien
ID - 1392
TI - A logic-based framework for verifying consensus algorithms
VL - 8318
ER -
TY - CONF
AB - Probabilistic programs are usual functional or imperative programs with two added constructs: (1) the ability to draw values at random from distributions, and (2) the ability to condition values of variables in a program via observations. Models from diverse application areas such as computer vision, coding theory, cryptographic protocols, biology and reliability analysis can be written as probabilistic programs. Probabilistic inference is the problem of computing an explicit representation of the probability distribution implicitly specified by a probabilistic program. Depending on the application, the desired output from inference may vary-we may want to estimate the expected value of some function f with respect to the distribution, or the mode of the distribution, or simply a set of samples drawn from the distribution. In this paper, we describe connections this research area called \Probabilistic Programming" has with programming languages and software engineering, and this includes language design, and the static and dynamic analysis of programs. We survey current state of the art and speculate on promising directions for future research.
AU - Gordon, Andrew
AU - Henzinger, Thomas A
AU - Nori, Aditya
AU - Rajamani, Sriram
ID - 1393
T2 - Proceedings of the on Future of Software Engineering
TI - Probabilistic programming
ER -
TY - THES
AB - In this thesis I studied various individual and social immune defences employed by the invasive garden ant Lasius neglectus mostly against entomopathogenic fungi. The first two chapters of this thesis address the phenomenon of 'social immunisation'. Social immunisation, that is the immunological protection of group members due to social contact to a pathogen-exposed nestmate, has been described in various social insect species against different types of pathogens. However, in the case of entomopathogenic fungi it has, so far, only been demonstrated that social immunisation exists at all. Its underlying mechanisms r any other properties were, however, unknown. In the first chapter of this thesis I identified the mechanistic basis of social immunisation in L. neglectus against the entomopathogenous fungus Metarhizium. I could show that nestmates of a pathogen-exposed individual contract low-level infections due to social interactions. These low-level infections are, however, non-lethal and cause an active stimulation of the immune system, which protects the nestmates upon subsequent pathogen encounters. In the second chapter of this thesis I investigated the specificity and colony level effects of social immunisation. I demonstrated that the protection conferred by social immunisation is highly specific, protecting ants only against the same pathogen strain. In addition, depending on the respective context, social immunisation may even cause fitness costs. I further showed that social immunisation crucially affects sanitary behaviour and disease dynamics within ant groups. In the third chapter of this thesis I studied the effects of the ectosymbiotic fungus Laboulbenia formicarum on its host L. neglectus. Although Laboulbeniales are the largest order of insect-parasitic fungi, research concerning host fitness consequence is sparse. I showed that highly Laboulbenia-infected ants sustain fitness costs under resource limitation, however, gain fitness benefits when exposed to an entomopathogenus fungus. These effects are probably cause by a prophylactic upregulation of behavioural as well as physiological immune defences in highly infected ants.
AU - Konrad, Matthias
ID - 1395
TI - Immune defences in ants: Effects of social immunisation and a fungal ectosymbiont in the ant Lasius neglectus
ER -
TY - THES
AB - Phosphatidylinositol (Ptdlns) is a structural phospholipid that can be phosphorylated into various lipid signaling molecules, designated polyphosphoinositides (PPIs). The reversible phosphorylation of PPIs on the 3, 4, or 5 position of inositol is performed by a set of organelle-specific kinases and phosphatases, and the characteristic head groups make these molecules ideal for regulating biological processes in time and space. In yeast and mammals, Ptdlns3P and Ptdlns(3,5)P2 play crucial roles in trafficking toward the lytic compartments, whereas the role in plants is not yet fully understood. Here we identified the role of a land plant-specific subgroup of PPI phosphatases, the suppressor of actin 2 (SAC2) to SAC5, during vauolar trafficking and morphogenesis in Arabidopsis thaliana. SAC2-SAC5 localize to the tonoplast along with Ptdlns3P, the presumable product of their activity. in SAC gain- and loss-of-function mutants, the levels of Ptdlns monophosphates and bisphosphates were changed, with opposite effects on the morphology of storage and lytic vacuoles, and the trafficking toward the vacuoles was defective. Moreover, multiple sac knockout mutants had an increased number of smaller storage and lytic vacuoles, whereas extralarge vacuoles were observed in the overexpression lines, correlating with various growth and developmental defects. The fragmented vacuolar phenotype of sac mutants could be mimicked by treating wild-type seedlings with Ptdlns(3,5)P2, corroborating that this PPI is important for vacuole morphology. Taken together, these results provide evidence that PPIs, together with their metabolic enzymes SAC2-SAC5, are crucial for vacuolar trafficking and for vacuolar morphology and function in plants.
AU - Marhavá, Petra
ID - 1402
TI - Molecular mechanisms of patterning and subcellular trafficking in Arabidopsis thaliana
ER -
TY - THES
AB - A variety of developmental and disease related processes depend on epithelial cell sheet spreading. In order to gain insight into the biophysical mechanism(s) underlying the tissue morphogenesis we studied the spreading of an epithelium during the early development of the zebrafish embryo. In zebrafish epiboly the enveloping cell layer (EVL), a simple squamous epithelium, spreads over the yolk cell to completely engulf it at the end of gastrulation. Previous studies have proposed that an actomyosin ring forming within the yolk syncytial layer (YSL) acts as purse string that through constriction along its circumference pulls on the margin of the EVL. Direct biophysical evidence for this hypothesis has however been missing. The aim of the thesis was to understand how the actomyosin ring may generate pulling forces onto the EVL and what cellular mechanism(s) may facilitate the spreading of the epithelium. Using laser ablation to measure cortical tension within the actomyosin ring we found an anisotropic tension distribution, which was highest along the circumference of the ring. However the low degree of anisotropy was incompatible with the actomyosin ring functioning as a purse string only. Additionally, we observed retrograde cortical flow from vegetal parts of the ring into the EVL margin. Interpreting the experimental data using a theoretical distribution that models the tissues as active viscous gels led us to proposen that the actomyosin ring has a twofold contribution to EVL epiboly. It not only acts as a purse string through constriction along its circumference, but in addition constriction along the width of the ring generates pulling forces through friction-resisted cortical flow. Moreover, when rendering the purse string mechanism unproductive EVL epiboly proceeded normally indicating that the flow-friction mechanism is sufficient to drive the process. Aiming to understand what cellular mechanism(s) may facilitate the spreading of the epithelium we found that tension-oriented EVL cell divisions limit tissue anisotropy by releasing tension along the division axis and promote epithelial spreading. Notably, EVL cells undergo ectopic cell fusion in conditions in which oriented-cell division is impaired or the epithelium is mechanically challenged. Taken together our study of EVL epiboly suggests a novel mechanism of force generation for actomyosin rings through friction-resisted cortical flow and highlights the importance of tension-oriented cell divisions in epithelial morphogenesis.
AU - Behrndt, Martin
ID - 1403
TI - Forces driving epithelial spreading in zebrafish epiboly
ER -
TY - THES
AB - The co-evolution of hosts and pathogens is characterized by continuous adaptations of both parties. Pathogens of social insects need to adapt towards disease defences at two levels: 1) individual immunity of each colony member consisting of behavioural defence strategies as well as humoral and cellular immune responses and 2) social immunity that is collectively performed by all group members comprising behavioural, physiological and organisational defence strategies.
To disentangle the selection pressure on pathogens by the collective versus individual level of disease defence in social insects, we performed an evolution experiment using the Argentine Ant, Linepithema humile, as a host and a mixture of the general insect pathogenic fungus Metarhizium spp. (6 strains) as a pathogen. We allowed pathogen evolution over 10 serial host passages to two different evolution host treatments: (1) only individual host immunity in a single host treatment, and (2) simultaneously acting individual and social immunity in a social host treatment, in which an exposed ant was accompanied by two untreated nestmates.
Before starting the pathogen evolution experiment, the 6 Metarhizium spp. strains were characterised concerning conidiospore size killing rates in singly and socially reared ants, their competitiveness under coinfecting conditions and their influence on ant behaviour. We analysed how the ancestral atrain mixture changed in conidiospere size, killing rate and strain composition dependent on host treatment (single or social hosts) during 10 passages and found that killing rate and conidiospere size of the pathogen increased under both evolution regimes, but different depending on host treatment.
Testing the evolved strain mixtures that evolved under either the single or social host treatment under both single and social current rearing conditions in a full factorial design experiment revealed that the additional collective defences in insect societies add new selection pressure for their coevolving pathogens that compromise their ability to adapt to its host at the group level. To our knowledge, this is the first study directly measuring the influence of social immunity on pathogen evolution.
AU - Stock, Miriam
ID - 1404
TI - Evolution of a fungal pathogen towards individual versus social immunity in ants
ER -
TY - CONF
AB - The Wigner-Dyson-Gaudin-Mehta conjecture asserts that the local eigenvalue statistics of large real and complex Hermitian matrices with independent, identically distributed entries are universal in a sense that they depend only on the symmetry class of the matrix and otherwise are independent of the details of the distribution. We present the recent solution to this half-century old conjecture. We explain how stochastic tools, such as the Dyson Brownian motion, and PDE ideas, such as De Giorgi-Nash-Moser regularity theory, were combined in the solution. We also show related results for log-gases that represent a universal model for strongly correlated systems. Finally, in the spirit of Wigner’s original vision, we discuss the extensions of these universality results to more realistic physical systems such as random band matrices.
AU - Erdös, László
ID - 1507
TI - Random matrices, log-gases and Hölder regularity
VL - 3
ER -
TY - CONF
AB - We present a rigorous derivation of the BCS gap equation for superfluid fermionic gases with point interactions. Our starting point is the BCS energy functional, whose minimizer we investigate in the limit when the range of the interaction potential goes to zero.
AU - Bräunlich, Gerhard
AU - Hainzl, Christian
AU - Seiringer, Robert
ID - 1516
T2 - Proceedings of the QMath12 Conference
TI - On the BCS gap equation for superfluid fermionic gases
ER -
TY - JOUR
AB - Ammonium is the major nitrogen source in some plant ecosystems but is toxic at high concentrations, especially when available as the exclusive nitrogen source. Ammonium stress rapidly leads to various metabolic and hormonal imbalances that ultimately inhibit root and shoot growth in many plant species, including Arabidopsis thaliana (L.) Heynh. To identify molecular and genetic factors involved in seedling survival with prolonged exclusive NH4+ nutrition, a transcriptomic analysis with microarrays was used. Substantial transcriptional differences were most pronounced in (NH4)2SO4-grown seedlings, compared with plants grown on KNO3 or NH4NO3. Consistent with previous physiological analyses, major differences in the expression modules of photosynthesis-related genes, an altered mitochondrial metabolism, differential expression of the primary NH4+ assimilation, alteration of transporter gene expression and crucial changes in cell wall biosynthesis were found. A major difference in plant hormone responses, particularly of auxin but not cytokinin, was striking. The activity of the DR5::GUS reporter revealed a dramatically decreased auxin response in (NH4)2SO4-grown primary roots. The impaired root growth on (NH4)2SO4 was partially rescued by exogenous auxin or in specific mutants in the auxin pathway. The data suggest that NH4+-induced nutritional and metabolic imbalances can be partially overcome by elevated auxin levels.
AU - Yang, Huaiyu
AU - Von Der Fecht Bartenbach, Jenny
AU - Friml, Jirí
AU - Lohmann, Jan
AU - Neuhäuser, Benjamin
AU - Ludewig, Uwe
ID - 1532
IS - 3
JF - Functional Plant Biology
TI - Auxin-modulated root growth inhibition in Arabidopsis thaliana seedlings with ammonium as the sole nitrogen source
VL - 42
ER -
TY - JOUR
AB - We propose a method for propagating edit operations in 2D vector graphics, based on geometric relationship functions. These functions quantify the geometric relationship of a point to a polygon, such as the distance to the boundary or the direction to the closest corner vertex. The level sets of the relationship functions describe points with the same relationship to a polygon. For a given query point, we first determine a set of relationships to local features, construct all level sets for these relationships, and accumulate them. The maxima of the resulting distribution are points with similar geometric relationships. We show extensions to handle mirror symmetries, and discuss the use of relationship functions as local coordinate systems. Our method can be applied, for example, to interactive floorplan editing, and it is especially useful for large layouts, where individual edits would be cumbersome. We demonstrate populating 2D layouts with tens to hundreds of objects by propagating relatively few edit operations.
AU - Guerrero, Paul
AU - Jeschke, Stefan
AU - Wimmer, Michael
AU - Wonka, Peter
ID - 1629
IS - 2
JF - ACM Transactions on Graphics
TI - Edit propagation using geometric relationship functions
VL - 33
ER -
TY - CONF
AB - We extend the notion of verifiable random functions (VRF) to constrained VRFs, which generalize the concept of constrained pseudorandom functions, put forward by Boneh and Waters (Asiacrypt’13), and independently by Kiayias et al. (CCS’13) and Boyle et al. (PKC’14), who call them delegatable PRFs and functional PRFs, respectively. In a standard VRF the secret key sk allows one to evaluate a pseudorandom function at any point of its domain; in addition, it enables computation of a non-interactive proof that the function value was computed correctly. In a constrained VRF from the key sk one can derive constrained keys skS for subsets S of the domain, which allow computation of function values and proofs only at points in S. After formally defining constrained VRFs, we derive instantiations from the multilinear-maps-based constrained PRFs by Boneh and Waters, yielding a VRF with constrained keys for any set that can be decided by a polynomial-size circuit. Our VRFs have the same function values as the Boneh-Waters PRFs and are proved secure under the same hardness assumption, showing that verifiability comes at no cost. Constrained (functional) VRFs were stated as an open problem by Boyle et al.
AU - Fuchsbauer, Georg
ED - Abdalla, Michel
ED - De Prisco, Roberto
ID - 1643
T2 - SCN 2014
TI - Constrained Verifiable Random Functions
VL - 8642
ER -
TY - JOUR
AB - Adaptation in the retina is thought to optimize the encoding of natural light signals into sequences of spikes sent to the brain. While adaptive changes in retinal processing to the variations of the mean luminance level and second-order stimulus statistics have been documented before, no such measurements have been performed when higher-order moments of the light distribution change. We therefore measured the ganglion cell responses in the tiger salamander retina to controlled changes in the second (contrast), third (skew) and fourth (kurtosis) moments of the light intensity distribution of spatially uniform temporally independent stimuli. The skew and kurtosis of the stimuli were chosen to cover the range observed in natural scenes. We quantified adaptation in ganglion cells by studying linear-nonlinear models that capture well the retinal encoding properties across all stimuli. We found that the encoding properties of retinal ganglion cells change only marginally when higher-order statistics change, compared to the changes observed in response to the variation in contrast. By analyzing optimal coding in LN-type models, we showed that neurons can maintain a high information rate without large dynamic adaptation to changes in skew or kurtosis. This is because, for uncorrelated stimuli, spatio-temporal summation within the receptive field averages away non-gaussian aspects of the light intensity distribution.
AU - Tkacik, Gasper
AU - Ghosh, Anandamohan
AU - Schneidman, Elad
AU - Segev, Ronen
ID - 3263
IS - 1
JF - PLoS One
TI - Adaptation to changes in higher-order stimulus statistics in the salamander retina
VL - 9
ER -
TY - CONF
AB - While fixing concurrency bugs, program repair algorithms may introduce new concurrency bugs. We present an algorithm that avoids such regressions. The solution space is given by a set of program transformations we consider in the repair process. These include reordering of instructions within a thread and inserting atomic sections. The new algorithm learns a constraint on the space of candidate solutions, from both positive examples (error-free traces) and counterexamples (error traces). From each counterexample, the algorithm learns a constraint necessary to remove the errors. From each positive examples, it learns a constraint that is necessary in order to prevent the repair from turning the trace into an error trace. We implemented the algorithm and evaluated it on simplified Linux device drivers with known bugs.
AU - Cerny, Pavol
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Ryzhyk, Leonid
AU - Tarrach, Thorsten
ID - 2218
SN - 978-331908866-2
TI - Regression-free synthesis for concurrency
VL - 8559
ER -
TY - CONF
AB - Motivated by topological Tverberg-type problems, we consider multiple (double, triple, and higher multiplicity) selfintersection points of maps from finite simplicial complexes (compact polyhedra) into ℝd and study conditions under which such multiple points can be eliminated. The most classical case is that of embeddings (i.e., maps without double points) of a κ-dimensional complex K into ℝ2κ. For this problem, the work of van Kampen, Shapiro, and Wu provides an efficiently testable necessary condition for embeddability (namely, vanishing of the van Kampen ob-struction). For κ ≥ 3, the condition is also sufficient, and yields a polynomial-time algorithm for deciding embeddability: One starts with an arbitrary map f : K→ℝ2κ, which generically has finitely many double points; if k ≥ 3 and if the obstruction vanishes then one can successively remove these double points by local modifications of the map f. One of the main tools is the famous Whitney trick that permits eliminating pairs of double points of opposite intersection sign. We are interested in generalizing this approach to intersection points of higher multiplicity. We call a point y 2 ℝd an r-fold Tverberg point of a map f : Kκ →ℝd if y lies in the intersection f(σ1)∩. ∩f(σr) of the images of r pairwise disjoint simplices of K. The analogue of (non-)embeddability that we study is the problem Tverbergκ r→d: Given a κ-dimensional complex K, does it satisfy a Tverberg-type theorem with parameters r and d, i.e., does every map f : K κ → ℝd have an r-fold Tverberg point? Here, we show that for fixed r, κ and d of the form d = rm and k = (r-1)m, m ≥ 3, there is a polynomial-time algorithm for deciding this (based on the vanishing of a cohomological obstruction, as in the case of embeddings). Our main tool is an r-fold analogue of the Whitney trick: Given r pairwise disjoint simplices of K such that the intersection of their images contains two r-fold Tverberg points y+ and y- of opposite intersection sign, we can eliminate y+ and y- by a local isotopy of f. In a subsequent paper, we plan to develop this further and present a generalization of the classical Haeiger-Weber Theorem (which yields a necessary and sufficient condition for embeddability of κ-complexes into ℝd for a wider range of dimensions) to intersection points of higher multiplicity.
AU - Mabillard, Isaac
AU - Wagner, Uli
ID - 2159
T2 - Proceedings of the Annual Symposium on Computational Geometry
TI - Eliminating Tverberg points, I. An analogue of the Whitney trick
ER -
TY - JOUR
AB - Understanding the evolution of dispersal is essential for understanding and predicting the dynamics of natural populations. Two main factors are known to influence dispersal evolution: spatio-temporal variation in the environment and relatedness between individuals. However, the relation between these factors is still poorly understood, and they are usually treated separately. In this article, I present a theoretical framework that contains and connects effects of both environmental variation and relatedness, and reproduces and extends their known features. Spatial habitat variation selects for balanced dispersal strategies, whereby the population is kept at an ideal free distribution. Within this class of dispersal strategies, I explain how increased dispersal is promoted by perturbations to the dispersal type frequencies. An explicit formula shows the magnitude of the selective advantage of increased dispersal in terms of the spatial variability in the frequencies of the different dispersal strategies present. These variances are capable of capturing various sources of stochasticity and hence establish a common scale for their effects on the evolution of dispersal. The results furthermore indicate an alternative approach to identifying effects of relatedness on dispersal evolution.
AU - Novak, Sebastian
ID - 2023
IS - 24
JF - Ecology and Evolution
TI - Habitat heterogeneities versus spatial type frequency variances as driving forces of dispersal evolution
VL - 4
ER -
TY - JOUR
AB - Deposits of phosphorylated tau protein and convergence of pathology in the hippocampus are the hallmarks of neurodegenerative tauopathies. Thus we aimed to evaluate whether regional and cellular vulnerability patterns in the hippocampus distinguish tauopathies or are influenced by their concomitant presence. Methods: We created a heat map of phospho-tau (AT8) immunoreactivity patterns in 24 hippocampal subregions/layers in individuals with Alzheimer's disease (AD)-related neurofibrillary degeneration (n = 40), Pick's disease (n = 8), progressive supranuclear palsy (n = 7), corticobasal degeneration (n = 6), argyrophilic grain disease (AGD, n = 18), globular glial tauopathy (n = 5), and tau-astrogliopathy of the elderly (n = 10). AT8 immunoreactivity patterns were compared by mathematical analysis. Results: Our study reveals disease-specific hot spots and regional selective vulnerability for these disorders. The pattern of hippocampal AD-related tau pathology is strongly influenced by concomitant AGD. Mathematical analysis reveals that hippocampal involvement in primary tauopathies is distinguishable from early-stage AD-related neurofibrillary degeneration. Conclusion: Our data demonstrate disease-specific AT8 immunoreactivity patterns and hot spots in the hippocampus even in tauopathies, which primarily do not affect the hippocampus. These hot spots can be shifted to other regions by the co-occurrence of tauopathies like AGD. Our observations support the notion that globular glial tauopathies and tau-astrogliopathy of the elderly are distinct entities.
AU - Milenković, Ivan
AU - Petrov, Tatjana
AU - Kovács, Gábor
ID - 1913
IS - 5-6
JF - Dementia and Geriatric Cognitive Disorders
TI - Patterns of hippocampal tau pathology differentiate neurodegenerative dementias
VL - 38
ER -
TY - JOUR
AB - Selection for disease control is believed to have contributed to shape the organisation of insect societies — leading to interaction patterns that mitigate disease transmission risk within colonies, conferring them ‘organisational immunity’. Recent studies combining epidemiological models with social network analysis have identified general properties of interaction networks that may hinder propagation of infection within groups. These can be prophylactic and/or induced upon pathogen exposure. Here we review empirical evidence for these two types of organisational immunity in social insects and describe the individual-level behaviours that underlie it. We highlight areas requiring further investigation, and emphasise the need for tighter links between theory and empirical research and between individual-level and collective-level analyses.
AU - Stroeymeyt, Nathalie
AU - Casillas Perez, Barbara E
AU - Cremer, Sylvia
ID - 1999
IS - 1
JF - Current Opinion in Insect Science
TI - Organisational immunity in social insects
VL - 5
ER -
TY - CONF
AB - Direct Anonymous Attestation (DAA) is one of the most complex cryptographic protocols deployed in practice. It allows an embedded secure processor known as a Trusted Platform Module (TPM) to attest to the configuration of its host computer without violating the owner’s privacy. DAA has been standardized by the Trusted Computing Group and ISO/IEC.
The security of the DAA standard and all existing schemes is analyzed in the random-oracle model. We provide the first constructions of DAA in the standard model, that is, without relying on random oracles. Our constructions use new building blocks, including the first efficient signatures of knowledge in the standard model, which have many applications beyond DAA.
AU - Bernhard, David
AU - Fuchsbauer, Georg
AU - Ghadafi, Essam
ID - 2260
TI - Efficient signatures of knowledge and DAA in the standard model
VL - 7954
ER -
TY - JOUR
AB - Faithful progression through the cell cycle is crucial to the maintenance and developmental potential of stem cells. Here, we demonstrate that neural stem cells (NSCs) and intermediate neural progenitor cells (NPCs) employ a zinc-finger transcription factor specificity protein 2 (Sp2) as a cell cycle regulator in two temporally and spatially distinct progenitor domains. Differential conditional deletion of Sp2 in early embryonic cerebral cortical progenitors, and perinatal olfactory bulb progenitors disrupted transitions through G1, G2 and M phases, whereas DNA synthesis appeared intact. Cell-autonomous function of Sp2 was identified by deletion of Sp2 using mosaic analysis with double markers, which clearly established that conditional Sp2-null NSCs and NPCs are M phase arrested in vivo. Importantly, conditional deletion of Sp2 led to a decline in the generation of NPCs and neurons in the developing and postnatal brains. Our findings implicate Sp2-dependent mechanisms as novel regulators of cell cycle progression, the absence of which disrupts neurogenesis in the embryonic and postnatal brain.
AU - Liang, Huixuan
AU - Xiao, Guanxi
AU - Yin, Haifeng
AU - Hippenmeyer, Simon
AU - Horowitz, Jonathan
AU - Ghashghaei, Troy
ID - 2264
IS - 3
JF - Development
TI - Neural development is dependent on the function of specificity protein 2 in cell cycle progression
VL - 140
ER -
TY - CONF
AB - Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher-
ent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive
Weighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs.
AU - Bachrach, Yoram
AU - Kohli, Pushmeet
AU - Kolmogorov, Vladimir
AU - Zadimoghaddam, Morteza
ID - 2270
TI - Optimal Coalition Structures in Cooperative Graph Games
ER -
TY - CONF
AB - We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1...xn is the sum of terms over intervals [i,j] where each term is non-zero only if the substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems.
We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined length of input patterns, ℓmax is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of (Ye et al., 2009) whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where |Γ| is the number of input patterns.
In addition, we give an efficient algorithm for sampling. Finally, we consider the case of non-positive weights. (Komodakis & Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present a modification that has the same worst-case complexity but can beat it in the best case.
AU - Takhanov, Rustem
AU - Kolmogorov, Vladimir
ID - 2272
IS - 3
T2 - ICML'13 Proceedings of the 30th International Conference on International
TI - Inference algorithms for pattern-based CRFs on sequence data
VL - 28
ER -
TY - GEN
AB - We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results.
AU - Vladimir Kolmogorov
ID - 2273
TI - Reweighted message passing revisited
ER -
TY - GEN
AB - Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
In this work, we put forward an alternative concept for PoWs -- so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model, using graphs with high "pebbling complexity" and Merkle hash-trees.
AU - Dziembowski, Stefan
AU - Faust, Sebastian
AU - Kolmogorov, Vladimir
AU - Pietrzak, Krzysztof Z
ID - 2274
TI - Proofs of Space
ER -
TY - CONF
AB - The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions.
AU - Gridchyn, Igor
AU - Kolmogorov, Vladimir
ID - 2276
TI - Potts model, parametric maxflow and k-submodular functions
ER -
TY - JOUR
AB - Redundancies and correlations in the responses of sensory neurons may seem to waste neural resources, but they can also carry cues about structured stimuli and may help the brain to correct for response errors. To investigate the effect of stimulus structure on redundancy in retina, we measured simultaneous responses from populations of retinal ganglion cells presented with natural and artificial stimuli that varied greatly in correlation structure; these stimuli and recordings are publicly available online. Responding to spatio-temporally structured stimuli such as natural movies, pairs of ganglion cells were modestly more correlated than in response to white noise checkerboards, but they were much less correlated than predicted by a non-adapting functional model of retinal response. Meanwhile, responding to stimuli with purely spatial correlations, pairs of ganglion cells showed increased correlations consistent with a static, non-adapting receptive field and nonlinearity. We found that in response to spatio-temporally correlated stimuli, ganglion cells had faster temporal kernels and tended to have stronger surrounds. These properties of individual cells, along with gain changes that opposed changes in effective contrast at the ganglion cell input, largely explained the pattern of pairwise correlations across stimuli where receptive field measurements were possible.
AU - Simmons, Kristina
AU - Prentice, Jason
AU - Tkacik, Gasper
AU - Homann, Jan
AU - Yee, Heather
AU - Palmer, Stephanie
AU - Nelson, Philip
AU - Balasubramanian, Vijay
ID - 2277
IS - 12
JF - PLoS Computational Biology
TI - Transformation of stimulus correlations by the retina
VL - 9
ER -
TY - JOUR
AB - It is firmly established that interactions between neurons and glia are fundamental across species for the correct establishment of a functional brain. Here, we found that the glia of the Drosophila larval brain display an essential non-autonomous role during the development of the optic lobe. The optic lobe develops from neuroepithelial cells that proliferate by dividing symmetrically until they switch to asymmetric/differentiative divisions that generate neuroblasts. The proneural gene lethal of scute (l9sc) is transiently activated by the epidermal growth factor receptor (EGFR)-Ras signal transduction pathway at the leading edge of a proneural wave that sweeps from medial to lateral neuroepithelium, promoting this switch. This process is tightly regulated by the tissue-autonomous function within the neuroepithelium of multiple signaling pathways, including EGFR-Ras and Notch. This study shows that the Notch ligand Serrate (Ser) is expressed in the glia and it forms a complex in vivo with Notch and Canoe, which colocalize at the adherens junctions of neuroepithelial cells. This complex is crucial for interactions between glia and neuroepithelial cells during optic lobe development. Ser is tissue-autonomously required in the glia where it activates Notch to regulate its proliferation, and non-autonomously in the neuroepithelium where Ser induces Notch signaling to avoid the premature activation of the EGFR-Ras pathway and hence of L9sc. Interestingly, different Notch activity reporters showed very different expression patterns in the glia and in the neuroepithelium, suggesting the existence of tissue-specific factors that promote the expression of particular Notch target genes or/and a reporter response dependent on different thresholds of Notch signaling.
AU - Pérez Gómez, Raquel
AU - Slovakova, Jana
AU - Rives Quinto, Noemí
AU - Krejčí, Alena
AU - Carmena, Ana
ID - 2278
IS - 21
JF - Journal of Cell Science
TI - A serrate-notch-canoe complex mediates essential interactions between glia and neuroepithelial cells during Drosophila optic lobe development
VL - 126
ER -
TY - CONF
AB - We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Randour, Mickael
AU - Raskin, Jean
ID - 2279
TI - Looking at mean-payoff and total-payoff through windows
VL - 8172
ER -
TY - JOUR
AB - The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application-chromosome organization in the human cell nucleus-is discussed briefly, and some illustrative results are presented.
AU - Uhler, Caroline
AU - Wright, Stephen
ID - 2280
IS - 4
JF - SIAM Review
TI - Packing ellipsoids with overlap
VL - 55
ER -
TY - JOUR
AB - Epithelial spreading is a common and fundamental aspect of various developmental and disease-related processes such as epithelial closure and wound healing. A key challenge for epithelial tissues undergoing spreading is to increase their surface area without disrupting epithelial integrity. Here we show that orienting cell divisions by tension constitutes an efficient mechanism by which the enveloping cell layer (EVL) releases anisotropic tension while undergoing spreading during zebrafish epiboly. The control of EVL cell-division orientation by tension involves cell elongation and requires myosin II activity to align the mitotic spindle with the main tension axis. We also found that in the absence of tension-oriented cell divisions and in the presence of increased tissue tension, EVL cells undergo ectopic fusions, suggesting that the reduction of tension anisotropy by oriented cell divisions is required to prevent EVL cells from fusing. We conclude that cell-division orientation by tension constitutes a key mechanism for limiting tension anisotropy and thus promoting tissue spreading during EVL epiboly.
AU - Campinho, Pedro
AU - Behrndt, Martin
AU - Ranft, Jonas
AU - Risler, Thomas
AU - Minc, Nicolas
AU - Heisenberg, Carl-Philipp J
ID - 2282
JF - Nature Cell Biology
TI - Tension-oriented cell divisions limit anisotropic tissue tension in epithelial spreading during zebrafish epiboly
VL - 15
ER -