@article{2849,
author = {Edelsbrunner, Herbert and Strelkova, Nataliya},
journal = {Russian Mathematical Surveys},
number = {6},
pages = {1167 -- 1168},
publisher = {IOP Publishing Ltd.},
title = {{On the configuration space of Steiner minimal trees}},
doi = {10.1070/RM2012v067n06ABEH004820},
volume = {67},
year = {2012},
}
@inproceedings{2888,
abstract = {Formal verification aims to improve the quality of hardware and software by detecting errors before they do harm. At the basis of formal verification lies the logical notion of correctness, which purports to capture whether or not a circuit or program behaves as desired. We suggest that the boolean partition into correct and incorrect systems falls short of the practical need to assess the behavior of hardware and software in a more nuanced fashion against multiple criteria.},
author = {Henzinger, Thomas A},
booktitle = {Conference proceedings MODELS 2012},
location = {Innsbruck, Austria},
pages = {1 -- 2},
publisher = {Springer},
title = {{Quantitative reactive models}},
doi = {10.1007/978-3-642-33666-9_1},
volume = {7590},
year = {2012},
}
@inproceedings{2890,
abstract = {Systems are often specified using multiple requirements on their behavior. In practice, these requirements can be contradictory. The classical approach to specification, verification, and synthesis demands more detailed specifications that resolve any contradictions in the requirements. These detailed specifications are usually large, cumbersome, and hard to maintain or modify. In contrast, quantitative frameworks allow the formalization of the intuitive idea that what is desired is an implementation that comes "closest" to satisfying the mutually incompatible requirements, according to a measure of fit that can be defined by the requirements engineer. One flexible framework for quantifying how "well" an implementation satisfies a specification is offered by simulation distances that are parameterized by an error model. We introduce this framework, study its properties, and provide an algorithmic solution for the following quantitative synthesis question: given two (or more) behavioral requirements specified by possibly incompatible finite-state machines, and an error model, find the finite-state implementation that minimizes the maximal simulation distance to the given requirements. Furthermore, we generalize the framework to handle infinite alphabets (for example, realvalued domains). We also demonstrate how quantitative specifications based on simulation distances might lead to smaller and easier to modify specifications. Finally, we illustrate our approach using case studies on error correcting codes and scheduler synthesis.},
author = {Cerny, Pavol and Gopi, Sivakanth and Henzinger, Thomas A and Radhakrishna, Arjun and Totla, Nishant},
booktitle = {Proceedings of the tenth ACM international conference on Embedded software},
location = {Tampere, Finland},
pages = {53 -- 62},
publisher = {ACM},
title = {{Synthesis from incompatible specifications}},
doi = {10.1145/2380356.2380371},
year = {2012},
}
@inproceedings{2891,
abstract = {Quantitative automata are nondeterministic finite automata with edge weights. They value a
run by some function from the sequence of visited weights to the reals, and value a word by its
minimal/maximal run. They generalize boolean automata, and have gained much attention in
recent years. Unfortunately, important automaton classes, such as sum, discounted-sum, and
limit-average automata, cannot be determinized. Yet, the quantitative setting provides the potential
of approximate determinization. We define approximate determinization with respect to
a distance function, and investigate this potential.
We show that sum automata cannot be determinized approximately with respect to any
distance function. However, restricting to nonnegative weights allows for approximate determinization
with respect to some distance functions.
Discounted-sum automata allow for approximate determinization, as the influence of a word’s
suffix is decaying. However, the naive approach, of unfolding the automaton computations up
to a sufficient level, is shown to be doubly exponential in the discount factor. We provide an
alternative construction that is singly exponential in the discount factor, in the precision, and
in the number of states. We prove matching lower bounds, showing exponential dependency on
each of these three parameters.
Average and limit-average automata are shown to prohibit approximate determinization with
respect to any distance function, and this is the case even for two weights, 0 and 1.},
author = {Boker, Udi and Henzinger, Thomas A},
booktitle = {Leibniz International Proceedings in Informatics},
location = {Hyderabad, India},
pages = {362 -- 373},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Approximate determinization of quantitative automata}},
doi = {10.4230/LIPIcs.FSTTCS.2012.362},
volume = {18},
year = {2012},
}
@article{2902,
abstract = {We present an algorithm for simplifying linear cartographic objects and results obtained with a computer program implementing this algorithm. },
author = {Edelsbrunner, Herbert and Musin, Oleg and Ukhalov, Alexey and Yakimova, Olga and Alexeev, Vladislav and Bogaevskaya, Victoriya and Gorohov, Andrey and Preobrazhenskaya, Margarita},
journal = {Modeling and Analysis of Information Systems},
number = {6},
pages = {152 -- 160},
publisher = {Technische Universität Darmstadt},
title = {{Fractal and computational geometry for generalizing cartographic objects}},
volume = {19},
year = {2012},
}
@inproceedings{2903,
abstract = {In order to enjoy a digital version of the Jordan Curve Theorem, it is common to use the closed topology for the foreground and the open topology for the background of a 2-dimensional binary image. In this paper, we introduce a single topology that enjoys this theorem for all thresholds decomposing a real-valued image into foreground and background. This topology is easy to construct and it generalizes to n-dimensional images.},
author = {Edelsbrunner, Herbert and Symonova, Olga},
location = {New Brunswick, NJ, USA },
pages = {41 -- 48},
publisher = {IEEE},
title = {{The adaptive topology of a digital image}},
doi = {10.1109/ISVD.2012.11},
year = {2012},
}
@article{2904,
abstract = {Generalized van der Corput sequences are onedimensional, infinite sequences in the unit interval. They are generated from permutations in integer base b and are the building blocks of the multi-dimensional Halton sequences. Motivated by recent progress of Atanassov on the uniform distribution behavior of Halton sequences, we study, among others, permutations of the form P(i) = ai (mod b) for coprime integers a and b. We show that multipliers a that either divide b - 1 or b + 1 generate van der Corput sequences with weak distribution properties. We give explicit lower bounds for the asymptotic distribution behavior of these sequences and relate them to sequences generated from the identity permutation in smaller bases, which are, due to Faure, the weakest distributed generalized van der Corput sequences.},
author = {Pausinger, Florian},
issn = {2118-8572},
journal = {Journal de Theorie des Nombres des Bordeaux},
number = {3},
pages = {729 -- 749},
publisher = {Universite de Bordeaux},
title = {{Weak multipliers for generalized van der Corput sequences}},
doi = {10.5802/jtnb.819},
volume = {24},
year = {2012},
}
@article{2912,
author = {Edelsbrunner, Herbert and Strelkova, Nataliya},
journal = { Uspekhi Mat. Nauk},
number = {6},
pages = {203 -- 204},
publisher = {Moscow Mathematical Society },
title = {{Configuration space for shortest networks }},
doi = {10.4213/rm9503},
volume = {67},
year = {2012},
}
@inproceedings{2915,
author = {Kroemer, Oliver and Lampert, Christoph and Peters, Jan},
publisher = {Deutsches Zentrum für Luft und Raumfahrt},
title = {{Multi-modal learning for dynamic tactile sensing}},
year = {2012},
}
@inproceedings{2916,
abstract = {The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a quantitative measure for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intu- itively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, and that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.},
author = {Cerny, Pavol and Chmelik, Martin and Henzinger, Thomas A and Radhakrishna, Arjun},
booktitle = {Electronic Proceedings in Theoretical Computer Science},
location = {Napoli, Italy},
pages = {29 -- 42},
publisher = {EPTCS},
title = {{Interface Simulation Distances}},
doi = {10.4204/EPTCS.96.3},
volume = {96},
year = {2012},
}
@article{2917,
abstract = {The search for extra-terrestrial intelligence (SETI) has been performed principally as a one-way survey, listening of radio frequencies across the Milky Way and other galaxies. However, scientists have engaged in an active messaging only rarely. This suggests the simple rationale that if other civilizations exist and take a similar approach to ours, namely listening but not broadcasting, the result is a silent universe. A simple game theoretical model, the prisoner's dilemma, explains this situation: each player (civilization) can passively search (defect), or actively search and broadcast (cooperate). In order to maximize the payoff (or, equivalently, minimize the risks) the best strategy is not to broadcast. In fact, the active search has been opposed on the basis that it might be dangerous to expose ourselves. However, most of these ideas have not been based on objective arguments, and ignore accounting of the possible gains and losses. Thus, the question stands: should we perform an active search? I develop a game-theoretical framework where civilizations can be of different types, and explicitly apply it to a situation where societies are either interested in establishing a two-way communication or belligerent and in urge to exploit ours. The framework gives a quantitative solution (a mixed-strategy), which is how frequent we should perform the active SETI. This frequency is roughly proportional to the inverse of the risk, and can be extremely small. However, given the immense amount of stars being scanned, it supports active SETI. The model is compared with simulations, and the possible actions are evaluated through the San Marino scale, measuring the risks of messaging.},
author = {Vladar, Harold},
journal = {International Journal of Astrobiology},
number = {1},
pages = {53 -- 62},
publisher = {Cambridge University Press},
title = {{The game of active search for extra terrestrial intelligence Breaking the Great Silence }},
doi = {10.1017/S1473550412000407},
volume = {12},
year = {2012},
}
@unpublished{2928,
abstract = { This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. },
author = {Kolmogorov, Vladimir and Schoenemann, Thomas},
booktitle = {arXiv},
pages = {16},
publisher = {ArXiv},
title = {{Generalized sequential tree-reweighted message passing}},
year = {2012},
}
@inproceedings{2930,
abstract = {In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively.
In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.
},
author = {Huber, Anna and Kolmogorov, Vladimir},
location = {Athens, Greece},
pages = {451 -- 462},
publisher = {Springer},
title = {{Towards minimizing k-submodular functions}},
doi = {10.1007/978-3-642-32147-4_40},
volume = {7422},
year = {2012},
}
@article{2931,
abstract = {In this paper, we present a new approach for establishing correspondences between sparse image features related by an unknown nonrigid mapping and corrupted by clutter and occlusion, such as points extracted from images of different instances of the same object category. We formulate this matching task as an energy minimization problem by defining an elaborate objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general an NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples, DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods.
},
author = {Torresani, Lorenzo and Kolmogorov, Vladimir and Rother, Carsten},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
number = {2},
pages = {259 -- 271},
publisher = {IEEE},
title = {{A dual decomposition approach to feature correspondence}},
doi = {10.1109/TPAMI.2012.105},
volume = {35},
year = {2012},
}
@inproceedings{2936,
abstract = {The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce automata with delay blocks (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete. Copyright 2012 ACM.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak},
booktitle = {roceedings of the tenth ACM international conference on Embedded software},
location = {Tampere, Finland},
pages = {43 -- 52},
publisher = {ACM},
title = {{Finite automata with time delay blocks}},
doi = {10.1145/2380356.2380370},
year = {2012},
}
@inproceedings{2937,
abstract = {Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.},
author = {Almeida, José and Barbosa, Manuel and Bangerter, Endre and Barthe, Gilles and Krenn, Stephan and Béguelin, Santiago},
booktitle = {Proceedings of the 2012 ACM conference on Computer and communications security},
location = {Raleigh, NC, USA},
pages = {488 -- 500},
publisher = {ACM},
title = {{Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols}},
doi = {10.1145/2382196.2382249},
year = {2012},
}
@article{2938,
abstract = {Social insects have a very high potential to become invasive pest species. Here, we explore how their social lifestyle and their interaction with parasites may contribute to this invasive success. Similar to solitary species, parasite release followed by the evolution of increased competitive ability can promote establishment of introduced social insect hosts in their introduced range. Genetic bottlenecks during introduction of low numbers of founder individuals decrease the genetic diversity at three levels: the population, the colony and the individual, with the colony level being specific to social insects. Reduced genetic diversity can affect both the individual immune system and the collective colony-level disease defences (social immunity). Still, the dual immune system is likely to make social insects more robust to parasite attack. Changes in social structure from small, family-based, territorially aggressive societies in native populations towards huge networks of cooperating nests (unicoloniality) occur in some invasive social insects, for example, most invasive ants and some termites. Unicoloniality is likely to affect disease dynamics in multiple ways. The free exchange of individuals within the population leads to an increased genetic heterogeneity among individuals of a single nest, thereby decreasing disease transmission. However, the multitude of reproductively active queens per colony buffers the effect of individual diseased queens and their offspring, which may result in a higher level of vertical disease transmission in unicolonial societies. Lastly, unicoloniality provides a competitive advantage over native species, allowing them to quickly become the dominant species in the habitat, which in turn selects for parasite adaptation to this common host genotype and thus eventually a high parasite pressure. Overall, invasions by insect societies are characterized by general features applying to all introduced species, as well as idiosyncrasies that emerge from their social lifestyle. It is important to study these effects in concert to be able to develop efficient management and biocontrol strategies. © 2012 British Ecological Society.},
author = {Ugelvig, Line V and Cremer, Sylvia},
journal = {Functional Ecology},
number = {6},
pages = {1300 -- 1312},
publisher = {Wiley-Blackwell},
title = {{Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies}},
doi = {10.1111/1365-2435.12013},
volume = {26},
year = {2012},
}
@article{2941,
author = {Dolbilin, Nikolai and Edelsbrunner, Herbert and Musin, Oleg},
journal = {Russian Mathematical Surveys},
number = {4},
pages = {781 -- 783},
publisher = {IOP Publishing},
title = {{On the optimality of functionals over triangulations of Delaunay sets}},
doi = {10.1070/RM2012v067n04ABEH004807},
volume = {67},
year = {2012},
}
@inproceedings{2942,
abstract = {Interface theories provide a formal framework for component-based development of software and hardware which supports the incremental design of systems and the independent implementability of components. These capabilities are ensured through mathematical properties of the parallel composition operator and the refinement relation for components. More recently, a conjunction operation was added to interface theories in order to provide support for handling multiple viewpoints, requirements engineering, and component reuse. Unfortunately, the conjunction operator does not allow independent implementability in general. In this paper, we study conditions that need to be imposed on interface models in order to enforce independent implementability with respect to conjunction. We focus on multiple viewpoint specifications and propose a new compatibility criterion between two interfaces, which we call orthogonality. We show that orthogonal interfaces can be refined separately, while preserving both orthogonality and composability with other interfaces. We illustrate the independent implementability of different viewpoints with a FIFO buffer example.},
author = {Henzinger, Thomas A and Nickovic, Dejan},
booktitle = { Conference proceedings Monterey Workshop 2012},
location = {Oxford, UK},
pages = {380 -- 395},
publisher = {Springer},
title = {{Independent implementability of viewpoints}},
doi = {10.1007/978-3-642-34059-8_20},
volume = {7539},
year = {2012},
}
@article{2943,
abstract = {We examine whether the Escherichia coli chromosome is folded into a self-adherent nucleoprotein complex, or alternately is a confined but otherwise unconstrained self-avoiding polymer. We address this through in vivo visualization, using an inducible GFP fusion to the nucleoid-associated protein Fis to non-specifically decorate the entire chromosome. For a range of different growth conditions, the chromosome is a compact structure that does not fill the volume of the cell, and which moves from the new pole to the cell centre. During rapid growth, chromosome segregation occurs well before cell division, with daughter chromosomes coupled by a thin inter-daughter filament before complete segregation, whereas during slow growth chromosomes stay adjacent until cell division occurs. Image correlation analysis indicates that sub-nucleoid structure is stable on a 1min timescale, comparable to the timescale for redistribution time measured for GFP-Fis after photobleaching. Optical deconvolution and writhe calculation analysis indicate that the nucleoid has a large-scale coiled organization rather than being an amorphous mass. Our observations are consistent with the chromosome having a self-adherent filament organization.},
author = {Hadizadeh Yazdi, Nastaran and Guet, Calin C and Johnson, Reid and Marko, John},
journal = {Molecular Microbiology},
number = {6},
pages = {1318 -- 1333},
publisher = {Wiley-Blackwell},
title = {{Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions}},
doi = {10.1111/mmi.12071},
volume = {86},
year = {2012},
}
@article{2945,
abstract = {In search of foreign antigens, lymphocytes recirculate from the blood, through lymph nodes, into lymphatics and back to the blood. Dendritic cells also migrate to lymph nodes for optimal interaction with lymphocytes. This continuous trafficking of immune cells into and out of lymph nodes is essential for immune surveillance of foreign invaders. In this article, we review our current understanding of the functions of high endothelial venules (HEVs), stroma and lymphatics in the entry, positioning and exit of immune cells in lymph nodes during homeostasis, and we highlight the unexpected role of dendritic cells in the control of lymphocyte homing through HEVs.},
author = {Girard, Jean and Moussion, Christine and Förster, Reinhold},
journal = {Nature Reviews Immunology},
number = {11},
pages = {762 -- 773},
publisher = {Nature Publishing Group},
title = {{HEVs, lymphatics and homeostatic immune cell trafficking in lymph nodes}},
doi = {10.1038/nri3298},
volume = {12},
year = {2012},
}
@article{2946,
abstract = {MicroRNAs (miRNAs) are small noncoding RNAs that function in literally all cellular processes. miRNAs interact with Argonaute (Ago) proteins and guide them to specific target sites located in the 3′-untranslated region (3′-UTR) of target mRNAs leading to translational repression and deadenylation-induced mRNA degradation. Most miRNAs are processed from hairpin-structured precursors by the consecutive action of the RNase III enzymes Drosha and Dicer. However, processing of miR-451 is Dicer independent and cleavage is mediated by the endonuclease Ago2. Here we have characterized miR-451 sequence and structure requirements for processing as well as sorting of miRNAs into different Ago proteins. Pre-miR-451 appears to be optimized for Ago2 cleavage and changes result in reduced processing. In addition, we show that the mature miR-451 only associates with Ago2 suggesting that mature miRNAs are not exchanged between different members of the Ago protein family. Based on cloning and deep sequencing of endogenous miRNAs associated with Ago1-3, we do not find evidence for miRNA sorting in human cells. However, Ago identity appears to influence the length of some miRNAs, while others remain unaffected.},
author = {Dueck, Anne and Ziegler, Christian and Eichner, Alexander and Berezikov, Eugène and Meister, Gunter},
journal = {Nucleic Acids Research},
number = {19},
pages = {9850 -- 9862},
publisher = {Oxford University Press},
title = {{MicroRNAs associated with the different human Argonaute proteins}},
doi = {10.1093/nar/gks705},
volume = {40},
year = {2012},
}
@inproceedings{2947,
abstract = {We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Majumdar, Ritankar},
location = {Thiruvananthapuram, India},
pages = {385 -- 399},
publisher = {Springer},
title = {{Equivalence of games with probabilistic uncertainty and partial observation games}},
doi = {10.1007/978-3-642-33386-6_30},
volume = {7561},
year = {2012},
}
@article{2949,
author = {Dupret, David and Csicsvari, Jozsef L},
journal = {Nature Neuroscience},
number = {11},
pages = {1471 -- 1472},
publisher = {Nature Publishing Group},
title = {{The medial entorhinal cortex keeps Up}},
doi = {10.1038/nn.3245},
volume = {15},
year = {2012},
}
@article{2950,
abstract = {Contractile actomyosin rings drive various fundamental morphogenetic processes ranging from cytokinesis to wound healing. Actomyosin rings are generally thought to function by circumferential contraction. Here, we show that the spreading of the enveloping cell layer (EVL) over the yolk cell during zebrafish gastrulation is driven by a contractile actomyosin ring. In contrast to previous suggestions, we find that this ring functions not only by circumferential contraction but also by a flow-friction mechanism. This generates a pulling force through resistance against retrograde actomyosin flow. EVL spreading proceeds normally in situations where circumferential contraction is unproductive, indicating that the flow-friction mechanism is sufficient. Thus, actomyosin rings can function in epithelial morphogenesis through a combination of cable-constriction and flow-friction mechanisms.},
author = {Behrndt, Martin and Salbreux, Guillaume and Campinho, Pedro and Hauschild, Robert and Oswald, Felix and Roensch, Julia and Grill, Stephan and Heisenberg, Carl-Philipp J},
journal = {Science},
number = {6104},
pages = {257 -- 260},
publisher = {American Association for the Advancement of Science},
title = {{Forces driving epithelial spreading in zebrafish gastrulation}},
doi = {10.1126/science.1224143},
volume = {338},
year = {2012},
}
@article{2951,
abstract = {Differential cell adhesion and cortex tension are thought to drive cell sorting by controlling cell-cell contact formation. Here, we show that cell adhesion and cortex tension have different mechanical functions in controlling progenitor cell-cell contact formation and sorting during zebrafish gastrulation. Cortex tension controls cell-cell contact expansion by modulating interfacial tension at the contact. By contrast, adhesion has little direct function in contact expansion, but instead is needed to mechanically couple the cortices of adhering cells at their contacts, allowing cortex tension to control contact expansion. The coupling function of adhesion is mediated by E-cadherin and limited by the mechanical anchoring of E-cadherin to the cortex. Thus, cell adhesion provides the mechanical scaffold for cell cortex tension to drive cell sorting during gastrulation.},
author = {Maître, Jean-Léon and Berthoumieux, Hélène and Krens, Gabriel and Salbreux, Guillaume and Julicher, Frank and Paluch, Ewa and Heisenberg, Carl-Philipp J},
journal = {Science},
number = {6104},
pages = {253 -- 256},
publisher = {American Association for the Advancement of Science},
title = {{Adhesion functions in cell sorting by mechanically coupling the cortices of adhering cells}},
doi = {10.1126/science.1225399},
volume = {338},
year = {2012},
}
@article{2952,
abstract = {Body axis elongation represents a common and fundamental morphogenetic process in development. A key mechanism triggering body axis elongation without additional growth is convergent extension (CE), whereby a tissue undergoes simultaneous narrowing and extension. Both collective cell migration and cell intercalation are thought to drive CE and are used to different degrees in various species as they elongate their body axis. Here, we provide an overview of CE as a general strategy for body axis elongation and discuss conserved and divergent mechanisms underlying CE among different species.},
author = {Tada, Masazumi and Heisenberg, Carl-Philipp J},
journal = {Development},
number = {21},
pages = {3897 -- 3904},
publisher = {Company of Biologists},
title = {{Convergent extension Using collective cell migration and cell intercalation to shape embryos}},
doi = {10.1242/dev.073007},
volume = {139},
year = {2012},
}
@article{2953,
author = {Heisenberg, Carl-Philipp J and Fässler, Reinhard},
journal = {Current Opinion in Cell Biology},
number = {5},
pages = {559 -- 561},
publisher = {Elsevier},
title = {{Cell-cell adhesion and extracellular matrix diversity counts}},
doi = {10.1016/j.ceb.2012.09.002},
volume = {24},
year = {2012},
}
@article{2954,
abstract = {Spontaneous postsynaptic currents (PSCs) provide key information about the mechanisms of synaptic transmission and the activity modes of neuronal networks. However, detecting spontaneous PSCs in vitro and in vivo has been challenging, because of the small amplitude, the variable kinetics, and the undefined time of generation of these events. Here, we describe a, to our knowledge, new method for detecting spontaneous synaptic events by deconvolution, using a template that approximates the average time course of spontaneous PSCs. A recorded PSC trace is deconvolved from the template, resulting in a series of delta-like functions. The maxima of these delta-like events are reliably detected, revealing the precise onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based method has a unique temporal resolution, allowing the detection of individual events in high-frequency bursts. Furthermore, the deconvolution-based method has a high amplitude resolution, because deconvolution can substantially increase the signal/noise ratio. When tested against previously published methods using experimental data, the deconvolution-based method was superior for spontaneous PSCs recorded in vivo. Using the high-resolution deconvolution-based detection algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro.},
author = {Pernia-Andrade, Alejandro and Goswami, Sarit and Stickler, Yvonne and Fröbe, Ulrich and Schlögl, Alois and Jonas, Peter M},
journal = {Biophysical Journal},
number = {7},
pages = {1429 -- 1439},
publisher = {Biophysical},
title = {{A deconvolution based method with high sensitivity and temporal resolution for detection of spontaneous synaptic currents in vitro and in vivo}},
doi = {10.1016/j.bpj.2012.08.039},
volume = {103},
year = {2012},
}
@inproceedings{2955,
abstract = {We consider two-player stochastic games played on finite graphs with reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1), or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and 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, the players (a) may not be allowed to use randomization (pure strategies), or (b) may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) may use full randomization. Our main results for pure strategies are as follows. (1) For one-sided games with player 1 having partial observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure 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. (2) For one-sided games with player 2 having partial observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and positive 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 result exhibits serious flaws in previous results of the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
booktitle = {Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science},
location = {Dubrovnik, Croatia},
publisher = {IEEE},
title = {{Partial-observation stochastic games: How to win when belief fails}},
doi = {10.1109/LICS.2012.28},
year = {2012},
}
@inproceedings{2956,
abstract = {Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and parity objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two-player pushdown games. Finally we also show that all the problems have the same computational complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.},
author = {Chatterjee, Krishnendu and Velner, Yaron},
booktitle = {Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science},
location = {Dubrovnik, Croatia },
publisher = {IEEE},
title = {{Mean payoff pushdown games}},
doi = {10.1109/LICS.2012.30},
year = {2012},
}
@inproceedings{2957,
abstract = {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 words are accepted with probability arbitrarily close to 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 (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.},
author = {Chatterjee, Krishnendu and Tracol, Mathieu},
booktitle = {Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science},
location = {Dubrovnik, Croatia },
publisher = {IEEE},
title = {{Decidable problems for probabilistic automata on infinite words}},
doi = {10.1109/LICS.2012.29},
year = {2012},
}
@article{2958,
abstract = {The activity of hippocampal pyramidal cells reflects both the current position of the animal and information related to its current behavior. Here we investigated whether single hippocampal neurons can encode several independent features defining trials during a memory task. We also tested whether task-related information is represented by partial remapping of the place cell population or, instead, via firing rate modulation of spatially stable place cells. To address these two questions, the activity of hippocampal neurons was recorded in rats performing a conditional discrimination task on a modified T-maze in which the identity of a food reward guided behavior. When the rat was on the central arm of the maze, the firing rate of pyramidal cells changed depending on two independent factors: (1) the identity of the food reward given to the animal and (2) the previous location of the animal on the maze. Importantly, some pyramidal cells encoded information relative to both factors. This trial-type specific and retrospective coding did not interfere with the spatial representation of the maze: hippocampal cells had stable place fields and their theta-phase precession profiles were unaltered during the task, indicating that trial-related information was encoded via rate remapping. During error trials, encoding of both trial-related information and spatial location was impaired. Finally, we found that pyramidal cells also encode trial-related information via rate remapping during the continuous version of the rewarded alternation task without delays. These results suggest that hippocampal neurons can encode several task-related cognitive aspects via rate remapping.},
author = {Allen, Kevin and Rawlins, J Nick and Bannerman, David and Csicsvari, Jozsef L},
journal = {Journal of Neuroscience},
number = {42},
pages = {14752 -- 14766},
publisher = {Society for Neuroscience},
title = {{Hippocampal place cells can encode multiple trial-dependent features through rate remapping}},
doi = {10.1523/JNEUROSCI.6175-11.2012},
volume = {32},
year = {2012},
}
@article{2959,
abstract = {We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator (MLE) exists with probability one. This is applied to bipartite graphs, grids and colored graphs. We also study the ML degree, and we present the first instance of a graph for which the MLE exists with probability one, even when the number of observations equals the treewidth.},
author = {Uhler, Caroline},
journal = {Annals of Statistics},
number = {1},
pages = {238 -- 261},
publisher = {Institute of Mathematical Statistics},
title = {{Geometry of maximum likelihood estimation in Gaussian graphical models}},
doi = {10.1214/11-AOS957},
volume = {40},
year = {2012},
}
@article{2962,
abstract = {The choice of summary statistics is a crucial step in approximate Bayesian computation (ABC). Since statistics are often not sufficient, this choice involves a trade-off between loss of information and reduction of dimensionality. The latter may increase the efficiency of ABC. Here, we propose an approach for choosing summary statistics based on boosting, a technique from the machine learning literature. We consider different types of boosting and compare them to partial least squares regression as an alternative. To mitigate the lack of sufficiency, we also propose an approach for choosing summary statistics locally, in the putative neighborhood of the true parameter value. We study a demographic model motivated by the re-introduction of Alpine ibex (Capra ibex) into the Swiss Alps. The parameters of interest are the mean and standard deviation across microsatellites of the scaled ancestral mutation rate (θanc = 4 Ne u), and the proportion of males obtaining access to matings per breeding season (ω). By simulation, we assess the properties of the posterior distribution obtained with the various methods. According to our criteria, ABC with summary statistics chosen locally via boosting with the L2-loss performs best. Applying that method to the ibex data, we estimate θanc ≈ 1.288, and find that most of the variation across loci of the ancestral mutation rate u is between 7.7×10−4 and 3.5×10−3 per locus per generation. The proportion of males with access to matings is estimated to ω ≈ 0.21, which is in good agreement with recent independent estimates.},
author = {Aeschbacher, Simon and Beaumont, Mark and Futschik, Andreas},
journal = {Genetics},
number = {3},
pages = {1027 -- 1047},
publisher = {Genetics Society of America},
title = {{A novel approach for choosing summary statistics in approximate Bayesian computation}},
doi = {10.1534/genetics.112.143164},
volume = {192},
year = {2012},
}
@article{2963,
abstract = {Zebra finches are an ubiquitous model system for the study of vocal learning in animal communication. Their song has been well described, but its possible function(s) in social communication are only partly understood. The so-called ‘directed song’ is a high-intensity, high-performance song given during courtship in close proximity to the female, which is known to mediate mate choice and mating. However, this singing mode constitutes only a fraction of zebra finch males’ prolific song output. Potential communicative functions of their second, ‘undirected’ singing mode remain unresolved in the face of contradicting reports of both facilitating and inhibiting effects of social company on singing. We addressed this issue by experimentally manipulating social contexts in a within-subject design, comparing a solo versus male or female only company condition, each lasting for 24 hours. Males’ total song output was significantly higher when a conspecific was in audible and visible distance than when they were alone. Male and female company had an equally facilitating effect on song output. Our findings thus indicate that singing motivation is facilitated rather than inhibited by social company, suggesting that singing in zebra finches might function both in inter- and intrasexual communication. },
author = {Jesse, Fabienne and Riebel, Katharina},
journal = {Behavioural Processes},
number = {3},
pages = {262 -- 266},
publisher = {Elsevier},
title = {{Social facilitation of male song by male and female conspecifics in the zebra finch, Taeniopygia guttata}},
doi = {10.1016/j.beproc.2012.09.006},
volume = {91},
year = {2012},
}
@phdthesis{2964,
abstract = {CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. These neurons receive multiple excitatory inputs from numerous sources. Therefore, the rules of spatiotemporal integration of multiple synaptic inputs and propagation of action potentials are important to understand how CA3 neurons contribute to higher brain functions at cellular level. By using confocally targeted patch-clamp recording techniques, we investigated the biophysical properties of rat CA3 pyramidal neuron dendrites. We found two distinct dendritic domains critical for action potential initiation and propagation: 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 evoked by local dendritic depolarization or waveforms mimicking synaptic events. These findings can be explained by a high Na+-to-K+ conductance density ratio of CA3 pyramidal neuron dendrites. The results challenge the prevailing view that proximal mossy fiber inputs activate CA3 pyramidal neurons more efficiently than distal perforant inputs by showing that the distal synapses trigger a different form of activity represented by dendritic spikes. The high probability of dendritic spike initiation in the distal area may enhance the computational power of CA3 pyramidal neurons in the hippocampal network. },
author = {Kim, Sooyun},
pages = {65},
publisher = {IST Austria},
title = {{Active properties of hippocampal CA3 pyramidal neuron dendrites}},
year = {2012},
}
@article{2965,
abstract = {Dieser Artikel soll die sechs verschiedenen Creative Commons Lizenzen erläutern und ihre Bedeutung im Rahmen des wissenschaftlichen Publizierens und des Open Access erklären (CC-BY, CC-BY-SA, CC-BY-NC, CC-BY-ND, CC-BYNC-SA, CC-BY-NC-ND).},
author = {Danowski, Patrick},
journal = {Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen & Bibliothekare},
number = {2},
pages = {200 -- 212},
publisher = {VÖB},
title = {{Kontext Open Access: Creative Commons}},
volume = {65},
year = {2012},
}
@article{2966,
abstract = {Background: The outcome of male-male competition can be predicted from the relative fighting qualities of the opponents, which often depend on their age. In insects, freshly emerged and still sexually inactive males are morphologically indistinct from older, sexually active males. These young inactive males may thus be easy targets for older males if they cannot conceal themselves from their attacks. The ant Cardiocondyla obscurior is characterised by lethal fighting between wingless (" ergatoid" ) males. Here, we analyse for how long young males are defenceless after eclosion, and how early adult males can detect the presence of rival males.Results: We found that old ergatoid males consistently won fights against ergatoid males younger than two days. Old males did not differentiate between different types of unpigmented pupae several days before emergence, but had more frequent contact to ready-to-eclose pupae of female sexuals and winged males than of workers and ergatoid males. In rare cases, old ergatoid males displayed alleviated biting of pigmented ergatoid male pupae shortly before adult eclosion, as well as copulation attempts to dark pupae of female sexuals and winged males. Ergatoid male behaviour may be promoted by a closer similarity of the chemical profile of ready-to-eclose pupae to the profile of adults than that of young pupae several days prior to emergence.Conclusion: Young ergatoid males of C. obscurior would benefit greatly by hiding their identity from older, resident males, as they are highly vulnerable during the first two days of their adult lives. In contrast to the winged males of the same species, which are able to prevent ergatoid male attacks by chemical female mimicry, young ergatoids do not seem to be able to produce a protective chemical profile. Conflicts in male-male competition between ergatoid males of different age thus seem to be resolved in favour of the older males. This might represent selection at the colony level rather than the individual level. © 2012 Cremer et al.; licensee BioMed Central Ltd.},
author = {Cremer, Sylvia and Suefuji, Masaki and Schrempf, Alexandra and Heinze, Jürgen},
journal = {BMC Ecology},
publisher = {BioMed Central},
title = {{The dynamics of male-male competition in Cardiocondyla obscurior ants}},
doi = {10.1186/1472-6785-12-7},
volume = {12},
year = {2012},
}
@article{2967,
abstract = {For programs whose data variables range over Boolean or finite domains, program verification is decidable, and this forms the basis of recent tools for software model checking. In this article, we consider algorithmic verification of programs that use Boolean variables, and in addition, access a single read-only array whose length is potentially unbounded, and whose elements range over an unbounded data domain. We show that the reachability problem, while undecidable in general, is (1) PSPACE-complete for programs in which the array-accessing for-loops are not nested, (2) decidable for a restricted class of programs with doubly nested loops. The second result establishes connections to automata and logics defining languages over data words.},
author = {Alur, Rajeev and Cerny, Pavol and Weinstein, Scott},
journal = {ACM Transactions on Computational Logic (TOCL)},
number = {3},
publisher = {ACM},
title = {{Algorithmic analysis of array-accessing programs}},
doi = {10.1145/2287718.2287727},
volume = {13},
year = {2012},
}
@article{2968,
abstract = {Little is known about the stability of trophic relationships in complex natural communities over evolutionary timescales. Here, we use sequence data from 18 nuclear loci to reconstruct and compare the intraspecific histories of major Pleistocene refugial populations in the Middle East, the Balkans and Iberia in a guild of four Chalcid parasitoids (Cecidostiba fungosa, Cecidostiba semifascia, Hobbya stenonota and Mesopolobus amaenus) all attacking Cynipid oak galls. We develop a likelihood method to numerically estimate models of divergence between three populations from multilocus data. We investigate the power of this framework on simulated data, and-using triplet alignments of intronic loci-quantify the support for all possible divergence relationships between refugial populations in the four parasitoids. Although an East to West order of population divergence has highest support in all but one species, we cannot rule out alternative population tree topologies. Comparing the estimated times of population splits between species, we find that one species, M. amaenus, has a significantly older history than the rest of the guild and must have arrived in central Europe at least one glacial cycle prior to other guild members. This suggests that although all four species may share a common origin in the East, they expanded westwards into Europe at different times. © 2012 Blackwell Publishing Ltd.},
author = {Lohse, Konrad and Barton, Nicholas H and Melika, George and Stone, Graham},
journal = {Molecular Ecology},
number = {18},
pages = {4605 -- 4617},
publisher = {Wiley-Blackwell},
title = {{A likelihood based comparison of population histories in a parasitoid guild}},
doi = {10.1111/j.1365-294X.2012.05700.x},
volume = {21},
year = {2012},
}
@article{2969,
abstract = {The coupling between presynaptic Ca^(2+) channels and Ca^(2+) sensors of exocytosis is a key determinant of synaptic transmission. Evoked release from parvalbumin (PV)-expressing interneurons is triggered by nanodomain coupling of P/Q-type Ca^(2+) channels, whereas release from cholecystokinin (CCK)-containing interneurons is generated by microdomain coupling of N-type channels. Nanodomain coupling has several functional advantages, including speed and efficacy of transmission. One potential disadvantage is that stochastic
opening of presynaptic Ca^(2+) channels may trigger spontaneous transmitter release. We addressed this possibility in rat hippocampal
granule cells, which receive converging inputs from different inhibitory sources. Both reduction of extracellular Ca^(2+) concentration and the unselective Ca^(2+) channel blocker Cd^(2+) reduced the frequency of miniature IPSCs (mIPSCs) in granule cells by ~50%, suggesting that the opening of presynaptic Ca^(2+) channels contributes to spontaneous release. Application of the selective P/Q-type Ca^(2+) channel blocker
ω-agatoxin IVa had no detectable effects, whereas both the N-type blocker ω-conotoxin GVIa and the L-type blocker nimodipine reduced
mIPSC frequency. Furthermore, both the fast Ca^(2+) chelator BAPTA-AM and the slow chelator EGTA-AM reduced the mIPSC frequency,
suggesting that Ca^(2+)-dependent spontaneous release is triggered by microdomain rather than nanodomain coupling. The CB_(1) receptor
agonist WIN 55212-2 also decreased spontaneous release; this effect was occluded by prior application of ω-conotoxin GVIa, suggesting that a major fraction of Ca^(2+)-dependent spontaneous release was generated at the terminals of CCK-expressing interneurons. Tonic inhibition generated by spontaneous opening of presynaptic N- and L-type Ca^(2+) channels may be important for hippocampal information processing.
},
author = {Goswami, Sarit and Bucurenciu, Iancu and Jonas, Peter M},
journal = {Journal of Neuroscience},
number = {41},
pages = {14294 -- 14304},
publisher = {Society for Neuroscience},
title = {{Miniature IPSCs in hippocampal granule cells are triggered by voltage-gated Ca^(2+) channels via microdomain coupling}},
doi = {10.1523/JNEUROSCI.6104-11.2012},
volume = {32},
year = {2012},
}
@article{2970,
abstract = {Morphogen gradients regulate the patterning and growth of many tissues, hence a key question is how they are established and maintained during development. Theoretical descriptions have helped to explain how gradient shape is controlled by the rates of morphogen production, spreading and degradation. These effective rates have been measured using fluorescence recovery after photobleaching (FRAP) and photoactivation. To unravel which molecular events determine the effective rates, such tissue-level assays have been combined with genetic analysis, high-resolution assays, and models that take into account interactions with receptors, extracellular components and trafficking. Nevertheless, because of the natural and experimental data variability, and the underlying assumptions of transport models, it remains challenging to conclusively distinguish between cellular mechanisms.},
author = {Kicheva, Anna and Bollenbach, Mark Tobias and Wartlick, Ortrud and Julicher, Frank and Gonzalez Gaitan, Marcos},
journal = {Current Opinion in Genetics & Development},
number = {6},
pages = {527 -- 532},
publisher = {Elsevier},
title = {{Investigating the principles of morphogen gradient formation: from tissues to cells}},
doi = {10.1016/j.gde.2012.08.004},
volume = {22},
year = {2012},
}
@inproceedings{2971,
abstract = {We study the task of interactive semantic labeling of a segmentation hierarchy. To this end we propose a framework interleaving two components: an automatic labeling step, based on a Conditional Random Field whose dependencies are defined by the inclusion tree of the segmentation hierarchy, and an interaction step that integrates incremental input from a human user. Evaluated on two distinct datasets, the proposed interactive approach efficiently integrates human interventions and illustrates the advantages of structured prediction in an interactive framework. },
author = {Zankl, Georg and Haxhimusa, Yll and Ion, Adrian},
location = {Graz, Austria},
pages = {11 -- 20},
publisher = {Springer},
title = {{Interactive labeling of image segmentation hierarchies}},
doi = {10.1007/978-3-642-32717-9_2},
volume = {7476},
year = {2012},
}
@article{2972,
abstract = {Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objectives. Our main results are as follows: (a) exponential memory is sufficient and may be necessary for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is logspace-equivalent to the problem of deciding the winner in mean-payoff parity games, which can thus be solved in NP ∩ coNP. As a consequence we also obtain a conceptually simple algorithm to solve mean-payoff parity games.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
journal = {Theoretical Computer Science},
pages = {49 -- 60},
publisher = {Elsevier},
title = {{Energy parity games}},
doi = {10.1016/j.tcs.2012.07.038},
volume = {458},
year = {2012},
}
@inproceedings{2974,
abstract = {We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise (LPN) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a Σ-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u) for any circuit C.
To get soundness which is exponentially small in a security parameter t, and when the zero-knowledge property relies on the LPN problem with secrets of length l, our 3 round protocol has communication complexity O(t|C|l log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.},
author = {Jain, Abhishek and Krenn, Stephan and Pietrzak, Krzysztof Z and Tentes, Aris},
editor = {Wang, Xiaoyun and Sako, Kazue},
location = {Beijing, China},
pages = {663 -- 680},
publisher = {Springer},
title = {{Commitments and efficient zero knowledge proofs from learning parity with noise}},
doi = {10.1007/978-3-642-34961-4_40},
volume = {7658},
year = {2012},
}
@article{3115,
abstract = {We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.},
author = {Berberich, Eric and Halperin, Dan and Kerber, Michael and Pogalnikova, Roza},
journal = {Discrete & Computational Geometry},
number = {4},
pages = {964 -- 989},
publisher = {Springer},
title = {{Deconstructing approximate offsets}},
doi = {10.1007/s00454-012-9441-5},
volume = {48},
year = {2012},
}
@article{3117,
abstract = {We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms. A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines. We then explore in more detail Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms.},
author = {Kolmogorov, Vladimir},
journal = {Discrete Applied Mathematics},
number = {15},
pages = {2246 -- 2258},
publisher = {Elsevier},
title = {{Minimizing a sum of submodular functions}},
doi = {10.1016/j.dam.2012.05.025},
volume = {160},
year = {2012},
}
@inproceedings{3119,
abstract = {We present an approach for artist-directed animation of liquids using multiple levels of control over the simulation, ranging from the overall tracking of desired shapes to highly detailed secondary effects such as dripping streams, separating sheets of fluid, surface waves and ripples. The first portion of our technique is a volume preserving morph that allows the animator to produce a plausible fluid-like motion from a sparse set of control meshes. By rasterizing the resulting control meshes onto the simulation grid, the mesh velocities act as boundary conditions during the projection step of the fluid simulation. We can then blend this motion together with uncontrolled fluid velocities to achieve a more relaxed control over the fluid that captures natural inertial effects. Our method can produce highly detailed liquid surfaces with control over sub-grid details by using a mesh-based surface tracker on top of a coarse grid-based fluid simulation. We can create ripples and waves on the fluid surface attracting the surface mesh to the control mesh with spring-like forces and also by running a wave simulation over the surface mesh. Our video results demonstrate how our control scheme can be used to create animated characters and shapes that are made of water.
},
author = {Raveendran, Karthik and Thuerey, Nils and Wojtan, Christopher J and Turk, Greg},
booktitle = {Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation},
location = {Aire-la-Ville, Switzerland},
pages = {255 -- 264},
publisher = {ACM},
title = {{Controlling liquids using meshes}},
year = {2012},
}
@article{3120,
abstract = {We introduce a strategy based on Kustin-Miller unprojection that allows us to construct many hundreds of Gorenstein codimension 4 ideals with 9 × 16 resolutions (that is, nine equations and sixteen first syzygies). Our two basic games are called Tom and Jerry; the main application is the biregular construction of most of the anticanonically polarised Mori Fano 3-folds of Altinok's thesis. There are 115 cases whose numerical data (in effect, the Hilbert series) allow a Type I projection. In every case, at least one Tom and one Jerry construction works, providing at least two deformation families of quasismooth Fano 3-folds having the same numerics but different topology. © 2012 Copyright Foundation Compositio Mathematica.},
author = {Brown, Gavin and Kerber, Michael and Reid, Miles},
journal = {Compositio Mathematica},
number = {4},
pages = {1171 -- 1194},
publisher = {Cambridge University Press},
title = {{Fano 3 folds in codimension 4 Tom and Jerry Part I}},
doi = {10.1112/S0010437X11007226},
volume = {148},
year = {2012},
}
@article{3121,
abstract = {Voltage-activated Ca(2+) channels (VACCs) mediate Ca(2+) influx to trigger action potential-evoked neurotransmitter release, but the mechanism by which Ca(2+) regulates spontaneous transmission is unclear. We found that VACCs are the major physiological triggers for spontaneous release at mouse neocortical inhibitory synapses. Moreover, despite the absence of a synchronizing action potential, we found that spontaneous fusion of a GABA-containing vesicle required the activation of multiple tightly coupled VACCs of variable type.},
author = {Williams, Courtney and Chen, Wenyan and Lee, Chia and Yaeger, Daniel and Vyleta, Nicholas and Smith, Stephen},
journal = {Nature Neuroscience},
number = {9},
pages = {1195 -- 1197},
publisher = {Nature Publishing Group},
title = {{Coactivation of multiple tightly coupled calcium channels triggers spontaneous release of GABA}},
doi = {10.1038/nn.3162},
volume = {15},
year = {2012},
}
@article{3122,
abstract = {Since Darwin's pioneering research on plant reproductive biology (e.g. Darwin 1877), understanding the mechanisms maintaining the diverse sexual strategies of plants has remained an important challenge for evolutionary biologists. In some species, populations are sexually polymorphic and contain two or more mating morphs (sex phenotypes). Differences in morphology or phenology among the morphs influence patterns of non-random mating. In these populations, negative frequency-dependent selection arising from disassortative (intermorph) mating is usually required for the evolutionary maintenance of sexual polymorphism, but few studies have demonstrated the required patterns of non-random mating. In the current issue of Molecular Ecology, Shang (2012) make an important contribution to our understanding of how disassortative mating influences sex phenotype ratios in Acer pictum subsp. mono (painted maple), a heterodichogamous, deciduous tree of eastern China. They monitored sex expression in 97 adults and used paternity analysis of open-pollinated seed to examine disassortative mating among three sex phenotypes. Using a deterministic 'pollen transfer' model, Shang et al. present convincing evidence that differences in the degree of disassortative mating in progeny arrays of the sex phenotypes can explain their uneven frequencies in the adult population. This study provides a useful example of how the deployment of genetic markers, demographic monitoring and modelling can be integrated to investigate the maintenance of sexual diversity in plants. },
author = {Field, David and Barrett, Spencer},
journal = {Molecular Ecology},
number = {15},
pages = {3640 -- 3643},
publisher = {Wiley-Blackwell},
title = {{Disassortative mating and the maintenance of sexual polymorphism in painted maple}},
doi = {10.1111/j.1365-294X.2012.05643.x},
volume = {21},
year = {2012},
}
@inproceedings{3123,
abstract = {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.},
author = {Yu, Jihun and Wojtan, Christopher J and Turk, Greg and Yap, Chee},
booktitle = {Computer Graphics Forum},
location = {Cagliari, Sardinia, Italy},
number = {2},
pages = {815 -- 824},
publisher = {Blackwell Publishing},
title = {{Explicit mesh surfaces for particle based fluids}},
doi = {10.1111/j.1467-8659.2012.03062.x},
volume = {31},
year = {2012},
}
@inproceedings{3124,
abstract = {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.
},
author = {Korc, Filip and Kolmogorov, Vladimir and Lampert, Christoph},
location = {Edinburgh, Scotland},
publisher = {ICML},
title = {{Approximating marginals using discrete energy minimization}},
year = {2012},
}
@inproceedings{3125,
abstract = {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.},
author = {Sharmanska, Viktoriia and Quadrianto, Novi and Lampert, Christoph},
location = {Florence, Italy},
number = {PART 5},
pages = {242 -- 255},
publisher = {Springer},
title = {{Augmented attribute representations}},
doi = {10.1007/978-3-642-33715-4_18},
volume = {7576},
year = {2012},
}
@inproceedings{3126,
abstract = {In this work we propose a new information-theoretic clustering algorithm that infers cluster memberships by direct optimization of a non-parametric mutual information estimate between data distribution and cluster assignment. Although the optimization objective has a solid theoretical foundation it is hard to optimize. We propose an approximate optimization formulation that leads to an efficient algorithm with low runtime complexity. The algorithm has a single free parameter, the number of clusters to find. We demonstrate superior performance on several synthetic and real datasets.
},
author = {Müller, Andreas and Nowozin, Sebastian and Lampert, Christoph},
location = {Graz, Austria},
pages = {205 -- 215},
publisher = {Springer},
title = {{Information theoretic clustering using minimal spanning trees}},
doi = {10.1007/978-3-642-32717-9_21},
volume = {7476},
year = {2012},
}
@inproceedings{3127,
abstract = {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.},
author = {Quadrianto, Novi and Lampert, Christoph and Chen, Chao},
booktitle = {Proceedings of the 29th International Conference on Machine Learning},
location = {Edinburgh, United Kingdom},
pages = {211--218},
publisher = {Omnipress},
title = {{The most persistent soft-clique in a set of sampled graphs}},
year = {2012},
}
@article{3128,
abstract = {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). },
author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A},
journal = {Formal Methods in System Design},
number = {2},
pages = {268 -- 284},
publisher = {Springer},
title = {{A survey of partial-observation stochastic parity games}},
doi = {10.1007/s10703-012-0164-2},
volume = {43},
year = {2012},
}
@inproceedings{3129,
abstract = {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.
},
author = {Busaryev, Oleksiy and Cabello, Sergio and Chen, Chao and Dey, Tamal and Wang, Yusu},
location = {Helsinki, Finland},
pages = {189 -- 200},
publisher = {Springer},
title = {{Annotating simplices with a homology basis and its applications}},
doi = {10.1007/978-3-642-31155-0_17},
volume = {7357},
year = {2012},
}
@article{3130,
abstract = {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.},
author = {Bergmiller, Tobias and Ackermann, Martin and Silander, Olin},
journal = {PLoS Genetics},
number = {6},
publisher = {Public Library of Science},
title = {{Patterns of evolutionary conservation of essential genes correlate with their compensability}},
doi = {10.1371/journal.pgen.1002803},
volume = {8},
year = {2012},
}
@article{3131,
abstract = {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.},
author = {Weissman, Daniel and Barton, Nicholas H},
journal = {PLoS Genetics},
number = {6},
publisher = {Public Library of Science},
title = {{Limits to the rate of adaptive substitution in sexual populations}},
doi = {10.1371/journal.pgen.1002740},
volume = {8},
year = {2012},
}
@article{3132,
abstract = {Reproductive division of labour is a characteristic trait of social insects. The dominant reproductive individual, often the queen, uses chemical communication and/or behaviour to maintain her social status. Queens of many social insects communicate their fertility status via cuticle-bound substances. As these substances usually possess a low volatility, their range in queen–worker communication is potentially limited. Here, we investigate the range and impact of behavioural and chemical queen signals on workers of the ant Temnothorax longispinosus. We compared the behaviour and ovary development of workers subjected to three different treatments: workers with direct chemical and physical contact to the queen, those solely under the influence of volatile queen substances and those entirely separated from the queen. In addition to short-ranged queen signals preventing ovary development in workers, we discovered a novel secondary pathway influencing worker behaviour. Workers with no physical contact to the queen, but exposed to volatile substances, started to develop their ovaries, but did not change their behaviour compared to workers in direct contact to the queen. In contrast, workers in queen-separated groups showed both increased ovary development and aggressive dominance interactions. We conclude that T. longispinosus queens influence worker ovary development and behaviour via two independent signals, both ensuring social harmony within the colony.},
author = {Konrad, Matthias and Pamminger, Tobias and Foitzik, Susanne},
journal = {Naturwissenschaften},
number = {8},
pages = {627 -- 636},
publisher = {Springer},
title = {{Two pathways ensuring social harmony}},
doi = {10.1007/s00114-012-0943-z},
volume = {99},
year = {2012},
}
@inproceedings{3133,
abstract = {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. },
author = {Edelsbrunner, Herbert and Kerber, Michael},
booktitle = {Proceedings of the twenty-eighth annual symposium on Computational geometry },
location = {Chapel Hill, NC, USA},
pages = {249 -- 258},
publisher = {ACM},
title = {{Alexander duality for functions: The persistent behavior of land and water and shore}},
doi = {10.1145/2261250.2261287},
year = {2012},
}
@inproceedings{3135,
abstract = {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. },
author = {Brázdil, Brázdil and Chatterjee, Krishnendu and Kučera, Antonín and Novotny, Petr},
location = {Berkeley, CA, USA},
pages = {23 -- 38},
publisher = {Springer},
title = {{Efficient controller synthesis for consumption games with multiple resource types}},
doi = {10.1007/978-3-642-31424-7_8},
volume = {7358},
year = {2012},
}
@inproceedings{3136,
abstract = {Continuous-time Markov chains (CTMC) with their rich theory and efficient simulation algorithms have been successfully used in modeling stochastic processes in diverse areas such as computer science, physics, and biology. However, systems that comprise non-instantaneous events cannot be accurately and efficiently modeled with CTMCs. In this paper we define delayed CTMCs, an extension of CTMCs that allows for the specification of a lower bound on the time interval between an event's initiation and its completion, and we propose an algorithm for the computation of their behavior. Our algorithm effectively decomposes the computation into two stages: a pure CTMC governs event initiations while a deterministic process guarantees lower bounds on event completion times. Furthermore, from the nature of delayed CTMCs, we obtain a parallelized version of our algorithm. We use our formalism to model genetic regulatory circuits (biological systems where delayed events are common) and report on the results of our numerical algorithm as run on a cluster. We compare performance and accuracy of our results with results obtained by using pure CTMCs. © 2012 Springer-Verlag.},
author = {Guet, Calin C and Gupta, Ashutosh and Henzinger, Thomas A and Mateescu, Maria and Sezgin, Ali},
location = {Berkeley, CA, USA},
pages = {294 -- 309},
publisher = {Springer},
title = {{Delayed continuous time Markov chains for genetic regulatory circuits}},
doi = {10.1007/978-3-642-31424-7_24},
volume = {7358 },
year = {2012},
}
@inproceedings{3155,
abstract = {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.},
author = {Delahaye, Benoît and Fahrenberg, Uli and Henzinger, Thomas A and Legay, Axel and Nickovic, Dejan},
location = {Stockholm, Sweden},
pages = {203 -- 218},
publisher = {Springer},
title = {{Synchronous interface theories and time triggered scheduling}},
doi = {10.1007/978-3-642-30793-5_13},
volume = {7273},
year = {2012},
}
@article{3156,
abstract = {Dispersal is crucial for gene flow and often determines the long-term stability of meta-populations, particularly in rare species with specialized life cycles. Such species are often foci of conservation efforts because they suffer disproportionally from degradation and fragmentation of their habitat. However, detailed knowledge of effective gene flow through dispersal is often missing, so that conservation strategies have to be based on mark-recapture observations that are suspected to be poor predictors of long-distance dispersal. These constraints have been especially severe in the study of butterfly populations, where microsatellite markers have been difficult to develop. We used eight microsatellite markers to analyse genetic population structure of the Large Blue butterfly Maculinea arion in Sweden. During recent decades, this species has become an icon of insect conservation after massive decline throughout Europe and extinction in Britain followed by reintroduction of a seed population from the Swedish island of Öland. We find that populations are highly structured genetically, but that gene flow occurs over distances 15 times longer than the maximum distance recorded from mark-recapture studies, which can only be explained by maximum dispersal distances at least twice as large as previously accepted. However, we also find evidence that gaps between sites with suitable habitat exceeding ∼ 20 km induce genetic erosion that can be detected from bottleneck analyses. Although further work is needed, our results suggest that M. arion can maintain fully functional metapopulations when they consist of optimal habitat patches that are no further apart than ∼10 km.},
author = {Ugelvig, Line V and Andersen, Anne and Boomsma, Jacobus and Nash, David},
journal = {Molecular Ecology},
number = {13},
pages = {3224 -- 3236},
publisher = {Wiley-Blackwell},
title = {{Dispersal and gene flow in the rare parasitic Large Blue butterfly Maculinea arion}},
doi = {10.1111/j.1365-294X.2012.05592.x},
volume = {21},
year = {2012},
}
@article{3157,
abstract = {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.},
author = {Diaz Jr, Luis and Williams, Richard and Wu, Jian and Kinde, Isaac and Hecht, Joel and Berlin, Jordan and Allen, Benjamin and Božić, Ivana and Reiter, Johannes and Nowak, Martin and Kinzler, Kenneth and Oliner, Kelly and Vogelstein, Bert},
journal = {Nature},
number = {7404},
pages = {537 -- 540},
publisher = {Nature Publishing Group},
title = {{The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers}},
doi = {10.1038/nature11219},
volume = {486},
year = {2012},
}
@article{3158,
abstract = {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.},
author = {Schachtner, Hannah and Li, Ang and Stevenson, David and Calaminus, Simon and Thomas, Steven and Watson, Steve and Sixt, Michael K and Wedlich Söldner, Roland and Strathdee, Douglas and Machesky, Laura},
journal = {European Journal of Cell Biology},
number = {11-12},
pages = {923 -- 929},
publisher = {Elsevier},
title = {{Tissue inducible Lifeact expression allows visualization of actin dynamics in vivo and ex vivo}},
doi = {10.1016/j.ejcb.2012.04.002},
volume = {91},
year = {2012},
}
@article{3159,
abstract = {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.},
author = {Mileyko, Yuriy and Edelsbrunner, Herbert and Price, Charles and Weitz, Joshua},
journal = {PLoS One},
number = {6},
publisher = {Public Library of Science},
title = {{Hierarchical ordering of reticular networks}},
doi = {10.1371/journal.pone.0036715},
volume = {7},
year = {2012},
}
@article{3160,
abstract = {There is a long-running controversy about how early cell fate decisions are made in the developing mammalian embryo. 1,2 In particular, it is controversial when the first events that can predict the establishment of the pluripotent and extra-embryonic lineages in the blastocyst of the pre-implantation embryo occur. It has long been proposed that the position and polarity of cells at the 16- to 32-cell stage embryo influence their decision to either give rise to the pluripotent cell lineage that eventually contributes to the inner cell mass (ICM), comprising the primitive endoderm (PE) and the epiblast (EPI), or the extra-embryonic trophectoderm (TE) surrounding the blastocoel. The positioning of cells in the embryo at this developmental stage could largely be the result of random events, making this a stochastic model of cell lineage allocation. Contrary to such a stochastic model, some studies have detected putative differences in the lineage potential of individual blastomeres before compaction, indicating that the first cell fate decisions may occur as early as at the 4-cell stage. Using a non-invasive, quantitative in vivo imaging assay to study the kinetic behavior of Oct4 (also known as POU5F1), a key transcription factor (TF) controlling pre-implantation development in the mouse embryo, 3-5 a recent study identifies Oct4 kinetics as a predictive measure of cell lineage patterning in the early mouse embryo. 6 Here, we discuss the implications of such molecular heterogeneities in early development and offer potential avenues toward a mechanistic understanding of these observations, contributing to the resolution of the controversy of developmental cell lineage allocation.},
author = {Pantazis, Periklis and Bollenbach, Tobias},
journal = {Cell Cycle},
number = {11},
pages = {2055 -- 2058},
publisher = {Taylor and Francis},
title = {{Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo}},
doi = {10.4161/cc.20118},
volume = {11},
year = {2012},
}
@article{3161,
abstract = {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.},
author = {Vyleta, Meghan and Wong, John and Magun, Bruce},
journal = {PLoS One},
number = {5},
publisher = {Public Library of Science},
title = {{Suppression of ribosomal function triggers innate immune signaling through activation of the NLRP3 inflammasome}},
doi = {10.1371/journal.pone.0036044},
volume = {7},
year = {2012},
}
@inproceedings{3162,
abstract = {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.},
author = {Asarin, Eugene and Donzé, Alexandre and Maler, Oded and Nickovic, Dejan},
location = {San Francisco, CA, United States},
pages = {147 -- 160},
publisher = {Springer},
title = {{Parametric identification of temporal properties}},
doi = {10.1007/978-3-642-29860-8_12},
volume = {7186},
year = {2012},
}
@article{3164,
abstract = {Overview of the Special Issue on structured prediction and inference.},
author = {Blaschko, Matthew and Lampert, Christoph},
journal = {International Journal of Computer Vision},
number = {3},
pages = {257 -- 258},
publisher = {Springer},
title = {{Guest editorial: Special issue on structured prediction and inference}},
doi = {10.1007/s11263-012-0530-y},
volume = {99},
year = {2012},
}
@article{3166,
abstract = {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)},
author = {Vladar, Harold},
journal = {Biology Direct},
publisher = {BioMed Central},
title = {{Amino acid fermentation at the origin of the genetic code}},
doi = {10.1186/1745-6150-7-6},
volume = {7},
year = {2012},
}
@article{3167,
author = {Weber, Michele},
journal = {Science},
number = {6077},
pages = {32--34},
publisher = {American Association for the Advancement of Science},
title = {{NextGen speaks 13 }},
doi = {10.1126/science.336.6077.32},
volume = {336},
year = {2012},
}
@article{3168,
abstract = {The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently, we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper, we prove that this quotienting yields a sufficient condition for weak lumpability (that is to say that the quotient system is still Markovian for a given set of initial distributions) and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system (which means that the conditional probability of being in a given state in the original system knowing that we are in its equivalence class is an invariant of the system). We illustrate the framework on a case study of the epidermal growth factor (EGF)/insulin receptor crosstalk.},
author = {Feret, Jérôme and Henzinger, Thomas A and Koeppl, Heinz and Petrov, Tatjana},
journal = {Theoretical Computer Science},
pages = {137 -- 164},
publisher = {Elsevier},
title = {{Lumpability abstractions of rule based systems}},
doi = {10.1016/j.tcs.2011.12.059},
volume = {431},
year = {2012},
}
@article{3243,
author = {Danowski, Patrick},
journal = {Büchereiperspektiven},
pages = {11},
publisher = {Buchereiverband Österreichs},
title = {{Zwischen Technologie und Information}},
volume = {1/2012},
year = {2012},
}
@article{3244,
author = {Danowski, Patrick},
journal = {BuB – Forum Bibliothek und Information},
number = {4},
pages = {284},
publisher = {Bock & Herchen Verlag},
title = {{Die Zeit des Abwartens ist vorbei!}},
volume = {64},
year = {2012},
}
@article{3245,
abstract = {How cells orchestrate their behavior during collective migration is a long-standing question. Using magnetic tweezers to apply mechanical stimuli to Xenopus mesendoderm cells, Weber etal. (2012) now reveal, in this issue of Developmental Cell, a cadherin-mediated mechanosensitive response that promotes cell polarization and movement persistence during the collective mesendoderm migration in gastrulation.},
author = {Behrndt, Martin and Heisenberg, Carl-Philipp J},
journal = {Developmental Cell},
number = {1},
pages = {3 -- 4},
publisher = {Cell Press},
title = {{Spurred by resistance mechanosensation in collective migration}},
doi = {10.1016/j.devcel.2011.12.018},
volume = {22},
year = {2012},
}
@article{3246,
abstract = {Visualizing and analyzing shape changes at various scales, ranging from single molecules to whole organisms, are essential for understanding complex morphogenetic processes, such as early embryonic development. Embryo morphogenesis relies on the interplay between different tissues, the properties of which are again determined by the interaction between their constituent cells. Cell interactions, on the other hand, are controlled by various molecules, such as signaling and adhesion molecules, which in order to exert their functions need to be spatiotemporally organized within and between the interacting cells. In this review, we will focus on the role of cell adhesion functioning at different scales to organize cell, tissue and embryo morphogenesis. We will specifically ask how the subcellular distribution of adhesion molecules controls the formation of cell-cell contacts, how cell-cell contacts determine tissue shape, and how tissue interactions regulate embryo morphogenesis.},
author = {Barone, Vanessa and Heisenberg, Carl-Philipp J},
journal = {Current Opinion in Cell Biology},
number = {1},
pages = {148 -- 153},
publisher = {Elsevier},
title = {{Cell adhesion in embryo morphogenesis}},
doi = {10.1016/j.ceb.2011.11.006},
volume = {24},
year = {2012},
}
@article{3247,
abstract = {The Brazilian Merganser is a very rare and threatened species that nowadays inhabits only a few protected areas and their surroundings in the Brazilian territory. In order to estimate the remaining genetic diversity and population structure in this species, two mitochondrial genes were sequenced in 39 individuals belonging to two populations and in one individual collected in Argentina in 1950. We found a highly significant divergence between two major remaining populations of Mergus octosetaceus, which suggests a historical population structure in this species. Furthermore, two deeply divergent lineages were found in a single location, which could due to current or historical secondary contact. Based on the available genetic data, we point out future directions which would contribute to design strategies for conservation and management of this threatened species.},
author = {Vilaça, Sibelle and Fernandes Redondo, Rodrigo A and Lins, Lívia and Santos, Fabrício},
journal = {Conservation Genetics},
number = {1},
pages = {293 -- 298},
publisher = {Springer},
title = {{Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus)}},
doi = {10.1007/s10592-011-0262-5},
volume = {13},
year = {2012},
}
@article{3249,
abstract = {Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of "fit" or "desirability". We extend the simulation preorder to the quantitative setting by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes.},
author = {Cerny, Pavol and Henzinger, Thomas A and Radhakrishna, Arjun},
journal = {Theoretical Computer Science},
number = {1},
pages = {21 -- 35},
publisher = {Elsevier},
title = {{Simulation distances}},
doi = {10.1016/j.tcs.2011.08.002},
volume = {413},
year = {2012},
}
@inproceedings{3250,
abstract = {The Learning Parity with Noise (LPN) problem has recently found many applications in cryptography as the hardness assumption underlying the constructions of "provably secure" cryptographic schemes like encryption or authentication protocols. Being provably secure means that the scheme comes with a proof showing that the existence of an efficient adversary against the scheme implies that the underlying hardness assumption is wrong. LPN based schemes are appealing for theoretical and practical reasons. On the theoretical side, LPN based schemes offer a very strong security guarantee. The LPN problem is equivalent to the problem of decoding random linear codes, a problem that has been extensively studied in the last half century. The fastest known algorithms run in exponential time and unlike most number-theoretic problems used in cryptography, the LPN problem does not succumb to known quantum algorithms. On the practical side, LPN based schemes are often extremely simple and efficient in terms of code-size as well as time and space requirements. This makes them prime candidates for light-weight devices like RFID tags, which are too weak to implement standard cryptographic primitives like the AES block-cipher. This talk will be a gentle introduction to provable security using simple LPN based schemes as examples. Starting from pseudorandom generators and symmetric key encryption, over secret-key authentication protocols, and, if time admits, touching on recent constructions of public-key identification, commitments and zero-knowledge proofs.},
author = {Pietrzak, Krzysztof Z},
location = {Špindlerův Mlýn, Czech Republic},
pages = {99 -- 114},
publisher = {Springer},
title = {{Cryptography from learning parity with noise}},
doi = {10.1007/978-3-642-27660-6_9},
volume = {7147},
year = {2012},
}
@inproceedings{3251,
abstract = {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.},
author = {Zufferey, Damien and Wies, Thomas and Henzinger, Thomas A},
location = {Philadelphia, PA, USA},
pages = {445 -- 460},
publisher = {Springer},
title = {{Ideal abstractions for well structured transition systems}},
doi = {10.1007/978-3-642-27940-9_29},
volume = {7148},
year = {2012},
}
@inproceedings{3252,
abstract = {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.},
author = {Chatterjee, Krishnendu and Raman, Vishwanath},
location = {Philadelphia, PA, USA},
pages = {152 -- 168},
publisher = {Springer},
title = {{Synthesizing protocols for digital contract signing}},
doi = {10.1007/978-3-642-27940-9_11},
volume = {7148},
year = {2012},
}
@inproceedings{3253,
abstract = {We describe a framework for reasoning about programs with lists carrying integer numerical data. We use abstract domains to describe and manipulate complex constraints on configurations of these programs mixing constraints on the shape of the heap, sizes of the lists, on the multisets of data stored in these lists, and on the data at their different positions. Moreover, we provide powerful techniques for automatic validation of Hoare-triples and invariant checking, as well as for automatic synthesis of invariants and procedure summaries using modular inter-procedural analysis. The approach has been implemented in a tool called Celia and experimented successfully on a large benchmark of programs.},
author = {Bouajjani, Ahmed and Dragoi, Cezara and Enea, Constantin and Sighireanu, Mihaela},
location = {Philadelphia, PA, USA},
pages = {1 -- 22},
publisher = {Springer},
title = {{Abstract domains for automated reasoning about list manipulating programs with infinite data}},
doi = {10.1007/978-3-642-27940-9_1},
volume = {7148},
year = {2012},
}
@article{3254,
abstract = {The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also study the complexity of stochastic Müller games and show that both the qualitative and quantitative analysis problems are PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes.},
author = {Chatterjee, Krishnendu},
journal = {Information and Computation},
pages = {29 -- 48},
publisher = {Elsevier},
title = {{The complexity of stochastic Müller games}},
doi = {10.1016/j.ic.2011.11.004},
volume = {211},
year = {2012},
}
@inproceedings{3255,
abstract = {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.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
location = {Lednice, Czech Republic},
pages = {37 -- 46},
publisher = {Springer},
title = {{Games and Markov decision processes with mean payoff parity and energy parity objectives}},
doi = {10.1007/978-3-642-25929-6_3},
volume = {7119},
year = {2012},
}
@article{3256,
abstract = {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.},
author = {Edelsbrunner, Herbert and Kerber, Michael},
journal = {Discrete & Computational Geometry},
number = {2},
pages = {393 -- 414},
publisher = {Springer},
title = {{Dual complexes of cubical subdivisions of ℝn}},
doi = {10.1007/s00454-011-9382-4},
volume = {47},
year = {2012},
}
@article{3257,
abstract = {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.},
author = {Kolmogorov, Vladimir},
journal = {Discrete Applied Mathematics},
number = {4-5},
pages = {416 -- 426},
publisher = {Elsevier},
title = {{Generalized roof duality and bisubmodular functions}},
doi = {10.1016/j.dam.2011.10.026},
volume = {160},
year = {2012},
}
@article{3258,
abstract = {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.},
author = {Kim, Sooyun and Guzmán, José and Hu, Hua and Jonas, Peter M},
journal = {Nature Neuroscience},
number = {4},
pages = {600 -- 606},
publisher = {Nature Publishing Group},
title = {{Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons}},
doi = {10.1038/nn.3060},
volume = {15},
year = {2012},
}
@article{3260,
abstract = {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.
},
author = {Chatterjee, Krishnendu and Reiter, Johannes and Nowak, Martin},
journal = {Theoretical Population Biology},
number = {1},
pages = {69 -- 80},
publisher = {Academic Press},
title = {{Evolutionary dynamics of biological auctions}},
doi = {10.1016/j.tpb.2011.11.003},
volume = {81},
year = {2012},
}
@article{3262,
abstract = {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.},
author = {Tkacik, Gasper and Walczak, Aleksandra and Bialek, William},
journal = { Physical Review E statistical nonlinear and soft matter physics },
number = {4},
publisher = {American Institute of Physics},
title = {{Optimizing information flow in small genetic networks. III. A self-interacting gene}},
doi = {10.1103/PhysRevE.85.041903},
volume = {85},
year = {2012},
}
@inproceedings{3265,
abstract = {We propose a mid-level statistical model for image segmentation that composes multiple figure-ground hypotheses (FG) obtained by applying constraints at different locations and scales, into larger interpretations (tilings) of the entire image. Inference is cast as optimization over sets of maximal cliques sampled from a graph connecting all non-overlapping figure-ground segment hypotheses. Potential functions over cliques combine unary, Gestalt-based figure qualities, and pairwise compatibilities among spatially neighboring segments, constrained by T-junctions and the boundary interface statistics of real scenes. Learning the model parameters is based on maximum likelihood, alternating between sampling image tilings and optimizing their potential function parameters. State of the art results are reported on the Berkeley and Stanford segmentation datasets, as well as VOC2009, where a 28% improvement was achieved.},
author = {Ion, Adrian and Carreira, Joao and Sminchisescu, Cristian},
location = {Barcelona, Spain},
publisher = {IEEE},
title = {{Image segmentation by figure-ground composition into maximal cliques}},
doi = {10.1109/ICCV.2011.6126486},
year = {2012},
}
@article{3274,
abstract = {A boundary element model of a tunnel running through horizontally layered soil with anisotropic material properties is presented. Since there is no analytical fundamental solution for wave propagation inside a layered orthotropic medium in 3D, the fundamental displacements and stresses have to be calculated numerically. In our model this is done in the Fourier domain with respect to space and time. The assumption of a straight tunnel with infinite extension in the x direction makes it possible to decouple the system for every wave number kx, leading to a 2.5D-problem, which is suited for parallel computation. The special form of the fundamental solution, resulting from our Fourier ansatz, and the fact, that the calculation of the boundary integral equation is performed in the Fourier domain, enhances the stability and efficiency of the numerical calculations.},
author = {Rieckh, Georg and Kreuzer, Wolfgang and Waubke, Holger and Balazs, Peter},
journal = { Engineering Analysis with Boundary Elements},
number = {6},
pages = {960 -- 967},
publisher = {Elsevier},
title = {{A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil}},
doi = {10.1016/j.enganabound.2011.12.014},
volume = {36},
year = {2012},
}
@inbook{3277,
abstract = {The problem of the origin of metazoa is becoming more urgent in the context of astrobiology. By now it is clear that clues to the understanding of this crucial transition in the evolution of life can arise in a fourth pathway besides the three possibilities in the quest for simplicity outlined by Bonner in his classical book. In other words, solar system exploration seems to be one way in the long-term to elucidate the simplicity of evolutionary development. We place these ideas in the context of different inheritance systems, namely the genotypic and phenotypic replicators with limited or unlimited heredity, and ask which of these can support multicellular development, and to which degree of complexity. However, the quest for evidence on the evolution of biotas from planets around other stars does not seem to be feasible with present technology with direct visualization of living organisms on exoplanets. But this may be attempted on the Galilean moons of Jupiter where there is a possibility of detecting reliable biomarkers in the next decade with the Europa Jupiter System Mission, in view of recent progress by landing micropenetrators on planetary, or satellite surfaces. Mars is a second possibility in the inner Solar System, in spite of the multiple difficulties faced by the fleet of past, present and future missions. We discuss a series of preliminary ideas for elucidating the origin of metazoan analogues with available instrumentation in potential payloads of feasible space missions to the Galilean moons.},
author = {de Vladar, Harold and Chela Flores, Julian},
booktitle = {Life on Earth and other planetary bodies},
pages = {387 -- 405},
publisher = {Springer},
title = {{Can the evolution of multicellularity be anticipated in the exploration of the solar system?}},
doi = {10.1007/978-94-007-4966-5_22},
volume = {24},
year = {2012},
}
@inproceedings{3279,
abstract = {We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound q on the number of queries to the PRF. Our construction requires only O(logq) invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially secure if queried at most q = exp(√n)times and where each invocation of the PRF requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n) required by known constructions.
},
author = {Jain, Abhishek and Pietrzak, Krzysztof Z and Tentes, Aris},
location = {Taormina, Sicily, Italy},
pages = {369 -- 382},
publisher = {Springer},
title = {{Hardness preserving constructions of pseudorandom functions}},
doi = {10.1007/978-3-642-28914-9_21},
volume = {7194},
year = {2012},
}
@inproceedings{3280,
abstract = {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. },
author = {Pietrzak, Krzysztof Z},
location = {Taormina, Sicily, Italy},
pages = {548 -- 563},
publisher = {Springer},
title = {{Subspace LWE}},
doi = {10.1007/978-3-642-28914-9_31},
volume = {7194},
year = {2012},
}
@inproceedings{3281,
abstract = {We consider the problem of amplifying the "lossiness" of functions. We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f has image size at most 2 m-L. The question is whether such C* exists for L/m ≫ ℓ/n. This problem arises naturally in the context of cryptographic "lossy functions," where the relative lossiness is the key parameter. We show that for every circuit C* that makes at most t queries to f, the relative lossiness of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making a polynomial t = poly(n) number of queries can amplify relative lossiness by more than an O(logn)/n additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification.},
author = {Pietrzak, Krzysztof Z and Rosen, Alon and Segev, Gil},
location = {Taormina, Sicily, Italy},
pages = {458 -- 475},
publisher = {Springer},
title = {{Lossy functions do not amplify well}},
doi = {10.1007/978-3-642-28914-9_26},
volume = {7194},
year = {2012},
}