@inproceedings{766, abstract = {Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m + p log p log2 m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m + p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the Ω(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks.}, author = {Alistarh, Dan-Adrian and Bender, Michael and Gilbert, Seth and Guerraoui, Rachid}, pages = {331 -- 340}, publisher = {IEEE}, title = {{How to allocate tasks asynchronously}}, doi = {10.1109/FOCS.2012.41}, year = {2012}, } @article{767, abstract = {Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficiently transform an algorithm that relies on synchronous timing into an algorithm that tolerates asynchronous executions. We introduce a transformation technique from synchronous algorithms to indulgent algorithms (Guerraoui, in PODC, pp. 289-297, 2000), which induces only a constant overhead in terms of time complexity in well-behaved executions. Our technique is based on a new abstraction we call an asynchrony detector, which the participating processes implement collectively. The resulting transformation works for the class of colorless distributed tasks, including consensus and set agreement. Interestingly, we also show that our technique is relevant for colored tasks, by applying it to the renaming problem, to obtain the first indulgent renaming algorithm.}, author = {Alistarh, Dan-Adrian and Gilbert, Seth and Guerraoui, Rachid and Travers, Corentin}, journal = {Theory of Computing Systems}, number = {4}, pages = {404 -- 424}, publisher = {Elsevier}, title = {{Generating Fast Indulgent Algorithms}}, doi = {10.1007/s00224-012-9407-2}, volume = {51}, year = {2012}, } @article{7748, abstract = {Female mate choice acts as an important evolutionary force, yet the influence of the environment on both its expression and the selective pressures acting upon it remains unknown. We found consistent heritable differences between females in their choice of mate based on ornament size during a 25‐year study of a population of collared flycatchers. However, the fitness consequences of mate choice were dependent on environmental conditions experienced whilst breeding. Females breeding with highly ornamented males experienced high relative fitness during dry summer conditions, but low relative fitness during wetter years. Our results imply that sexual selection within a population can be highly variable and dependent upon the prevailing weather conditions experienced by individuals.}, author = {Robinson, Matthew Richard and Sander van Doorn, G. and Gustafsson, Lars and Qvarnström, Anna}, issn = {1461-023X}, journal = {Ecology Letters}, number = {6}, pages = {611--618}, publisher = {Wiley}, title = {{Environment-dependent selection on mate choice in a natural population of birds}}, doi = {10.1111/j.1461-0248.2012.01780.x}, volume = {15}, year = {2012}, } @article{7749, abstract = {Although studies on laboratory species and natural populations of vertebrates have shown reproduction to impair later performance, little is known of the age‐specific associations between reproduction and survival, and how such findings apply to the ageing of large, long‐lived species. Herein we develop a framework to examine population‐level patterns of reproduction and survival across lifespan in long‐lived organisms, and decompose those changes into individual‐level effects, and the effects of age‐specific trade‐offs between fitness components. We apply this to an extensive longitudinal dataset on female semi‐captive Asian timber elephants (Elephas maximus) and report the first evidence of age‐specific fitness declines that are driven by age‐specific associations between fitness components in a long‐lived mammal. Associations between reproduction and survival are positive in early life, but negative in later life with up to 71% of later‐life survival declines associated with investing in the production of offspring within this population of this critically endangered species.}, author = {Robinson, Matthew Richard and Mar, Khyne U and Lummaa, Virpi}, issn = {1461-023X}, journal = {Ecology Letters}, number = {3}, pages = {260--266}, publisher = {Wiley}, title = {{Senescence and age-specific trade-offs between reproduction and survival in female Asian elephants}}, doi = {10.1111/j.1461-0248.2011.01735.x}, volume = {15}, year = {2012}, } @article{492, abstract = {Background: Characterizing root system architecture (RSA) is essential to understanding the development and function of vascular plants. Identifying RSA-associated genes also represents an underexplored opportunity for crop improvement. Software tools are needed to accelerate the pace at which quantitative traits of RSA are estimated from images of root networks.Results: We have developed GiA Roots (General Image Analysis of Roots), a semi-automated software tool designed specifically for the high-throughput analysis of root system images. GiA Roots includes user-assisted algorithms to distinguish root from background and a fully automated pipeline that extracts dozens of root system phenotypes. Quantitative information on each phenotype, along with intermediate steps for full reproducibility, is returned to the end-user for downstream analysis. GiA Roots has a GUI front end and a command-line interface for interweaving the software into large-scale workflows. GiA Roots can also be extended to estimate novel phenotypes specified by the end-user.Conclusions: We demonstrate the use of GiA Roots on a set of 2393 images of rice roots representing 12 genotypes from the species Oryza sativa. We validate trait measurements against prior analyses of this image set that demonstrated that RSA traits are likely heritable and associated with genotypic differences. Moreover, we demonstrate that GiA Roots is extensible and an end-user can add functionality so that GiA Roots can estimate novel RSA traits. In summary, we show that the software can function as an efficient tool as part of a workflow to move from large numbers of root images to downstream analysis.}, author = {Galkovskyi, Taras and Mileyko, Yuriy and Bucksch, Alexander and Moore, Brad and Symonova, Olga and Price, Charles and Topp, Chrostopher and Iyer Pascuzzi, Anjali and Zurek, Paul and Fang, Suqin and Harer, John and Benfey, Philip and Weitz, Joshua}, journal = {BMC Plant Biology}, publisher = {BioMed Central}, title = {{GiA Roots: Software for the high throughput analysis of plant root system architecture}}, doi = {10.1186/1471-2229-12-116}, volume = {12}, year = {2012}, } @article{493, abstract = {The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.}, author = {Tangermann, Michael and Müller, Klaus and Aertsen, Ad and Birbaumer, Niels and Braun, Christoph and Brunner, Clemens and Leeb, Robert and Mehring, Carsten and Miller, Kai and Müller Putz, Gernot and Nolte, Guido and Pfurtscheller, Gert and Preissl, Hubert and Schalk, Gerwin and Schlögl, Alois and Vidaurre, Carmen and Waldert, Stephan and Blankertz, Benjamin}, journal = {Frontiers in Neuroscience}, publisher = {Frontiers Research Foundation}, title = {{Review of the BCI competition IV}}, doi = {10.3389/fnins.2012.00055}, volume = {6}, year = {2012}, } @article{494, abstract = {We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.}, author = {Boker, Udi and Kupferman, Orna}, journal = {ACM Transactions on Computational Logic (TOCL)}, number = {4}, publisher = {ACM}, title = {{Translating to Co-Büchi made tight, unified, and useful}}, doi = {10.1145/2362355.2362357}, volume = {13}, year = {2012}, } @inproceedings{495, abstract = {An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.}, author = {Kruckman, Alex and Rubin, Sasha and Sheridan, John and Zax, Ben}, booktitle = {Proceedings GandALF 2012}, location = {Napoli, Italy}, pages = {238 -- 246}, publisher = {Open Publishing Association}, title = {{A Myhill Nerode theorem for automata with advice}}, doi = {10.4204/EPTCS.96.18}, volume = {96}, year = {2012}, } @inproceedings{496, abstract = {We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.}, author = {Rabinovich, Alexander and Rubin, Sasha}, location = {Dubrovnik, Croatia}, publisher = {IEEE}, title = {{Interpretations in trees with countably many branches}}, doi = {10.1109/LICS.2012.65}, year = {2012}, } @inproceedings{497, abstract = {One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, location = {Fontainebleau, France}, pages = {167 -- 182}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Faster algorithms for alternating refinement relations}}, doi = {10.4230/LIPIcs.CSL.2012.167}, volume = {16}, year = {2012}, } @article{498, abstract = {Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration.}, author = {Pickup, Melinda and Field, David and Rowell, David and Young, Andrew}, journal = {Evolutionary Applications}, number = {8}, pages = {913 -- 924}, publisher = {Wiley-Blackwell}, title = {{Predicting local adaptation in fragmented plant populations: Implications for restoration genetics}}, doi = {10.1111/j.1752-4571.2012.00284.x}, volume = {5}, year = {2012}, } @article{506, author = {Sixt, Michael K}, journal = {Journal of Cell Biology}, number = {3}, pages = {347 -- 349}, publisher = {Rockefeller University Press}, title = {{Cell migration: Fibroblasts find a new way to get ahead}}, doi = {10.1083/jcb.201204039}, volume = {197}, year = {2012}, } @misc{5377, 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 ω-regular 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 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}, issn = {2664-1690}, pages = {33}, publisher = {IST Austria}, title = {{Mean-payoff pushdown games}}, doi = {10.15479/AT:IST-2012-0002}, year = {2012}, } @misc{5378, abstract = {One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, issn = {2664-1690}, pages = {21}, publisher = {IST Austria}, title = {{Faster algorithms for alternating refinement relations}}, doi = {10.15479/AT:IST-2012-0001}, 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{5839, abstract = {Canny's edge detection algorithm is a classical and robust method for edge detection in gray-scale images. The two significant features of this method are introduction of NMS (Non-Maximum Suppression) and double thresholding of the gradient image. Due to poor illumination, the region boundaries in an image may become vague, creating uncertainties in the gradient image. In this paper, we have proposed an algorithm based on the concept of type-2 fuzzy sets to handle uncertainties that automatically selects the threshold values needed to segment the gradient image using classical Canny’s edge detection algorithm. The results show that our algorithm works significantly well on different benchmark images as well as medical images (hand radiography images). }, author = {Biswas, Ranita and Sil, Jaya}, issn = {2212-0173}, journal = {Procedia Technology}, pages = {820--824}, publisher = {Elsevier}, title = {{An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets}}, doi = {10.1016/j.protcy.2012.05.134}, volume = {4}, year = {2012}, } @article{596, abstract = {The human Mediator complex controls RNA polymerase II (pol II) function in ways that remain incompletely understood. Activator-Mediator binding alters Mediator structure, and these activator-induced structural shifts appear to play key roles in regulating transcription. A recent cryo-electron microscopy (EM) analysis revealed that pol II adopted a stable orientation within a Mediator-pol II-TFIIF assembly in which Mediator was bound to the activation domain of viral protein 16 (VP16). Whereas TFIIF was shown to be important for orienting pol II within this assembly, the potential role of the activator was not assessed. To determine how activator binding might affect pol II orientation, we isolated human Mediator-pol II-TFIIF complexes in which Mediator was not bound to an activator. Cryo-EM analysis of this assembly, coupled with pol II crystal structure docking, revealed that pol II binds Mediator at the same general location; however, in contrast to VP16-bound Mediator, pol II does not appear to stably orient in the absence of an activator. Variability in pol II orientation might be important mechanistically, perhaps to enable sense and antisense transcription at human promoters. Because Mediator interacts extensively with pol II, these results suggest that Mediator structural shifts induced by activator binding help stably orient pol II prior to transcription initiation.}, author = {Bernecky, Carrie A and Taatjes, Dylan}, journal = {Journal of Molecular Biology}, number = {5}, pages = {387 -- 394}, publisher = {Elsevier}, title = {{Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly}}, doi = {10.1016/j.jmb.2012.02.014}, volume = {417}, year = {2012}, } @article{6136, abstract = {Tonic receptors convey stimulus duration and intensity and are implicated in homeostatic control. However, how tonic homeostatic signals are generated and how they reconfigure neural circuits and modify animal behavior is poorly understood. Here we show that Caenorhabditis elegans O2-sensing neurons are tonic receptors that continuously signal ambient [O2] to set the animal's behavioral state. Sustained signaling relied on a Ca2+ relay involving L-type voltage-gated Ca2+ channels, the ryanodine and the inositol-1,4,5-trisphosphate receptors. Tonic activity evoked continuous neuropeptide release, which helps elicit the enduring behavioral state associated with high [O2]. Sustained O2 receptor signaling was propagated to downstream neural circuits, including the hub interneuron RMG. O2 receptors evoked similar locomotory states at particular O2 concentrations, regardless of previous d[O2]/dt. However, a phasic component of the URX receptors' response to high d[O2]/dt, as well as tonic-to-phasic transformations in downstream interneurons, enabled transient reorientation movements shaped by d[O2]/dt. Our results highlight how tonic homeostatic signals can generate both transient and enduring behavioral change.}, author = {Busch, Karl Emanuel and Laurent, Patrick and Soltesz, Zoltan and Murphy, Robin Joseph and Faivre, Olivier and Hedwig, Berthold and Thomas, Martin and Smith, Heather L and de Bono, Mario}, issn = {1097-6256}, journal = {Nature Neuroscience}, number = {4}, pages = {581--591}, publisher = {Springer Nature}, title = {{Tonic signaling from O2 sensors sets neural circuit activity and behavioral state}}, doi = {10.1038/nn.3061}, volume = {15}, year = {2012}, }