TY - CONF
AB - We introduce the idea of using an explicit triangle mesh to track the air/fluid interface in a smoothed particle hydrodynamics (SPH) simulator. Once an initial surface mesh is created, this mesh is carried forward in time using nearby particle velocities to advect the mesh vertices. The mesh connectivity remains mostly unchanged across time-steps; it is only modified locally for topology change events or for the improvement of triangle quality. In order to ensure that the surface mesh does not diverge from the underlying particle simulation, we periodically project the mesh surface onto an implicit surface defined by the physics simulation. The mesh surface gives us several advantages over previous SPH surface tracking techniques. We demonstrate a new method for surface tension calculations that clearly outperforms the state of the art in SPH surface tension for computer graphics. We also demonstrate a method for tracking detailed surface information (like colors) that is less susceptible to numerical diffusion than competing techniques. Finally, our temporally-coherent surface mesh allows us to simulate high-resolution surface wave dynamics without being limited by the particle resolution of the SPH simulation.
AU - Yu, Jihun
AU - Wojtan, Christopher J
AU - Turk, Greg
AU - Yap, Chee
ID - 3123
IS - 2
T2 - Computer Graphics Forum
TI - Explicit mesh surfaces for particle based fluids
VL - 31
ER -
TY - CONF
AB - We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.
AU - Korc, Filip
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 3124
TI - Approximating marginals using discrete energy minimization
ER -
TY - CONF
AB - We propose a new learning method to infer a mid-level feature representation that combines the advantage of semantic attribute representations with the higher expressive power of non-semantic features. The idea lies in augmenting an existing attribute-based representation with additional dimensions for which an autoencoder model is coupled with a large-margin principle. This construction allows a smooth transition between the zero-shot regime with no training example, the unsupervised regime with training examples but without class labels, and the supervised regime with training examples and with class labels. The resulting optimization problem can be solved efficiently, because several of the necessity steps have closed-form solutions. Through extensive experiments we show that the augmented representation achieves better results in terms of object categorization accuracy than the semantic representation alone.
AU - Sharmanska, Viktoriia
AU - Quadrianto, Novi
AU - Lampert, Christoph
ID - 3125
IS - PART 5
TI - Augmented attribute representations
VL - 7576
ER -
TY - CONF
AB - When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques.
We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations.
AU - Quadrianto, Novi
AU - Lampert, Christoph
AU - Chen, Chao
ID - 3127
T2 - Proceedings of the 29th International Conference on Machine Learning
TI - The most persistent soft-clique in a set of sampled graphs
ER -
TY - JOUR
AB - We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational).
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
ID - 3128
IS - 2
JF - Formal Methods in System Design
TI - A survey of partial-observation stochastic parity games
VL - 43
ER -
TY - CONF
AB - Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n ω ) time, where n is the size of K and ω < 2.376 is a quantity so that two n×n matrices can be multiplied in O(n ω ) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently.
Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H1(K) , we improve the previously known time complexity from O(n 4) to O(n ω + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n ω ) + 2 O(g) n 2logn time using annotations.
AU - Busaryev, Oleksiy
AU - Cabello, Sergio
AU - Chen, Chao
AU - Dey, Tamal
AU - Wang, Yusu
ID - 3129
TI - Annotating simplices with a homology basis and its applications
VL - 7357
ER -
TY - JOUR
AB - Essential genes code for fundamental cellular functions required for the viability of an organism. For this reason, essential genes are often highly conserved across organisms. However, this is not always the case: orthologues of genes that are essential in one organism are sometimes not essential in other organisms or are absent from their genomes. This suggests that, in the course of evolution, essential genes can be rendered nonessential. How can a gene become non-essential? Here we used genetic manipulation to deplete the products of 26 different essential genes in Escherichia coli. This depletion results in a lethal phenotype, which could often be rescued by the overexpression of a non-homologous, non-essential gene, most likely through replacement of the essential function. We also show that, in a smaller number of cases, the essential genes can be fully deleted from the genome, suggesting that complete functional replacement is possible. Finally, we show that essential genes whose function can be replaced in the laboratory are more likely to be non-essential or not present in other taxa. These results are consistent with the notion that patterns of evolutionary conservation of essential genes are influenced by their compensability-that is, by how easily they can be functionally replaced, for example through increased expression of other genes.
AU - Bergmiller, Tobias
AU - Ackermann, Martin
AU - Silander, Olin
ID - 3130
IS - 6
JF - PLoS Genetics
TI - Patterns of evolutionary conservation of essential genes correlate with their compensability
VL - 8
ER -
TY - JOUR
AB - In large populations, many beneficial mutations may be simultaneously available and may compete with one another, slowing adaptation. By finding the probability of fixation of a favorable allele in a simple model of a haploid sexual population, we find limits to the rate of adaptive substitution, Λ, that depend on simple parameter combinations. When variance in fitness is low and linkage is loose, the baseline rate of substitution is Λ 0=2NU〈s〉 is the population size, U is the rate of beneficial mutations per genome, and 〈s〉 is their mean selective advantage. Heritable variance ν in log fitness due to unlinked loci reduces Λ by e -4ν under polygamy and e -8ν under monogamy. With a linear genetic map of length R Morgans, interference is yet stronger. We use a scaling argument to show that the density of adaptive substitutions depends on s, N, U, and R only through the baseline density: Λ/R=F(Λ 0/R). Under the approximation that the interference due to different sweeps adds up, we show that Λ/R~(Λ 0/R)/(1+2Λ 0/R), implying that interference prevents the rate of adaptive substitution from exceeding one per centimorgan per 200 generations. Simulations and numerical calculations confirm the scaling argument and confirm the additive approximation for Λ 0/R 1; for higher Λ 0/R, the rate of adaptation grows above R/2, but only very slowly. We also consider the effect of sweeps on neutral diversity and show that, while even occasional sweeps can greatly reduce neutral diversity, this effect saturates as sweeps become more common-diversity can be maintained even in populations experiencing very strong interference. Our results indicate that for some organisms the rate of adaptive substitution may be primarily recombination-limited, depending only weakly on the mutation supply and the strength of selection.
AU - Weissman, Daniel
AU - Barton, Nicholas H
ID - 3131
IS - 6
JF - PLoS Genetics
TI - Limits to the rate of adaptive substitution in sexual populations
VL - 8
ER -
TY - CONF
AB - This note contributes to the point calculus of persistent homology by extending Alexander duality from spaces to real-valued functions. Given a perfect Morse function f: S n+1 →[0, 1 and a decomposition S n+1 = U ∪ V into two (n + 1)-manifolds with common boundary M, we prove elementary relationships between the persistence diagrams of f restricted to U, to V, and to M.
AU - Edelsbrunner, Herbert
AU - Kerber, Michael
ID - 3133
T2 - Proceedings of the twenty-eighth annual symposium on Computational geometry
TI - Alexander duality for functions: The persistent behavior of land and water and shore
ER -
TY - CONF
AB - We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates.
AU - Brázdil, Brázdil
AU - Chatterjee, Krishnendu
AU - Kučera, Antonín
AU - Novotny, Petr
ID - 3135
TI - Efficient controller synthesis for consumption games with multiple resource types
VL - 7358
ER -
TY - CONF
AB - We propose synchronous interfaces, a new interface theory for discrete-time systems. We use an application to time-triggered scheduling to drive the design choices for our formalism; in particular, additionally to deriving useful mathematical properties, we focus on providing a syntax which is adapted to natural high-level system modeling. As a result, we develop an interface model that relies on a guarded-command based language and is equipped with shared variables and explicit discrete-time clocks. We define all standard interface operations: compatibility checking, composition, refinement, and shared refinement. Apart from the synchronous interface model, the contribution of this paper is the establishment of a formal relation between interface theories and real-time scheduling, where we demonstrate a fully automatic framework for the incremental computation of time-triggered schedules.
AU - Delahaye, Benoît
AU - Fahrenberg, Uli
AU - Henzinger, Thomas A
AU - Legay, Axel
AU - Nickovic, Dejan
ID - 3155
TI - Synchronous interface theories and time triggered scheduling
VL - 7273
ER -
TY - JOUR
AB - Colorectal tumours that are wild type for KRAS are often sensitive to EGFR blockade, but almost always develop resistance within several months of initiating therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies are largely unknown. This situation is in marked contrast to that of small-molecule targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations in the genes encoding the protein targets render the tumours resistant to the effects of the drugs. The simplest hypothesis to account for the development of resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis would seem readily testable, there is no evidence in pre-clinical models to support it, nor is there data from patients. To test this hypothesis, we determined whether mutant KRAS DNA could be detected in the circulation of 28 patients receiving monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that 9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed detectable mutations in KRAS in their sera, three of which developed multiple different KRAS mutations. The appearance of these mutations was very consistent, generally occurring between 5 and 6months following treatment. Mathematical modelling indicated that the mutations were present in expanded subclones before the initiation of panitumumab treatment. These results suggest that the emergence of KRAS mutations is a mediator of acquired resistance to EGFR blockade and that these mutations can be detected in a non-invasive manner. They explain why solid tumours develop resistance to targeted therapies in a highly reproducible fashion.
AU - Diaz Jr, Luis
AU - Williams, Richard
AU - Wu, Jian
AU - Kinde, Isaac
AU - Hecht, Joel
AU - Berlin, Jordan
AU - Allen, Benjamin
AU - Božić, Ivana
AU - Reiter, Johannes
AU - Nowak, Martin
AU - Kinzler, Kenneth
AU - Oliner, Kelly
AU - Vogelstein, Bert
ID - 3157
IS - 7404
JF - Nature
TI - The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers
VL - 486
ER -
TY - JOUR
AB - We describe here the development and characterization of a conditionally inducible mouse model expressing Lifeact-GFP, a peptide that reports the dynamics of filamentous actin. We have used this model to study platelets, megakaryocytes and melanoblasts and we provide evidence that Lifeact-GFP is a useful reporter in these cell types ex vivo. In the case of platelets and megakaryocytes, these cells are not transfectable by traditional methods, so conditional activation of Lifeact allows the study of actin dynamics in these cells live. We studied melanoblasts in native skin explants from embryos, allowing the visualization of live actin dynamics during cytokinesis and migration. Our study revealed that melanoblasts lacking the small GTPase Rac1 show a delay in the formation of new pseudopodia following cytokinesis that accounts for the previously reported cytokinesis delay in these cells. Thus, through use of this mouse model, we were able to gain insights into the actin dynamics of cells that could only previously be studied using fixed specimens or following isolation from their native tissue environment.
AU - Schachtner, Hannah
AU - Li, Ang
AU - Stevenson, David
AU - Calaminus, Simon
AU - Thomas, Steven
AU - Watson, Steve
AU - Sixt, Michael K
AU - Wedlich Söldner, Roland
AU - Strathdee, Douglas
AU - Machesky, Laura
ID - 3158
IS - 11-12
JF - European Journal of Cell Biology
TI - Tissue inducible Lifeact expression allows visualization of actin dynamics in vivo and ex vivo
VL - 91
ER -
TY - JOUR
AB - The structure of hierarchical networks in biological and physical systems has long been characterized using the Horton-Strahler ordering scheme. The scheme assigns an integer order to each edge in the network based on the topology of branching such that the order increases from distal parts of the network (e.g., mountain streams or capillaries) to the "root" of the network (e.g., the river outlet or the aorta). However, Horton-Strahler ordering cannot be applied to networks with loops because they they create a contradiction in the edge ordering in terms of which edge precedes another in the hierarchy. Here, we present a generalization of the Horton-Strahler order to weighted planar reticular networks, where weights are assumed to correlate with the importance of network edges, e.g., weights estimated from edge widths may correlate to flow capacity. Our method assigns hierarchical levels not only to edges of the network, but also to its loops, and classifies the edges into reticular edges, which are responsible for loop formation, and tree edges. In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations. In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges. We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.
AU - Mileyko, Yuriy
AU - Edelsbrunner, Herbert
AU - Price, Charles
AU - Weitz, Joshua
ID - 3159
IS - 6
JF - PLoS One
TI - Hierarchical ordering of reticular networks
VL - 7
ER -
TY - JOUR
AB - Some inflammatory stimuli trigger activation of the NLRP3 inflammasome by inducing efflux of cellular potassium. Loss of cellular potassium is known to potently suppress protein synthesis, leading us to test whether the inhibition of protein synthesis itself serves as an activating signal for the NLRP3 inflammasome. Murine bone marrow-derived macrophages, either primed by LPS or unprimed, were exposed to a panel of inhibitors of ribosomal function: ricin, cycloheximide, puromycin, pactamycin, and anisomycin. Macrophages were also exposed to nigericin, ATP, monosodium urate (MSU), and poly I:C. Synthesis of pro-IL-ß and release of IL-1ß from cells in response to these agents was detected by immunoblotting and ELISA. Release of intracellular potassium was measured by mass spectrometry. Inhibition of translation by each of the tested translation inhibitors led to processing of IL-1ß, which was released from cells. Processing and release of IL-1ß was reduced or absent from cells deficient in NLRP3, ASC, or caspase-1, demonstrating the role of the NLRP3 inflammasome. Despite the inability of these inhibitors to trigger efflux of intracellular potassium, the addition of high extracellular potassium suppressed activation of the NLRP3 inflammasome. MSU and double-stranded RNA, which are known to activate the NLRP3 inflammasome, also substantially inhibited protein translation, supporting a close association between inhibition of translation and inflammasome activation. These data demonstrate that translational inhibition itself constitutes a heretofore-unrecognized mechanism underlying IL-1ß dependent inflammatory signaling and that other physical, chemical, or pathogen-associated agents that impair translation may lead to IL-1ß-dependent inflammation through activation of the NLRP3 inflammasome. For agents that inhibit translation through decreased cellular potassium, the application of high extracellular potassium restores protein translation and suppresses activation of the NLRP inflammasome. For agents that inhibit translation through mechanisms that do not involve loss of potassium, high extracellular potassium suppresses IL-1ß processing through a mechanism that remains undefined.
AU - Vyleta, Meghan
AU - Wong, John
AU - Magun, Bruce
ID - 3161
IS - 5
JF - PLoS One
TI - Suppression of ribosomal function triggers innate immune signaling through activation of the NLRP3 inflammasome
VL - 7
ER -
TY - CONF
AB - Given a dense-time real-valued signal and a parameterized temporal logic formula with both magnitude and timing parameters, we compute the subset of the parameter space that renders the formula satisfied by the trace. We provide two preliminary implementations, one which follows the exact semantics and attempts to compute the validity domain by quantifier elimination in linear arithmetics and one which conducts adaptive search in the parameter space.
AU - Asarin, Eugene
AU - Donzé, Alexandre
AU - Maler, Oded
AU - Nickovic, Dejan
ID - 3162
TI - Parametric identification of temporal properties
VL - 7186
ER -
TY - JOUR
AB - There is evidence that the genetic code was established prior to the existence of proteins, when metabolism was powered by ribozymes. Also, early proto-organisms had to rely on simple anaerobic bioenergetic processes. In this work I propose that amino acid fermentation powered metabolism in the RNA world, and that this was facilitated by proto-adapters, the precursors of the tRNAs. Amino acids were used as carbon sources rather than as catalytic or structural elements. In modern bacteria, amino acid fermentation is known as the Stickland reaction. This pathway involves two amino acids: the first undergoes oxidative deamination, and the second acts as an electron acceptor through reductive deamination. This redox reaction results in two keto acids that are employed to synthesise ATP via substrate-level phosphorylation. The Stickland reaction is the basic bioenergetic pathway of some bacteria of the genus Clostridium. Two other facts support Stickland fermentation in the RNA world. First, several Stickland amino acid pairs are synthesised in abiotic amino acid synthesis. This suggests that amino acids that could be used as an energy substrate were freely available. Second, anticodons that have complementary sequences often correspond to amino acids that form Stickland pairs. The main hypothesis of this paper is that pairs of complementary proto-adapters were assigned to Stickland amino acids pairs. There are signatures of this hypothesis in the genetic code. Furthermore, it is argued that the proto-adapters formed double strands that brought amino acid pairs into proximity to facilitate their mutual redox reaction, structurally constraining the anticodon pairs that are assigned to these amino acid pairs. Significance tests which randomise the code are performed to study the extent of the variability of the energetic (ATP) yield. Random assignments can lead to a substantial yield of ATP and maintain enough variability, thus selection can act and refine the assignments into a proto-code that optimises the energetic yield. Monte Carlo simulations are performed to evaluate the establishment of these simple proto-codes, based on amino acid substitutions and codon swapping. In all cases, donor amino acids are assigned to anticodons composed of U+G, and have low redundancy (1-2 codons), whereas acceptor amino acids are assigned to the the remaining codons. These bioenergetic and structural constraints allow for a metabolic role for amino acids before their co-option as catalyst cofactors. Reviewers: this article was reviewed by Prof. William Martin, Prof. Eors Szathmary (nominated by Dr. Gaspar Jekely) and Dr. Adam Kun (nominated by Dr. Sandor Pongor)
AU - Vladar, Harold
ID - 3166
JF - Biology Direct
TI - Amino acid fermentation at the origin of the genetic code
VL - 7
ER -
TY - JOUR
AB - We describe RTblob, a high speed vision system that detects objects in cluttered scenes based on their color and shape at a speed of over 800 frames/s. Because the system is available as open-source software and relies only on off-the-shelf PC hardware components, it can provide the basis for multiple application scenarios. As an illustrative example, we show how RTblob can be used in a robotic table tennis scenario to estimate ball trajectories through 3D space simultaneously from four cameras images at a speed of 200 Hz.
AU - Lampert, Christoph
AU - Peters, Jan
ID - 3248
IS - 1
JF - Journal of Real-Time Image Processing
TI - Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components
VL - 7
ER -
TY - CONF
AB - We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents, the trusted third party (TTP) and the protocols as path formulas in Linear Temporal Logic (LTL) and prove that the satisfaction of the objectives of the agents and the TTP imply satisfaction of the protocol objectives. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail in synthesizing these protocols, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee synthesis is attack-free; no subset of participants can violate the objectives of the other participants without violating their own objectives; (b) the Asokan-Shoup-Waidner (ASW) certified mail protocol that has known vulnerabilities is not a solution of AGS; and (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution of AGS. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can generate correct protocols and automatically discover vulnerabilities. The solution to assume-guarantee synthesis can be computed efficiently as the secure equilibrium solution of three-player graph games. © 2012 Springer-Verlag.
AU - Chatterjee, Krishnendu
AU - Raman, Vishwanath
ID - 3252
TI - Synthesizing protocols for digital contract signing
VL - 7148
ER -
TY - CONF
AB - In this paper we survey results of two-player games on graphs and Markov decision processes with parity, mean-payoff and energy objectives, and the combination of mean-payoff and energy objectives with parity objectives. These problems have applications in verification and synthesis of reactive systems in resource-constrained environments.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 3255
TI - Games and Markov decision processes with mean payoff parity and energy parity objectives
VL - 7119
ER -
TY - JOUR
AB - We use a distortion to define the dual complex of a cubical subdivision of ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝ n.
AU - Edelsbrunner, Herbert
AU - Kerber, Michael
ID - 3256
IS - 2
JF - Discrete & Computational Geometry
TI - Dual complexes of cubical subdivisions of ℝn
VL - 47
ER -
TY - JOUR
AB - Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms.
AU - Kolmogorov, Vladimir
ID - 3257
IS - 4-5
JF - Discrete Applied Mathematics
TI - Generalized roof duality and bisubmodular functions
VL - 160
ER -
TY - JOUR
AB - CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. It is generally thought that proximal synapses from the mossy fibers activate these neurons most efficiently, whereas distal inputs from the perforant path have a weaker modulatory influence. We used confocally targeted patch-clamp recording from dendrites and axons to map the activation of rat CA3 pyramidal neurons at the subcellular level. Our results reveal two distinct dendritic domains. In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+ channel–mediated dendritic spikes are efficiently initiated by waveforms mimicking synaptic events. CA3 pyramidal neuron dendrites showed a high Na+-to-K+ conductance density ratio, providing ideal conditions for active backpropagation and dendritic spike initiation. Dendritic spikes may enhance the computational power of CA3 pyramidal neurons in the hippocampal network.
AU - Kim, Sooyun
AU - Guzmán, José
AU - Hu, Hua
AU - Jonas, Peter M
ID - 3258
IS - 4
JF - Nature Neuroscience
TI - Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons
VL - 15
ER -
TY - JOUR
AB - Many scenarios in the living world, where individual organisms compete for winning positions (or resources), have properties of auctions. Here we study the evolution of bids in biological auctions. For each auction, n individuals are drawn at random from a population of size N. Each individual makes a bid which entails a cost. The winner obtains a benefit of a certain value. Costs and benefits are translated into reproductive success (fitness). Therefore, successful bidding strategies spread in the population. We compare two types of auctions. In “biological all-pay auctions”, the costs are the bid for every participating individual. In “biological second price all-pay auctions”, the cost for everyone other than the winner is the bid, but the cost for the winner is the second highest bid. Second price all-pay auctions are generalizations of the “war of attrition” introduced by Maynard Smith. We study evolutionary dynamics in both types of auctions. We calculate pairwise invasion plots and evolutionarily stable distributions over the continuous strategy space. We find that the average bid in second price all-pay auctions is higher than in all-pay auctions, but the average cost for the winner is similar in both auctions. In both cases, the average bid is a declining function of the number of participants, n. The more individuals participate in an auction the smaller is the chance of winning, and thus expensive bids must be avoided.
AU - Chatterjee, Krishnendu
AU - Reiter, Johannes
AU - Nowak, Martin
ID - 3260
IS - 1
JF - Theoretical Population Biology
TI - Evolutionary dynamics of biological auctions
VL - 81
ER -
TY - JOUR
AB - Living cells must control the reading out or "expression" of information encoded in their genomes, and this regulation often is mediated by transcription factors--proteins that bind to DNA and either enhance or repress the expression of nearby genes. But the expression of transcription factor proteins is itself regulated, and many transcription factors regulate their own expression in addition to responding to other input signals. Here we analyze the simplest of such self-regulatory circuits, asking how parameters can be chosen to optimize information transmission from inputs to outputs in the steady state. Some nonzero level of self-regulation is almost always optimal, with self-activation dominant when transcription factor concentrations are low and self-repression dominant when concentrations are high. In steady state the optimal self-activation is never strong enough to induce bistability, although there is a limit in which the optimal parameters are very close to the critical point.
AU - Tkacik, Gasper
AU - Walczak, Aleksandra
AU - Bialek, William
ID - 3262
IS - 4
JF - Physical Review E statistical nonlinear and soft matter physics
TI - Optimizing information flow in small genetic networks. III. A self-interacting gene
VL - 85
ER -
TY - CONF
AB - The (decisional) learning with errors problem (LWE) asks to distinguish "noisy" inner products of a secret vector with random vectors from uniform. The learning parities with noise problem (LPN) is the special case where the elements of the vectors are bits. In recent years, the LWE and LPN problems have found many applications in cryptography. In this paper we introduce a (seemingly) much stronger adaptive assumption, called "subspace LWE" (SLWE), where the adversary can learn the inner product of the secret and random vectors after they were projected into an adaptively and adversarially chosen subspace. We prove that, surprisingly, the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE using secrets of length d (the other direction is trivial.) This result immediately implies that several existing cryptosystems whose security is based on the hardness of the LWE/LPN problems are provably secure in a much stronger sense than anticipated. As an illustrative example we show that the standard way of using LPN for symmetric CPA secure encryption is even secure against a very powerful class of related key attacks.
AU - Pietrzak, Krzysztof Z
ID - 3280
TI - Subspace LWE
VL - 7194
ER -
TY - CONF
AB - Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: We show several new probabilistic MAC constructions from a variety of general assumptions, including CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating these frameworks under concrete number theoretic assumptions, we get several schemes which are more efficient than just using a state-of-the-art PRF instantiation under the corresponding assumption. For probabilistic MACs, unlike deterministic ones, unforgeability against a chosen message attack (uf-cma ) alone does not imply security if the adversary can additionally make verification queries (uf-cmva ). We give an efficient generic transformation from any uf-cma secure MAC which is "message-hiding" into a uf-cmva secure MAC. This resolves the main open problem of Kiltz et al. from Eurocrypt'11; By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption. While all our new MAC constructions immediately give efficient actively secure, two-round symmetric-key identification schemes, we also show a very simple, three-round actively secure identification protocol from any weak PRF. In particular, the resulting protocol is much more efficient than the trivial approach of building a regular PRF from a weak PRF. © 2012 International Association for Cryptologic Research.
AU - Dodis, Yevgeniy
AU - Pietrzak, Krzysztof Z
AU - Kiltz, Eike
AU - Wichs, Daniel
ID - 3282
TI - Message authentication, revisited
VL - 7237
ER -
TY - JOUR
AB - Viral manipulation of transduction pathways associated with key cellular functions such as survival, response to microbial infection, and cytoskeleton reorganization can provide the supportive milieu for a productive infection. Here, we demonstrate that vaccinia virus (VACV) infection leads to activation of the stress-activated protein kinase (SAPK)/extracellular signal-regulated kinase (ERK) 4/7 (MKK4/7)-c-Jun N-terminal protein kinase 1/2 (JNK1/2) pathway; further, the stimulation of this pathway requires postpenetration, prereplicative events in the viral replication cycle. Although the formation of intracellular mature virus (IMV) was not affected in MKK4/7- or JNK1/2-knockout (KO) cells, we did note an accentuated deregulation of microtubule and actin network organization in infected JNK1/2-KO cells. This was followed by deregulated viral trafficking to the periphery and enhanced enveloped particle release. Furthermore, VACV infection induced alterations in the cell contractility and morphology, and cell migration was reduced in the JNK-KO cells. In addition, phosphorylation of proteins implicated with early cell contractility and cell migration, such as microtubule-associated protein 1B and paxillin, respectively, was not detected in the VACV-infected KO cells. In sum, our findings uncover a regulatory role played by the MKK4/7-JNK1/2 pathway in cytoskeleton reorganization during VACV infection.
AU - Pereira, Anna
AU - Leite, Flávia
AU - Brasil, Bruno
AU - Soares Martins, Jamaria
AU - Torres, Alice
AU - Pimenta, Paulo
AU - Souto Padrón, Thais
AU - Tranktman, Paula
AU - Ferreira, Paulo
AU - Kroon, Erna
AU - Bonjardim, Cláudio
ID - 3289
IS - 1
JF - Journal of Virology
TI - A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization
VL - 86
ER -
TY - JOUR
AB - The theory of persistent homology opens up the possibility to reason about topological features of a space or a function quantitatively and in combinatorial terms. We refer to this new angle at a classical subject within algebraic topology as a point calculus, which we present for the family of interlevel sets of a real-valued function. Our account of the subject is expository, devoid of proofs, and written for non-experts in algebraic topology.
AU - Bendich, Paul
AU - Cabello, Sergio
AU - Edelsbrunner, Herbert
ID - 3310
IS - 11
JF - Pattern Recognition Letters
TI - A point calculus for interlevel set homology
VL - 33
ER -
TY - JOUR
AB - The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant of the signalling properties of synapses in the nervous system. Recent functional analysis indicates that in some fast central synapses, transmitter release is triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors at the nanometre scale. Molecular analysis suggests that this tight coupling is generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors and various other synaptic proteins. Nanodomain coupling has several functional advantages, as it increases the efficacy, speed and energy efficiency of synaptic transmission.
AU - Eggermann, Emmanuel
AU - Bucurenciu, Iancu
AU - Goswami, Sarit
AU - Jonas, Peter M
ID - 3317
IS - 1
JF - Nature Reviews Neuroscience
TI - Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses
VL - 13
ER -
TY - JOUR
AB - Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve.
AU - Kerber, Michael
AU - Sagraloff, Michael
ID - 3331
IS - 3
JF - Journal of Symbolic Computation
TI - A worst case bound for topology computation of algebraic curves
VL - 47
ER -
TY - CONF
AB - We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).
AU - Chatterjee, Krishnendu
ID - 3341
TI - Robustness of structurally equivalent concurrent parity games
VL - 7213
ER -
TY - CONF
AB - Many infinite state systems can be seen as well-structured transition systems (WSTS), i.e., systems equipped with a well-quasi-ordering on states that is also a simulation relation. WSTS are an attractive target for formal analysis because there exist generic algorithms that decide interesting verification problems for this class. Among the most popular algorithms are acceleration-based forward analyses for computing the covering set. Termination of these algorithms can only be guaranteed for flattable WSTS. Yet, many WSTS of practical interest are not flattable and the question whether any given WSTS is flattable is itself undecidable. We therefore propose an analysis that computes the covering set and captures the essence of acceleration-based algorithms, but sacrifices precision for guaranteed termination. Our analysis is an abstract interpretation whose abstract domain builds on the ideal completion of the well-quasi-ordered state space, and a widening operator that mimics acceleration and controls the loss of precision of the analysis. We present instances of our framework for various classes of WSTS. Our experience with a prototype implementation indicates that, despite the inherent precision loss, our analysis often computes the precise covering set of the analyzed system.
AU - Zufferey, Damien
AU - Wies, Thomas
AU - Henzinger, Thomas A
ID - 3251
TI - Ideal abstractions for well structured transition systems
VL - 7148
ER -
TY - JOUR
AB - Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”).
AU - Konrad, Matthias
AU - Vyleta, Meghan
AU - Theis, Fabian
AU - Stock, Miriam
AU - Tragust, Simon
AU - Klatt, Martina
AU - Drescher, Verena
AU - Marr, Carsten
AU - Ugelvig, Line V
AU - Cremer, Sylvia
ID - 3242
IS - 4
JF - PLoS Biology
TI - Social transfer of pathogenic fungus promotes active immunisation in ant colonies
VL - 10
ER -
TY - JOUR
AB - Spontaneous release of glutamate is important for maintaining synaptic strength and controlling spike timing in the brain. Mechanisms regulating spontaneous exocytosis remain poorly understood. Extracellular calcium concentration ([Ca2+]o) regulates Ca2+ entry through voltage-activated calcium channels (VACCs) and consequently is a pivotal determinant of action potential-evoked vesicle fusion. Extracellular Ca 2+ also enhances spontaneous release, but via unknown mechanisms. Here we report that external Ca2+ triggers spontaneous glutamate release more weakly than evoked release in mouse neocortical neurons. Blockade of VACCs has no effect on the spontaneous release rate or its dependence on [Ca2+]o. Intracellular [Ca2+] slowly increases in a minority of neurons following increases in [Ca2+]o. Furthermore, the enhancement of spontaneous release by extracellular calcium is insensitive to chelation of intracellular calcium by BAPTA. Activation of the calcium-sensing receptor (CaSR), a G-protein-coupled receptor present in nerve terminals, by several specific agonists increased spontaneous glutamate release. The frequency of spontaneous synaptic transmission was decreased in CaSR mutant neurons. The concentration-effect relationship for extracellular calcium regulation of spontaneous release was well described by a combination of CaSR-dependent and CaSR-independent mechanisms. Overall these results indicate that extracellular Ca2+ does not trigger spontaneous glutamate release by simply increasing calcium influx but stimulates CaSR and thereby promotes resting spontaneous glutamate release.
AU - Vyleta, Nicholas
AU - Smith, Stephen
ID - 469
IS - 12
JF - European Journal of Neuroscience
TI - Spontaneous glutamate release is independent of calcium influx and tonically activated by the calcium-sensing receptor
VL - 31
ER -
TY - JOUR
AB - BioSig is an open source software library for biomedical signal processing. The aim of the BioSig project is to foster research in biomedical signal processing by providing free and open source software tools for many different application areas. Some of the areas where BioSig can be employed are neuroinformatics, brain-computer interfaces, neurophysiology, psychology, cardiovascular systems, and sleep research. Moreover, the analysis of biosignals such as the electroencephalogram (EEG), electrocorticogram (ECoG), electrocardiogram (ECG), electrooculogram (EOG), electromyogram (EMG), or respiration signals is a very relevant element of the BioSig project. Specifically, BioSig provides solutions for data acquisition, artifact processing, quality control, feature extraction, classification, modeling, and data visualization, to name a few. In this paper, we highlight several methods to help students and researchers to work more efficiently with biomedical signals.
AU - Schlögl, Alois
AU - Vidaurre, Carmen
AU - Sander, Tilmann
ID - 490
JF - Computational Intelligence and Neuroscience
TI - BioSig: The free and open source software library for biomedical signal processing
VL - 2011
ER -
TY - JOUR
AB - Cancer stem cells or cancer initiating cells are believed to contribute to cancer recurrence after therapy. MicroRNAs (miRNAs) are short RNA molecules with fundamental roles in gene regulation. The role of miRNAs in cancer stem cells is only poorly understood. Here, we report miRNA expression profiles of glioblastoma stem cell-containing CD133 + cell populations. We find that miR-9, miR-9 * (referred to as miR-9/9 *), miR-17 and miR-106b are highly abundant in CD133 + cells. Furthermore, inhibition of miR-9/9 * or miR-17 leads to reduced neurosphere formation and stimulates cell differentiation. Calmodulin-binding transcription activator 1 (CAMTA1) is a putative transcription factor, which induces the expression of the anti-proliferative cardiac hormone natriuretic peptide A (NPPA). We identify CAMTA1 as an miR-9/9 * and miR-17 target. CAMTA1 expression leads to reduced neurosphere formation and tumour growth in nude mice, suggesting that CAMTA1 can function as tumour suppressor. Consistently, CAMTA1 and NPPA expression correlate with patient survival. Our findings could provide a basis for novel strategies of glioblastoma therapy.
AU - Schraivogel, Daniel
AU - Weinmann, Lasse
AU - Beier, Dagmar
AU - Tabatabai, Ghazaleh
AU - Eichner, Alexander
AU - Zhu, Jia
AU - Anton, Martina
AU - Sixt, Michael K
AU - Weller, Michael
AU - Beier, Christoph
AU - Meister, Gunter
ID - 518
IS - 20
JF - EMBO Journal
TI - CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells
VL - 30
ER -
TY - JOUR
AB - Software transactional memories (STM) are described in the literature with assumptions of sequentially consistent program execution and atomicity of high level operations like read, write, and abort. However, in a realistic setting, processors use relaxed memory models to optimize hardware performance. Moreover, the atomicity of operations depends on the underlying hardware. This paper presents the first approach to verify STMs under relaxed memory models with atomicity of 32 bit loads and stores, and read-modify-write operations. We describe RML, a simple language for expressing concurrent programs. We develop a semantics of RML parametrized by a relaxed memory model. We then present our tool, FOIL, which takes as input the RML description of an STM algorithm restricted to two threads and two variables, and the description of a memory model, and automatically determines the locations of fences, which if inserted, ensure the correctness of the restricted STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and McRT STM under the memory models of sequential consistency, total store order, partial store order, and relaxed memory order for two threads and two variables. Finally, we extend the verification results for DSTM and TL2 to an arbitrary number of threads and variables by manually proving that the structural properties of STMs are satisfied at the hardware level of atomicity under the considered relaxed memory models.
AU - Guerraoui, Rachid
AU - Henzinger, Thomas A
AU - Singh, Vasu
ID - 531
IS - 3
JF - Formal Methods in System Design
TI - Verification of STM on relaxed memory models
VL - 39
ER -
TY - GEN
AB - Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is ̃O(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the ̃O(n·m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3 an earlier bound of O(min(m1.5, m·n2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika
ID - 5379
SN - 2664-1690
TI - An O(n2) time algorithm for alternating Büchi games
ER -
TY - GEN
AB - We consider 2-player games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We study concurrent games with ω-regular winning conditions specified as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite-precision; and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in O(n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms,that are obtained by characterization of the winning sets as μ-calculus formulas, are considerably more involved than those for turn-based games.
AU - Chatterjee, Krishnendu
ID - 5380
SN - 2664-1690
TI - Bounded rationality in concurrent parity games
ER -
TY - GEN
AB - In two-player finite-state stochastic games of partial obser- vation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distri- bution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or pos- itively (i.e., with positive probability), no matter the strategy of the second player.
We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two- sided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization.
Our main results for pure strategies are as follows: (1) For one-sided games with player 2 perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strate- gies are not sufficient, and present an exponential upper bound on mem- ory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algo- rithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 perfect observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and posi- tive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence re- sult exhibit serious flaws in previous results in the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 5381
SN - 2664-1690
TI - Partial-observation stochastic games: How to win when belief fails
ER -
TY - GEN
AB - We consider two-player stochastic games played on a finite state space for an infinite num- ber of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with ω-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity games with respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition func- tion is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).
AU - Chatterjee, Krishnendu
ID - 5382
SN - 2664-1690
TI - Robustness of structurally equivalent concurrent parity games
ER -
TY - GEN
AB - We present a new decidable logic called TREX for expressing constraints about imperative tree data structures. In particular, TREX supports a transitive closure operator that can express reachability constraints, which often appear in data structure invariants. We show that our logic is closed under weakest precondition computation, which enables its use for automated software verification. We further show that satisfiability of formulas in TREX is decidable in NP. The low complexity makes it an attractive alternative to more expensive logics such as monadic second-order logic (MSOL) over trees, which have been traditionally used for reasoning about tree data structures.
AU - Wies, Thomas
AU - Muñiz, Marco
AU - Kuncak, Viktor
ID - 5383
SN - 2664-1690
TI - On an efficient decision procedure for imperative tree data structures
ER -
TY - GEN
AB - We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every ε > 0 there is a word that is accepted with probability at least 1 − ε. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions.
AU - Chatterjee, Krishnendu
AU - Tracol, Mathieu
ID - 5384
SN - 2664-1690
TI - Decidable problems for probabilistic automata on infinite words
ER -
TY - GEN
AB - There is recently a significant effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions, aiming for a general and flexible framework for quantitative-oriented specifications. In the heart of quantitative objectives lies the accumulation of values along a computation. It is either the accumulated summation, as with the energy objectives, or the accumulated average, as with the mean-payoff objectives. We investigate the extension of temporal logics with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric variable of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the accumulated sum and average of the values of v from the beginning of the computation up to the current point of time. We also allow the path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an entire computation. We study the border of decidability for extensions of various temporal logics. In particular, we show that extending the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities by prefix-accumulation assertions and extending LTL with path-accumulation assertions, result in temporal logics whose model-checking problem is decidable. The extended logics allow to significantly extend the currently known energy and mean-payoff objectives. Moreover, the prefix-accumulation assertions may be refined with “controlled-accumulation”, allowing, for example, to specify constraints on the average waiting time between a request and a grant. On the negative side, we show that the fragment we point to is, in a sense, the maximal logic whose extension with prefix-accumulation assertions permits a decidable model-checking procedure. Extending a temporal logic that has the EG or EU modalities, and in particular CTL and LTL, makes the problem undecidable.
AU - Boker, Udi
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Kupferman, Orna
ID - 5385
SN - 2664-1690
TI - Temporal specifications with accumulative values
ER -
TY - GEN
AB - We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks.
AU - Chen, Chao
AU - Freedman, Daniel
AU - Lampert, Christoph
ID - 5386
SN - 2664-1690
TI - Enforcing topological constraints in random field image segmentation
ER -
TY - GEN
AB - We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 5387
SN - 2664-1690
TI - Energy and mean-payoff parity Markov decision processes
ER -
TY - JOUR
AU - Barton, Nicholas H
ID - 3778
IS - 2
JF - Heredity
TI - Estimating linkage disequilibria
VL - 106
ER -
TY - JOUR
AB - Advanced stages of Scyllarus phyllosoma larvae were collected by demersal trawling during fishery research surveys in the western Mediterranean Sea in 2003–2005. Nucleotide sequence analysis of the mitochondrial 16S rDNA gene allowed the final-stage phyllosoma of Scyllarus arctus to be identified among these larvae. Its morphology is described and illustrated. This constitutes the second complete description of a Scyllaridae phyllosoma with its specific identity being validated by molecular techniques (the first was S. pygmaeus). These results also solved a long lasting taxonomic anomaly of several species assigned to the ancient genus Phyllosoma Leach, 1814. Detailed examination indicated that the final-stage phyllosoma of S. arctus shows closer affinities with the American scyllarid Scyllarus depressus or with the Australian Scyllarus sp. b (sensu Phillips et al., 1981) than to its sympatric species S. pygmaeus.
AU - Palero, Ferran
AU - Guerao, Guillermo
AU - Clark, Paul
AU - Abello, Pere
ID - 3784
IS - 2
JF - Journal of the Marine Biological Association of the United Kingdom
TI - Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description
VL - 91
ER -
TY - CHAP
AB - We address the problem of covering ℝ n with congruent balls, while minimizing the number of balls that contain an average point. Considering the 1-parameter family of lattices defined by stretching or compressing the integer grid in diagonal direction, we give a closed formula for the covering density that depends on the distortion parameter. We observe that our family contains the thinnest lattice coverings in dimensions 2 to 5. We also consider the problem of packing congruent balls in ℝ n , for which we give a closed formula for the packing density as well. Again we observe that our family contains optimal configurations, this time densest packings in dimensions 2 and 3.
AU - Edelsbrunner, Herbert
AU - Kerber, Michael
ED - Calude, Cristian
ED - Rozenberg, Grzegorz
ED - Salomaa, Arto
ID - 3796
T2 - Rainbow of Computer Science
TI - Covering and packing with spheres by diagonal distortion in R^n
VL - 6570
ER -