@inbook{10899, author = {Barton, Nicholas H}, booktitle = {Encyclopedia of Biodiversity}, isbn = {978-0-12-384720-1}, keywords = {Adaptive landscape, Cline, Coalescent process, Gene flow, Hybrid zone, Local adaptation, Natural selection, Neutral theory, Population structure, Speciation}, pages = {508--515}, publisher = {Elsevier}, title = {{Differentiation}}, doi = {10.1016/b978-0-12-384719-5.00031-9}, year = {2013}, } @inbook{10900, abstract = {Leukocyte migration through the interstitial space is crucial for the maintenance of tolerance and immunity. The main cues for leukocyte trafficking are chemokines thought to directionally guide these cells towards their targets. However, model systems that facilitate quantification of chemokine-guided leukocyte migration in vivo are uncommon. Here we describe an ex vivo crawl-in assay using explanted mouse ears that allows the visualization of chemokine-dependent dendritic cell (DC) motility in the dermal interstitium in real time. We present methods for the preparation of mouse ear sheets and their use in multidimensional confocal imaging experiments to monitor and analyze the directional migration of fluorescently labelled DCs through the dermis and into afferent lymphatic vessels. The assay provides a more physiological approach to study leukocyte migration than in vitro three-dimensional (3D) or 2-dimensional (2D) migration assays such as collagen gels and transwell assays.}, author = {Weber, Michele and Sixt, Michael K}, booktitle = {Chemokines}, editor = {Cardona, Astrid and Ubogu, Eroboghene}, isbn = {9781627034258}, issn = {1940-6029}, pages = {215--226}, publisher = {Humana Press}, title = {{Live Cell Imaging of Chemotactic Dendritic Cell Migration in Explanted Mouse Ear Preparations}}, doi = {10.1007/978-1-62703-426-5_14}, volume = {1013}, year = {2013}, } @inproceedings{10902, abstract = {We consider how to edit strings from a source language so that the edited strings belong to a target language, where the languages are given as deterministic finite automata. Non-streaming (or offline) transducers perform edits given the whole source string. We show that the class of deterministic one-pass transducers with registers along with increment and min operation suffices for computing optimal edit distance, whereas the same class of transducers without the min operation is not sufficient. Streaming (or online) transducers perform edits as the letters of the source string are received. We present a polynomial time algorithm for the partial-repair problem that given a bound α asks for the construction of a deterministic streaming transducer (if one exists) that ensures that the ‘maximum fraction’ η of the strings of the source language are edited, within cost α, to the target language.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Rubin, Sasha}, booktitle = {7th International Conference on Language and Automata Theory and Applications}, isbn = {9783642370632}, issn = {1611-3349}, location = {Bilbao, Spain}, pages = {214--225}, publisher = {Springer Nature}, title = {{How to travel between languages}}, doi = {10.1007/978-3-642-37064-9_20}, volume = {7810}, year = {2013}, } @article{2516, abstract = {We study the problem of object recognition for categories for which we have no training examples, a task also called zero-data or zero-shot learning. This situation has hardly been studied in computer vision research, even though it occurs frequently: the world contains tens of thousands of different object classes and for only few of them image collections have been formed and suitably annotated. To tackle the problem we introduce attribute-based classification: objects are identified based on a high-level description that is phrased in terms of semantic attributes, such as the object's color or shape. Because the identification of each such property transcends the specific learning task at hand, the attribute classifiers can be pre-learned independently, e.g. from existing image datasets unrelated to the current task. Afterwards, new classes can be detected based on their attribute representation, without the need for a new training phase. In this paper we also introduce a new dataset, Animals with Attributes, of over 30,000 images of 50 animal classes, annotated with 85 semantic attributes. Extensive experiments on this and two more datasets show that attribute-based classification indeed is able to categorize images without access to any training images of the target classes.}, author = {Lampert, Christoph and Nickisch, Hannes and Harmeling, Stefan}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {3}, pages = {453 -- 465}, publisher = {IEEE}, title = {{Attribute-based classification for zero-shot learning of object categories}}, doi = {10.1109/TPAMI.2013.140}, volume = {36}, year = {2013}, } @article{12198, abstract = {The Arabidopsis thaliana central cell, the companion cell of the egg, undergoes DNA demethylation before fertilization, but the targeting preferences, mechanism, and biological significance of this process remain unclear. Here, we show that active DNA demethylation mediated by the DEMETER DNA glycosylase accounts for all of the demethylation in the central cell and preferentially targets small, AT-rich, and nucleosome-depleted euchromatic transposable elements. The vegetative cell, the companion cell of sperm, also undergoes DEMETER-dependent demethylation of similar sequences, and lack of DEMETER in vegetative cells causes reduced small RNA–directed DNA methylation of transposons in sperm. Our results demonstrate that demethylation in companion cells reinforces transposon methylation in plant gametes and likely contributes to stable silencing of transposable elements across generations.}, author = {Ibarra, Christian A. and Feng, Xiaoqi and Schoft, Vera K. and Hsieh, Tzung-Fu and Uzawa, Rie and Rodrigues, Jessica A. and Zemach, Assaf and Chumak, Nina and Machlicova, Adriana and Nishimura, Toshiro and Rojas, Denisse and Fischer, Robert L. and Tamaru, Hisashi and Zilberman, Daniel}, issn = {1095-9203}, journal = {Science}, keywords = {Multidisciplinary}, number = {6100}, pages = {1360--1364}, publisher = {American Association for the Advancement of Science}, title = {{Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes}}, doi = {10.1126/science.1224839}, volume = {337}, year = {2012}, } @misc{13075, 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, C. 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.}, author = {Lohse, Konrad and Barton, Nicholas H and Stone, Graham and Melika, George}, publisher = {Dryad}, title = {{Data from: A likelihood-based comparison of population histories in a parasitoid guild}}, doi = {10.5061/DRYAD.0G0FS}, year = {2012}, } @inproceedings{2048, abstract = {Leakage resilient cryptography attempts to incorporate side-channel leakage into the black-box security model and designs cryptographic schemes that are provably secure within it. Informally, a scheme is leakage-resilient if it remains secure even if an adversary learns a bounded amount of arbitrary information about the schemes internal state. Unfortunately, most leakage resilient schemes are unnecessarily complicated in order to achieve strong provable security guarantees. As advocated by Yu et al. [CCS’10], this mostly is an artefact of the security proof and in practice much simpler construction may already suffice to protect against realistic side-channel attacks. In this paper, we show that indeed for simpler constructions leakage-resilience can be obtained when we aim for relaxed security notions where the leakage-functions and/or the inputs to the primitive are chosen non-adaptively. For example, we show that a three round Feistel network instantiated with a leakage resilient PRF yields a leakage resilient PRP if the inputs are chosen non-adaptively (This complements the result of Dodis and Pietrzak [CRYPTO’10] who show that if a adaptive queries are allowed, a superlogarithmic number of rounds is necessary.) We also show that a minor variation of the classical GGM construction gives a leakage resilient PRF if both, the leakage-function and the inputs, are chosen non-adaptively.}, author = {Faust, Sebastian and Pietrzak, Krzysztof Z and Schipper, Joachim}, booktitle = { Conference proceedings CHES 2012}, location = {Leuven, Belgium}, pages = {213 -- 232}, publisher = {Springer}, title = {{Practical leakage-resilient symmetric cryptography}}, doi = {10.1007/978-3-642-33027-8_13}, volume = {7428}, year = {2012}, } @inproceedings{2049, abstract = {We propose a new authentication protocol that is provably secure based on a ring variant of the learning parity with noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt’11 (Kiltz et al.), and like it, is a two round protocol secure against active attacks. Moreover, our protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource-constrained devices. Performance-wise, our protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt’11. Our implementation results show that it is even comparable to the standard challenge-and-response protocols based on the AES block-cipher. Our basic protocol is roughly 20 times slower than AES, but with the advantage of having 10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile memory are available to allow the storage of some off-line pre-computations, then the online phase of our protocols is only twice as slow as AES. }, author = {Heyse, Stefan and Kiltz, Eike and Lyubashevsky, Vadim and Paar, Christof and Pietrzak, Krzysztof Z}, booktitle = { Conference proceedings FSE 2012}, location = {Washington, DC, USA}, pages = {346 -- 365}, publisher = {Springer}, title = {{Lapin: An efficient authentication protocol based on ring-LPN}}, doi = {10.1007/978-3-642-34047-5_20}, volume = {7549}, year = {2012}, } @inproceedings{1384, abstract = {Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition Ψ - usually a state predicate - such that the program satisfies the specification under the condition Ψ - that is, as long as the program does not leave the states in which Ψ is satisfied. In our experiments, we investigated as one major application of conditional model checking the sequential combination of model checkers with information passing. We give the condition that one model checker produces, as input to a second conditional model checker, such that the verification problem for the second is restricted to the part of the state space that is not covered by the condition, i.e., the second model checker works on the problems that the first model checker could not solve. Our experiments demonstrate that repeated application of conditional model checkers, passing information from one model checker to the next, can significantly improve the verification results and performance, i.e., we can now verify programs that we could not verify before.}, author = {Beyer, Dirk and Henzinger, Thomas A and Keremoglu, Mehmet and Wendler, Philipp}, booktitle = {Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering}, location = {Cary, NC, USA}, publisher = {ACM}, title = {{Conditional model checking: A technique to pass information between verifiers}}, doi = {10.1145/2393596.2393664}, year = {2012}, } @misc{5396, abstract = {We consider the problem of inference in agraphical 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 pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped 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 out-perform 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}, issn = {2664-1690}, pages = {13}, publisher = {IST Austria}, title = {{Approximating marginals using discrete energy minimization}}, doi = {10.15479/AT:IST-2012-0003}, year = {2012}, } @techreport{5398, abstract = {This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers.}, author = {Porsche, Jana}, publisher = {IST Austria}, title = {{Actual state of research data @ ISTAustria}}, year = {2012}, } @inbook{5745, author = {Gupta, Ashutosh}, booktitle = {Automated Technology for Verification and Analysis}, isbn = {9783642333859}, issn = {1611-3349}, location = {Thiruvananthapuram, Kerala, India}, pages = {107--121}, publisher = {Springer Berlin Heidelberg}, title = {{Improved Single Pass Algorithms for Resolution Proof Reduction}}, doi = {10.1007/978-3-642-33386-6_10}, volume = {7561}, year = {2012}, } @article{6588, abstract = {First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions.}, author = {Pausinger, Florian}, issn = {1812-9471}, journal = {Journal of Mathematical Physics, Analysis, Geometry}, number = {1}, pages = {63--78}, publisher = {B. Verkin Institute for Low Temperature Physics and Engineering}, title = {{Elementary solutions of the Bernstein problem on two intervals}}, volume = {8}, year = {2012}, } @misc{9755, abstract = {Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”).}, author = {Konrad, Matthias and Vyleta, Meghan and Theis, Fabian and Stock, Miriam and Klatt, Martina and Drescher, Verena and Marr, Carsten and Ugelvig, Line V and Cremer, Sylvia}, publisher = {Dryad}, title = {{Data from: Social transfer of pathogenic fungus promotes active immunisation in ant colonies}}, doi = {10.5061/dryad.sv37s}, year = {2012}, } @misc{9757, abstract = {To fight infectious diseases, host immune defences are employed at multiple levels. Sanitary behaviour, such as pathogen avoidance and removal, acts as a first line of defence to prevent infection [1] before activation of the physiological immune system. Insect societies have evolved a wide range of collective hygiene measures and intensive health care towards pathogen-exposed group members [2]. One of the most common behaviours is allogrooming, in which nestmates remove infectious particles from the body surfaces of exposed individuals [3]. Here we show that, in invasive garden ants, grooming of fungus-exposed brood is effective beyond the sheer mechanical removal of fungal conidiospores as it also includes chemical disinfection through the application of poison produced by the ants themselves. Formic acid is the main active component of the poison. It inhibits fungal growth of conidiospores remaining on the brood surface after grooming and also those collected in the mouth of the grooming ant. This dual function is achieved by uptake of the poison droplet into the mouth through acidopore self-grooming and subsequent application onto the infectious brood via brood grooming. This extraordinary behaviour extends current understanding of grooming and the establishment of social immunity in insect societies.}, author = {Tragust, Simon and Mitteregger, Barbara and Barone, Vanessa and Konrad, Matthias and Ugelvig, Line V and Cremer, Sylvia}, publisher = {Dryad}, title = {{Data from: Ants disinfect fungus-exposed brood by oral uptake and spread of their poison}}, doi = {10.5061/dryad.61649}, year = {2012}, } @misc{9758, abstract = {We propose a two-step procedure for estimating multiple migration rates in an approximate Bayesian computation (ABC) framework, accounting for global nuisance parameters. The approach is not limited to migration, but generally of interest for inference problems with multiple parameters and a modular structure (e.g. independent sets of demes or loci). We condition on a known, but complex demographic model of a spatially subdivided population, motivated by the reintroduction of Alpine ibex (Capra ibex) into Switzerland. In the first step, the global parameters ancestral mutation rate and male mating skew have been estimated for the whole population in Aeschbacher et al. (Genetics 2012; 192: 1027). In the second step, we estimate in this study the migration rates independently for clusters of demes putatively connected by migration. For large clusters (many migration rates), ABC faces the problem of too many summary statistics. We therefore assess by simulation if estimation per pair of demes is a valid alternative. We find that the trade-off between reduced dimensionality for the pairwise estimation on the one hand and lower accuracy due to the assumption of pairwise independence on the other depends on the number of migration rates to be inferred: the accuracy of the pairwise approach increases with the number of parameters, relative to the joint estimation approach. To distinguish between low and zero migration, we perform ABC-type model comparison between a model with migration and one without. Applying the approach to microsatellite data from Alpine ibex, we find no evidence for substantial gene flow via migration, except for one pair of demes in one direction.}, author = {Aeschbacher, Simon and Futschik, Andreas and Beaumont, Mark}, publisher = {Dryad}, title = {{Data from: Approximate Bayesian computation for modular inference problems with many parameters: the example of migration rates}}, doi = {10.5061/dryad.274b1}, year = {2012}, } @article{3317, abstract = {The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant of the signalling properties of synapses in the nervous system. Recent functional analysis indicates that in some fast central synapses, transmitter release is triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors at the nanometre scale. Molecular analysis suggests that this tight coupling is generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors and various other synaptic proteins. Nanodomain coupling has several functional advantages, as it increases the efficacy, speed and energy efficiency of synaptic transmission.}, author = {Eggermann, Emmanuel and Bucurenciu, Iancu and Goswami, Sarit and Jonas, Peter M}, journal = {Nature Reviews Neuroscience}, number = {1}, pages = {7 -- 21}, publisher = {Nature Publishing Group}, title = {{Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses}}, doi = {10.1038/nrn3125}, volume = {13}, year = {2012}, } @article{3331, abstract = {Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve.}, author = {Kerber, Michael and Sagraloff, Michael}, journal = { Journal of Symbolic Computation}, number = {3}, pages = {239 -- 258}, publisher = {Elsevier}, title = {{A worst case bound for topology computation of algebraic curves}}, doi = {10.1016/j.jsc.2011.11.001}, volume = {47}, year = {2012}, } @inproceedings{3341, abstract = {We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).}, author = {Chatterjee, Krishnendu}, location = {Tallinn, Estonia}, pages = {270 -- 285}, publisher = {Springer}, title = {{Robustness of structurally equivalent concurrent parity games}}, doi = {10.1007/978-3-642-28729-9_18}, volume = {7213}, year = {2012}, } @article{3836, abstract = {Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.}, author = {Ghosal, Arkadeb and Iercan, Daniel and Kirsch, Christoph and Henzinger, Thomas A and Sangiovanni Vincentelli, Alberto}, journal = {Science of Computer Programming}, number = {2}, pages = {96 -- 112}, publisher = {Elsevier}, title = {{Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code}}, doi = {10.1016/j.scico.2010.06.004}, volume = {77}, year = {2012}, }