TY - JOUR AB - Recent studies aimed at investigating artificial analogs of bacterial colonies have shown that low-density suspensions of self-propelled particles confined in two dimensions can assemble into finite aggregates that merge and split, but have a typical size that remains constant (living clusters). In this Letter, we address the problem of the formation of living clusters and crystals of active particles in three dimensions. We study two systems: self-propelled particles interacting via a generic attractive potential and colloids that can move toward each other as a result of active agents (e.g., by molecular motors). In both cases, fluidlike “living” clusters form. We explain this general feature in terms of the balance between active forces and regression to thermodynamic equilibrium. This balance can be quantified in terms of a dimensionless number that allows us to collapse the observed clustering behavior onto a universal curve. We also discuss how active motion affects the kinetics of crystal formation. AU - Mognetti, B. M. AU - Šarić, Anđela AU - Angioletti-Uberti, S. AU - Cacciuto, A. AU - Valeriani, C. AU - Frenkel, D. ID - 10384 IS - 24 JF - Physical Review Letters KW - general physics and astronomy SN - 0031-9007 TI - Living clusters and crystals from low-density suspensions of active colloids VL - 111 ER - TY - JOUR AB - In this paper we review recent numerical and theoretical developments of particle self-assembly on fluid and elastic membranes and compare them to available experimental realizations. We discuss the problem and its applications in biology and materials science, and give an overview of numerical models and strategies to study these systems across all length-scales. As this is a very broad field, this review focuses exclusively on surface-driven aggregation of nanoparticles that are at least one order of magnitude larger than the surface thickness and are adsorbed onto it. In this regime, all chemical details of the surface can be ignored in favor of a coarse-grained representation, and the collective behavior of many particles can be monitored and analyzed. We review the existing literature on how the mechanical properties and the geometry of the surface affect the structure of the particle aggregates and how these can drive shape deformation on the surface. AU - Šarić, Anđela AU - Cacciuto, Angelo ID - 10386 IS - 29 JF - Soft Matter KW - condensed matter physics KW - general chemistry SN - 1744-683X TI - Self-assembly of nanoparticles adsorbed on fluid and elastic membranes VL - 9 ER - TY - JOUR AB - We show how self-assembly of sticky nanoparticles can drive radial collapse of thin-walled nanotubes. Using numerical simulations, we study the transition as a function of the geometric and elastic parameters of the nanotube and the binding strength of the nanoparticles. We find that it is possible to derive a simple scaling law relating all these parameters, and estimate bounds for the onset conditions leading to the collapse of the nanotube. We also study the reverse process – the nanoparticle release from the folded state – and find that the stability of the collapsed state can be greatly improved by increasing the bending rigidity of the nanotubes. Our results suggest ways to strengthen the mechanical properties of nanotubes, but also indicate that the control of nanoparticle self-assembly on these nanotubes can lead to nanoparticle-laden responsive materials. AU - Napoli, Joseph A. AU - Šarić, Anđela AU - Cacciuto, Angelo ID - 10385 IS - 37 JF - Soft Matter KW - condensed matter physics KW - general chemistry SN - 1744-683X TI - Collapsing nanoparticle-laden nanotubes VL - 9 ER - TY - JOUR AB - Stimfit is a free cross-platform software package for viewing and analyzing electrophysiological data. It supports most standard file types for cellular neurophysiology and other biomedical formats. Its analysis algorithms have been used and validated in several experimental laboratories. Its embedded Python scripting interface makes Stimfit highly extensible and customizable. AU - Schlögl, Alois AU - Jonas, Peter M AU - Schmidt-Hieber, C. AU - Guzman, S. J. ID - 10396 IS - SI-1-Track-G JF - Biomedical Engineering / Biomedizinische Technik KW - biomedical engineering KW - data analysis KW - free software SN - 0013-5585 TI - Stimfit: A fast visualization and analysis environment for cellular neurophysiology VL - 58 ER - TY - CONF AB - Fluxoid quantization provides a direct means to study phase coherence. In cuprate superconductors, there have been observations which suggest that phase coherent superconducting fluctuations may persist at temperatures significantly above Tc. The focus of this work is to study the vortex states in mesoscopic cuprate superconducting samples to directly probe phase coherence over a wide range of temperatures. We present cantilever torque susceptometry measurements of micron and sub-micron size Bi2212 rings and disks. The high sensitivity of this technique allowed observation of transitions between different fluxoid states of a single ring, and the discrete vortex states of micron size disks. The dependence of magnetic susceptibility on diameter and wall thickness of the ring was investigated. Measurements were made at different values of the in-plane magnetic field, and over a wide range of temperatures. AU - Polshyn, Hryhoriy AU - Budakian, Raffi AU - Gu, Genda ID - 10749 IS - 1 SN - 0003-0503 T2 - APS March Meeting 2013 TI - Cantilever micro-susceptometry of mesoscopic Bi2212 samples VL - 58 ER - TY - JOUR AB - Due to their sessile lifestyles, plants need to deal with the limitations and stresses imposed by the changing environment. Plants cope with these by a remarkable developmental flexibility, which is embedded in their strategy to survive. Plants can adjust their size, shape and number of organs, bend according to gravity and light, and regenerate tissues that were damaged, utilizing a coordinating, intercellular signal, the plant hormone, auxin. Another versatile signal is the cation, Ca2+, which is a crucial second messenger for many rapid cellular processes during responses to a wide range of endogenous and environmental signals, such as hormones, light, drought stress and others. Auxin is a good candidate for one of these Ca2+-activating signals. However, the role of auxin-induced Ca2+ signaling is poorly understood. Here, we will provide an overview of possible developmental and physiological roles, as well as mechanisms underlying the interconnection of Ca2+ and auxin signaling. AU - Vanneste, Steffen AU - Friml, Jiří ID - 10895 IS - 4 JF - Plants KW - Plant Science KW - Ecology KW - Ecology KW - Evolution KW - Behavior and Systematics SN - 2223-7747 TI - Calcium: The missing link in auxin action VL - 2 ER - TY - CONF AB - A prominent remedy to multicore scalability issues in concurrent data structure implementations is to relax the sequential specification of the data structure. We present distributed queues (DQ), a new family of relaxed concurrent queue implementations. DQs implement relaxed queues with linearizable emptiness check and either configurable or bounded out-of-order behavior or pool behavior. Our experiments show that DQs outperform and outscale in micro- and macrobenchmarks all strict and relaxed queue as well as pool implementations that we considered. AU - Haas, Andreas AU - Lippautz, Michael AU - Henzinger, Thomas A AU - Payer, Hannes AU - Sokolova, Ana AU - Kirsch, Christoph M. AU - Sezgin, Ali ID - 10898 IS - 5 SN - 978-145032053-5 T2 - Proceedings of the ACM International Conference on Computing Frontiers - CF '13 TI - Distributed queues in shared memory: Multicore performance and scalability through quantitative relaxation ER - TY - CHAP AU - Barton, Nicholas H ID - 10899 KW - Adaptive landscape KW - Cline KW - Coalescent process KW - Gene flow KW - Hybrid zone KW - Local adaptation KW - Natural selection KW - Neutral theory KW - Population structure KW - Speciation SN - 978-0-12-384720-1 T2 - Encyclopedia of Biodiversity TI - Differentiation ER - TY - JOUR AB - Faithful execution of developmental gene expression programs occurs at multiple levels and involves many different components such as transcription factors, histone-modification enzymes, and mRNA processing proteins. Recent evidence suggests that nucleoporins, well known components that control nucleo-cytoplasmic trafficking, have wide-ranging functions in developmental gene regulation that potentially extend beyond their role in nuclear transport. Whether the unexpected role of nuclear pore proteins in transcription regulation, which initially has been described in fungi and flies, also applies to human cells is unknown. Here we show at a genome-wide level that the nuclear pore protein NUP98 associates with developmentally regulated genes active during human embryonic stem cell differentiation. Overexpression of a dominant negative fragment of NUP98 levels decreases expression levels of NUP98-bound genes. In addition, we identify two modes of developmental gene regulation by NUP98 that are differentiated by the spatial localization of NUP98 target genes. Genes in the initial stage of developmental induction can associate with NUP98 that is embedded in the nuclear pores at the nuclear periphery. Alternatively, genes that are highly induced can interact with NUP98 in the nuclear interior, away from the nuclear pores. This work demonstrates for the first time that NUP98 dynamically associates with the human genome during differentiation, revealing a role of a nuclear pore protein in regulating developmental gene expression programs. AU - Liang, Yun AU - Franks, Tobias M. AU - Marchetto, Maria C. AU - Gage, Fred H. AU - HETZER, Martin W ID - 11086 IS - 2 JF - PLoS Genetics KW - Cancer Research KW - Genetics (clinical) KW - Genetics KW - Molecular Biology KW - Ecology KW - Evolution KW - Behavior and Systematics SN - 1553-7404 TI - Dynamic association of NUP98 with the human genome VL - 9 ER - TY - JOUR AB - Intracellular proteins with long lifespans have recently been linked to age-dependent defects, ranging from decreased fertility to the functional decline of neurons. Why long-lived proteins exist in metabolically active cellular environments and how they are maintained over time remains poorly understood. Here, we provide a system-wide identification of proteins with exceptional lifespans in the rat brain. These proteins are inefficiently replenished despite being translated robustly throughout adulthood. Using nucleoporins as a paradigm for long-term protein persistence, we found that nuclear pore complexes (NPCs) are maintained over a cell’s life through slow but finite exchange of even its most stable subcomplexes. This maintenance is limited, however, as some nucleoporin levels decrease during aging, providing a rationale for the previously observed age-dependent deterioration of NPC function. Our identification of a long-lived proteome reveals cellular components that are at increased risk for damage accumulation, linking long-term protein persistence to the cellular aging process. AU - Toyama, Brandon H. AU - Savas, Jeffrey N. AU - Park, Sung Kyu AU - Harris, Michael S. AU - Ingolia, Nicholas T. AU - Yates, John R. AU - HETZER, Martin W ID - 11087 IS - 5 JF - Cell KW - General Biochemistry KW - Genetics and Molecular Biology SN - 0092-8674 TI - Identification of long-lived proteins reveals exceptional stability of essential cellular structures VL - 154 ER - TY - JOUR AB - During mitotic exit, missegregated chromosomes can recruit their own nuclear envelope (NE) to form micronuclei (MN). MN have reduced functioning compared to primary nuclei in the same cell, although the two compartments appear to be structurally comparable. Here we show that over 60% of MN undergo an irreversible loss of compartmentalization during interphase due to NE collapse. This disruption of the MN, which is induced by defects in nuclear lamina assembly, drastically reduces nuclear functions and can trigger massive DNA damage. MN disruption is associated with chromatin compaction and invasion of endoplasmic reticulum (ER) tubules into the chromatin. We identified disrupted MN in both major subtypes of human non-small-cell lung cancer, suggesting that disrupted MN could be a useful objective biomarker for genomic instability in solid tumors. Our study shows that NE collapse is a key event underlying MN dysfunction and establishes a link between aberrant NE organization and aneuploidy. AU - Hatch, Emily M. AU - Fischer, Andrew H. AU - Deerinck, Thomas J. AU - HETZER, Martin W ID - 11085 IS - 1 JF - Cell KW - General Biochemistry KW - Genetics and Molecular Biology SN - 0092-8674 TI - Catastrophic nuclear envelope collapse in cancer cell micronuclei VL - 154 ER - TY - JOUR AB - The crowded intracellular environment poses a formidable challenge to experimental and theoretical analyses of intracellular transport mechanisms. Our measurements of single-particle trajectories in cytoplasm and their random-walk interpretations elucidate two of these mechanisms: molecular diffusion in crowded environments and cytoskeletal transport along microtubules. We employed acousto-optic deflector microscopy to map out the three-dimensional trajectories of microspheres migrating in the cytosolic fraction of a cellular extract. Classical Brownian motion (BM), continuous time random walk, and fractional BM were alternatively used to represent these trajectories. The comparison of the experimental and numerical data demonstrates that cytoskeletal transport along microtubules and diffusion in the cytosolic fraction exhibit anomalous (nonFickian) behavior and posses statistically distinct signatures. Among the three random-walk models used, continuous time random walk provides the best representation of diffusion, whereas microtubular transport is accurately modeled with fractional BM. AU - Regner, Benjamin M. AU - Vučinić, Dejan AU - Domnisoru, Cristina AU - Bartol, Thomas M. AU - HETZER, Martin W AU - Tartakovsky, Daniel M. AU - Sejnowski, Terrence J. ID - 11088 IS - 8 JF - Biophysical Journal KW - Biophysics SN - 0006-3495 TI - Anomalous diffusion of single particles in cytoplasm VL - 104 ER - TY - JOUR AB - Nuclear pore complex (NPC) proteins are known for their critical roles in regulating nucleocytoplasmic traffic of macromolecules across the nuclear envelope. However, recent findings suggest that some nucleoporins (Nups), including Nup98, have additional functions in developmental gene regulation. Nup98, which exhibits transcription-dependent mobility at the NPC but can also bind chromatin away from the nuclear envelope, is frequently involved in chromosomal translocations in a subset of patients suffering from acute myeloid leukemia (AML). A common paradigm suggests that Nup98 translocations cause aberrant transcription when they are recuited to aberrant genomic loci. Importantly, this model fails to account for the potential loss of wild type (WT) Nup98 function in the presence of Nup98 translocation mutants. Here we examine how the cell might regulate Nup98 nucleoplasmic protein levels to control transcription in healthy cells. In addition, we discuss the possibility that dominant negative Nup98 fusion proteins disrupt the transcriptional activity of WT Nup98 in the nucleoplasm to drive AML. AU - Franks, Tobias M. AU - HETZER, Martin W ID - 11083 IS - 3 JF - Trends in Cell Biology KW - Cell Biology SN - 0962-8924 TI - The role of Nup98 in transcription regulation in healthy and diseased cells VL - 23 ER - TY - JOUR AB - Protein turnover is an effective way of maintaining a functional proteome, as old and potentially damaged polypeptides are destroyed and replaced by newly synthesized copies. An increasing number of intracellular proteins, however, have been identified that evade this turnover process and instead are maintained over a cell's lifetime. This diverse group of long-lived proteins might be particularly prone to accumulation of damage and thus have a crucial role in the functional deterioration of key regulatory processes during ageing. AU - Toyama, Brandon H. AU - HETZER, Martin W ID - 11084 JF - Nature Reviews Molecular Cell Biology KW - Cell Biology KW - Molecular Biology SN - 1471-0072 TI - Protein homeostasis: Live long, won't prosper VL - 14 ER - TY - JOUR AB - We present the design and performance characterization of a new experimental technique for measuring individual particle charges in large ensembles of macroscopic grains. The measurement principle is qualitatively similar to that used in determining the elementary charge by Millikan in that it follows individual particle trajectories. However, by taking advantage of new technology we are able to work with macroscopic grains and achieve several orders of magnitude better resolution in charge to mass ratios. By observing freely falling grains accelerated in a horizontal electric field with a co-falling, high-speed video camera, we dramatically increase particle tracking time and measurement precision. Keeping the granular medium under vacuum, we eliminate air drag, leaving the electrostatic force as the primary source of particle accelerations in the co-moving frame. Because the technique is based on direct imaging, we can distinguish between different particle types during the experiment, opening up the possibility of studying charge transfer processes between different particle species. For the ∼300 μm diameter grains reported here, we achieve an average acceleration resolution of ∼0.008 m/s2, a force resolution of ∼500 pN, and a median charge resolution ∼6× 104 elementary charges per grain (corresponding to surface charge densities ∼1 elementary charges per μm2). The primary source of error is indeterminacy in the grain mass, but with higher resolution cameras and better optics this can be further improved. The high degree of resolution and the ability to visually identify particles of different species or sizes with direct imaging make this a powerful new tool to characterize charging processes in granular media. AU - Waitukaitis, Scott R AU - Jaeger, Heinrich ID - 115 IS - 2 JF - Review of Scientific Instruments TI - In situ granular charge measurement by free-fall videography VL - 84 ER - TY - JOUR AB - We present the spatially resolved Hα dynamics of 16 star-forming galaxies at z ∼ 0.81 using the new KMOS multi-object integral field spectrograph on the ESO Very Large Telescope. These galaxies, selected using 1.18 μm narrowband imaging from the 10 deg2 CFHT-HiZELS survey of the SA 22 hr field, are found in a ∼4 Mpc overdensity of Hα emitters and likely reside in a group/intermediate environment, but not a cluster. We confirm and identify a rich group of star-forming galaxies at z = 0.813 ± 0.003, with 13 galaxies within 1000 km s−1 of each other, and seven within a diameter of 3 Mpc. All of our galaxies are “typical” star-forming galaxies at their redshift, 0.8 ± 0.4 SFR$^*_{z = 0.8}$, spanning a range of specific star formation rates (sSFRs) of 0.2–1.1 Gyr−1 and have a median metallicity very close to solar of 12 + log(O/H) = 8.62 ± 0.06. We measure the spatially resolved Hα dynamics of the galaxies in our sample and show that 13 out of 16 galaxies can be described by rotating disks and use the data to derive inclination corrected rotation speeds of 50–275 km s−1. The fraction of disks within our sample is 75% ± 8%, consistent with previous results based on Hubble Space Telescope morphologies of Hα-selected galaxies at z ∼ 1 and confirming that disks dominate the SFR density at z ∼ 1. Our Hα galaxies are well fitted by the z ∼ 1–2 Tully–Fisher (TF) relation, confirming the evolution seen in the zero point. Apart from having, on average, higher stellar masses and lower sSFRs, our group galaxies at z = 0.81 present the same mass–metallicity and TF relation as z ∼ 1 field galaxies and are all disk galaxies. AU - Sobral, D. AU - Swinbank, A. M. AU - Stott, J. P. AU - Matthee, Jorryt J AU - Bower, R. G. AU - Smail, Ian AU - Best, P. AU - Geach, J. E. AU - Sharples, R. M. ID - 11520 IS - 2 JF - The Astrophysical Journal KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution – galaxies KW - high-redshift – galaxies KW - starburst SN - 0004-637X TI - The dynamics of z=0.8 H-alpha-selected star-forming galaxies from KMOS/CF-HiZELS VL - 779 ER - TY - JOUR AB - We describe a model experiment for dynamic jamming: a two-dimensional collection of initially unjammed disks that are forced into the jammed state by uniaxial compression via a rake. This leads to a stable densification front that travels ahead of the rake, leaving regions behind it jammed. Using disk conservation in conjunction with an upper limit to the packing fraction at jamming onset, we predict the front speed as a function of packing fraction and rake speed. However, we find that the jamming front has a finite width, a feature that cannot be explained by disk conservation alone. This width appears to diverge on approach to jamming, which suggests that it may be related to growing lengthscales encountered in other jamming studies. AU - Waitukaitis, Scott R AU - Roth, Leah AU - Vitelli, Vincenzo AU - Jaeger, Heinrich ID - 116 IS - 4 JF - EPL TI - Dynamic jamming fronts VL - 102 ER - TY - JOUR AB - Given only the URL of a Web page, can we identify its language? In this article we examine this question. URL-based language classification is useful when the content of the Web page is not available or downloading the content is a waste of bandwidth and time. We built URL-based language classifiers for English, German, French, Spanish, and Italian by applying a variety of algorithms and features. As algorithms we used machine learning algorithms which are widely applied for text classification and state-of-art algorithms for language identification of text. As features we used words, various sized n-grams, and custom-made features (our novel feature set). We compared our approaches with two baseline methods, namely classification by country code top-level domains and classification by IP addresses of the hosting Web servers. We trained and tested our classifiers in a 10-fold cross-validation setup on a dataset obtained from the Open Directory Project and from querying a commercial search engine. We obtained the lowest F1-measure for English (94) and the highest F1-measure for German (98) with the best performing classifiers. We also evaluated the performance of our methods: (i) on a set of Web pages written in Adobe Flash and (ii) as part of a language-focused crawler. In the first case, the content of the Web page is hard to extract and in the second page downloading pages of the “wrong” language constitutes a waste of bandwidth. In both settings the best classifiers have a high accuracy with an F1-measure between 95 (for English) and 98 (for Italian) for the Adobe Flash pages and a precision between 90 (for Italian) and 97 (for French) for the language-focused crawler. AU - Baykan, Eda AU - Weber, Ingmar AU - Henzinger, Monika H ID - 11671 IS - 1 JF - ACM Transactions on the Web KW - Computer Networks and Communications SN - 1559-1131 TI - A comprehensive study of techniques for URL-based web page language classification VL - 7 ER - TY - CONF AB - The packing arrangement of individual particles inside a granular material and the resulting response to applied stresses depend critically on particle-particle interactions. One aspect that recently received attention are nanoscale surface features of particles, which play an important role in determining the strength of cohesive van der Waals and capillary interactions and also affect tribo-charging of grains. We describe experiments on freely falling granular streams that can detect the contributions from all three of these forces. We show that it is possible to measure the charge of individual grains and build up distributions that are detailed enough to provide stringent tests of tribo-charging models currently available. A second aspect concerns particle shape. In this case steric interactions become important and new types of aggregate behavior can be expected when non-convex particle shapes are considered that can interlock or entangle. However, a general connection between the mechanical response of a granular material and the constituents\' shape remains unknown. This has made it infeasible to tackle the "inverse packing problem", namely to start from a given, desired behavior for the aggregate as a whole and then find the particle shape the produces it. We discuss a new approach, using concepts rooted in artificial evolution that provides a way to solve this inverse problem. This approach facilitates exploring the role of arbitrary particle geometry in jammed systems and invites the discovery and design of granular matter with optimized properties. AU - Jaeger, Heinrich AU - Miskin, Marc AU - Waitukaitis, Scott R ID - 117 T2 - AIP Conference Proceedings TI - From nanoscale cohesion to macroscale entanglement: opportunities for designing granular aggregate behaviour by tailoring grain shape and interactions VL - 1542 ER - TY - JOUR AB - Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism—as any other mechanism that computes such an outcome for settings with budgets—is incentive compatible. AU - Dütting, Paul AU - Henzinger, Monika H AU - Weber, Ingmar ID - 11759 IS - 3 JF - Information Processing Letters SN - 0020-0190 TI - Sponsored search, market equilibria, and the Hungarian Method VL - 113 ER - TY - CONF AB - We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We show (1 + ε)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. This breaks the Θ(D) time bound of recomputing “from scratch”. Our technique also leads to a (1 + ε)-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of [9] that is optimal under some assumptions [27]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11793 SN - 1611-3349 T2 - 40th International Colloquium on Automata, Languages, and Programming TI - Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks VL - 7966 ER - TY - CONF AB - The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes. AU - Dütting, Paul AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11791 SN - 1611-3349 T2 - 9th International Conference on Web and Internet Economics TI - Valuation compressions in VCG-based combinatorial auctions VL - 8289 ER - TY - CONF AB - We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithm. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1𝑒√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1 − 1/e + ε)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting. AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Williamson, David P. ID - 11792 SN - 1611-3349 T2 - 21st Annual European Symposium on Algorithms TI - Maximizing a submodular function with viability constraints VL - 8125 ER - TY - CONF AB - We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n)) ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11856 SN - 0272-5428 T2 - 54th Annual Symposium on Foundations of Computer Science TI - Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization ER - TY - JOUR AB - We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions ui,j(pj) expressing his utility of being matched to item j at price pj. For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under which every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders. AU - Dütting, Paul AU - Henzinger, Monika H AU - Weber, Ingmar ID - 11902 IS - 3 JF - Theoretical Computer Science SN - 0304-3975 TI - Bidder optimal assignments for general utilities VL - 478 ER - TY - JOUR AB - No catalyst required! A highly efficient, catalyst-free process to generate diimide in situ from hydrazine monohydrate and molecular oxygen for the selective reduction of alkenes has been developed. The use of a gas–liquid segmented flow system allowed safe operating conditions and dramatically enhanced this atom-economical reaction, resulting in short processing times. AU - Pieber, Bartholomäus AU - Martinez, Sabrina Teixeira AU - Cantillo, David AU - Kappe, C. Oliver ID - 11959 IS - 39 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - In situ generation of diimide from hydrazine and oxygen: Continuous-flow transfer hydrogenation of olefins VL - 52 ER - TY - JOUR AB - It's not magic! The effects observed in microwave-irradiated chemical transformations can in most cases be rationalized by purely bulk thermal phenomena associated with rapid heating to elevated temperatures. As discussed in this Essay, the existence of so-called nonthermal or specific microwave effects is highly doubtful. AU - Kappe, C. Oliver AU - Pieber, Bartholomäus AU - Dallinger, Doris ID - 11960 IS - 4 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Microwave effects in organic synthesis: Myth or reality? VL - 52 ER - TY - JOUR AB - The use of high-temperature/pressure gas–liquid continuous flow conditions dramatically enhances the iron-catalyzed aerobic oxidation of 2-benzylpyridines to their corresponding ketones. Pressurized air serves as a readily available oxygen source and propylene carbonate as a green solvent in this radically intensified preparation of synthetically valuable 2-aroylpyridines. AU - Pieber, Bartholomäus AU - Kappe, C. Oliver ID - 11973 IS - 2 JF - Green Chemistry SN - 1463-9262 TI - Direct aerobic oxidation of 2-benzylpyridines in a gas-liquid continuous-flow regime using propylene carbonate as a solvent VL - 15 ER - TY - JOUR AB - Near-surface air temperature, typically measured at a height of 2 m, is the most important control on the energy exchange and the melt rate at a snow or ice surface. It is distributed in a simplistic manner in most glacier melt models by using constant linear lapse rates, which poorly represent the actual spatial and temporal variability of air temperature. In this paper, we test a simple thermodynamic model proposed by Greuell and Böhm in 1998 as an alternative, using a new dataset of air temperature measurements from along the flowline of Haut Glacier d’Arolla, Switzerland. The unmodified model performs little better than assuming a constant linear lapse rate. When modified to allow the ratio of the boundary layer height to the bulk heat transfer coefficient to vary along the flowline, the model matches measured air temperatures better, and a further reduction of the root-mean-square error is obtained, although there is still considerable scope for improvement. The modified model is shown to perform best under conditions favourable to the development of katabatic winds – few clouds, positive ambient air temperature, limited influence of synoptic or valley winds and a long fetch – but its performance is poor under cloudy conditions. AU - Petersen, Lene AU - Pellicciotti, Francesca AU - Juszak, Inge AU - Carenzo, Marco AU - Brock, Ben ID - 12642 IS - 63 JF - Annals of Glaciology KW - Earth-Surface Processes SN - 0260-3055 TI - Suitability of a constant air temperature lapse rate over an Alpine glacier: Testing the Greuell and Böhm model as an alternative VL - 54 ER - TY - JOUR AB - Parameterizations of incoming longwave radiation are increasingly receiving attention for both low and high elevation glacierized sites. In this paper, we test 13 clear-sky parameterizations combined with seven cloud corrections for all-sky atmospheric emissivity at one location on Haut Glacier d'Arolla. We also analyze the four seasons separately and conduct a cross-validation to test the parameters’ robustness. The best parameterization is the one by Dilley and O'Brien, B for clear-sky conditions combined with Unsworth and Monteith cloud correction. This model is also the most robust when tested in cross-validation. When validated at different sites in the southern Alps of Switzerland and north-western Italian Alps, all parameterizations show a substantial decrease in performance, except for one site, thus suggesting that it is important to recalibrate parameterizations of incoming longwave radiation for different locations. We argue that this is due to differences in the structure of the atmosphere at the sites. We also quantify the effect that the incoming longwave radiation parameterizations have on energy-balance melt modeling, and show that recalibration of model parameters is needed. Using parameters from other sites leads to a significant underestimation of melt and to an error that is larger than that associated with using different parameterizations. Once recalibrated, however, the parameters of most models seem to be stable over seasons and years at the location on Haut Glacier d'Arolla. AU - Juszak, I. AU - Pellicciotti, Francesca ID - 12643 IS - 8 JF - Journal of Geophysical Research: Atmospheres KW - Space and Planetary Science KW - Earth and Planetary Sciences (miscellaneous) KW - Atmospheric Science KW - Geophysics SN - 2169-897X TI - A comparison of parameterizations of incoming longwave radiation over melting glaciers: Model robustness and seasonal variability VL - 118 ER - TY - JOUR AB - Greater Himalayan glaciers are retreating and losing mass at rates comparable to glaciers in other regions of the world1,2,3,4,5. Assessments of future changes and their associated hydrological impacts are scarce, oversimplify glacier dynamics or include a limited number of climate models6,7,8,9. Here, we use results from the latest ensemble of climate models in combination with a high-resolution glacio-hydrological model to assess the hydrological impact of climate change on two climatically contrasting watersheds in the Greater Himalaya, the Baltoro and Langtang watersheds that drain into the Indus and Ganges rivers, respectively. We show that the largest uncertainty in future runoff is a result of variations in projected precipitation between climate models. In both watersheds, strong, but highly variable, increases in future runoff are projected and, despite the different characteristics of the watersheds, their responses are surprisingly similar. In both cases, glaciers will recede but net glacier melt runoff is on a rising limb at least until 2050. In combination with a positive change in precipitation, water availability during this century is not likely to decline. We conclude that river basins that depend on monsoon rains and glacier melt will continue to sustain the increasing water demands expected in these areas10. AU - Immerzeel, W. W. AU - Pellicciotti, Francesca AU - Bierkens, M. F. P. ID - 12640 IS - 9 JF - Nature Geoscience KW - General Earth and Planetary Sciences SN - 1752-0894 TI - Rising river flows throughout the twenty-first century in two Himalayan glacierized watersheds VL - 6 ER - TY - JOUR AB - We investigate the sensitivity of a distributed enhanced temperature-index (ETI) melt model, in order to understand which parameters have the largest influence on model outputs and thus need to be accurately known. We use melt and meteorological data from two Alpine glaciers and one glacier in the Andes of Chile. Sensitivity analysis is conducted in a systematic way in terms of parameters and the different conditions (day, night, clear-sky, overcast), melt seasons and glaciers examined. The sensitivity of total melt to changes in individual parameters is calculated using a local method around the optimal value of the parameters. We verify that the parameters are optimal at the distributed scale and assess the model uncertainty induced by uncertainty in the parameters using a Monte Carlo technique. Model sensitivity to parameters is consistent across melt seasons, glaciers, different conditions and the daily statistics examined. The parameters to which the model is most sensitive are the shortwave-radiation factor, the temperature lapse rate for extrapolation of air temperature, the albedo parameters, the temperature threshold and the cloud transmittance factor parameters. A parameter uncertainty of 5% results in a model uncertainty of 5.6% of mean melt on Haut Glacier d’Arolla, Switzerland. AU - Heynen, Martin AU - Pellicciotti, Francesca AU - Carenzo, Marco ID - 12641 IS - 63 JF - Annals of Glaciology SN - 0260-3055 TI - Parameter sensitivity of a distributed enhanced temperature-index melt model VL - 54 ER - TY - JOUR AB - When confronted with a large-field stimulus rotating around the vertical body axis, flies display a following behavior called "optomotor response." As neural control elements, the large tangential horizontal system (HS) cells of the lobula plate have been prime candidates for long. Here, we applied optogenetic stimulation of HS cells to evaluate their behavioral role in Drosophila. To minimize interference of the optical activation of channelrhodopsin-2 with the visual perception of the flies, we used a bistable variant called ChR2-C128S. By applying pulses of blue and yellow light, we first demonstrate electrophysiologically that lobula plate tangential cells can be activated and deactivated repeatedly with no evident change in depolarization strength over trials. We next show that selective optogenetic activation of HS cells elicits robust yaw head movements and yaw turning responses in fixed and tethered flying flies, respectively. AU - Haikala, Väinö AU - Maximilian Jösch AU - Borst, Alexander AU - Mauss, Alex S ID - 1304 IS - 34 JF - Journal of Neuroscience TI - Optogenetic control of fly optomotor responses VL - 33 ER - TY - JOUR AB - In the fly Drosophila melanogaster, photoreceptor input to motion vision is split into two parallel pathways as represented by first-order interneurons L1 and L2 (Rister et al., 2007; Joesch et al., 2010). However, how these pathways are functionally specialized remains controversial. One study (Eichner et al., 2011) proposed that the L1-pathway evaluates only sequences of brightness increments (ON-ON), while the L2-pathway processes exclusively brightness decrements (OFF-OFF). Another study (Clark et al., 2011) proposed that each of the two pathways evaluates both ON-ON and OFF-OFF sequences. To decide between these alternatives, we recorded from motionsensitive neurons in flies in which the output from either L1 or L2 was genetically blocked. We found that blocking L1 abolishes ON-ON responses but leaves OFF-OFF responses intact. The opposite was true, when the output from L2 was blocked. We conclude that the L1 and L2 pathways are functionally specialized to detect ON-ON and OFF-OFF sequences, respectively. AU - Maximilian Jösch AU - Weber, Franz AU - Eichner, Hubert AU - Borst, Alexander ID - 1305 IS - 3 JF - Journal of Neuroscience TI - Functional specialization of parallel motion detection circuits in the fly VL - 33 ER - TY - JOUR AB - We derive sufficient conditions for advection-driven backward motion of the free boundary in a chemotaxis model with degenerate mobility. In this model, a porous-medium-type diffusive term and an advection term are in competition. The former induces forward motion, the latter may induce backward motion of the free boundary depending on the direction of advection. We deduce conditions on the growth of the initial data at the free boundary which ensure that at least initially the advection term is dominant. This implies local backward motion of the free boundary provided the advection is (locally) directed appropriately. Our result is based on a new class of moving test functions and Stampacchia's lemma. As a by-product of our estimates, we obtain quantitative bounds on the spreading of the support of solutions for the chemotaxis model and provide a proof for the finite speed of the support propagation property of solutions. AU - Julian Fischer ID - 1308 IS - 3 JF - SIAM Journal on Mathematical Analysis TI - Advection-driven support shrinking in a chemotaxis model with degenerate mobility VL - 45 ER - TY - JOUR AB - We prove uniqueness of solutions of the DLSS equation in a class of sufficiently regular functions. The global weak solutions of the DLSS equation constructed by Jüngel and Matthes belong to this class of uniqueness. We also show uniqueness of solutions for the quantum drift-diffusion equation, which contains additional drift and second-order diffusion terms. The results hold in case of periodic or Dirichlet-Neumann boundary conditions. Our proof is based on a monotonicity property of the DLSS operator and sophisticated approximation arguments; we derive a PDE satisfied by the pointwise square root of the solution, which enables us to exploit the monotonicity property of the operator. AU - Julian Fischer ID - 1307 IS - 11 JF - Communications in Partial Differential Equations TI - Uniqueness of solutions of the Derrida-Lebowitz-Speer-Spohn equation and quantum drift diffusion models VL - 38 ER - TY - JOUR AB - We derive lower bounds on asymptotic support propagation rates for strong solutions of the Cauchy problem for the thin-film equation. The bounds coincide up to a constant factor with the previously known upper bounds and thus are sharp. Our results hold in case of at most three spatial dimensions and n∈. (1, 2.92). The result is established using weighted backward entropy inequalities with singular weight functions to yield a differential inequality; combined with some entropy production estimates, the optimal rate of propagation is obtained. To the best of our knowledge, these are the first lower bounds on asymptotic support propagation rates for higher-order nonnegativity-preserving parabolic equations. AU - Julian Fischer ID - 1310 IS - 10 JF - Journal of Differential Equations TI - Optimal lower bounds on asymptotic support propagation rates for the thin-film equation VL - 255 ER - TY - CONF AB - We study two-player zero-sum games over infinite-state graphs equipped with ωB and finitary conditions. Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory suffices for finitary parity games. We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with ωB-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete. AU - Chatterjee, Krishnendu AU - Fijalkow, Nathanaël ID - 1374 T2 - 22nd EACSL Annual Conference on Computer Science Logic TI - Infinite-state games with finitary conditions VL - 23 ER - TY - CONF AB - It is often difficult to correctly implement a Boolean controller for a complex system, especially when concurrency is involved. Yet, it may be easy to formally specify a controller. For instance, for a pipelined processor it suffices to state that the visible behavior of the pipelined system should be identical to a non-pipelined reference system (Burch-Dill paradigm). We present a novel procedure to efficiently synthesize multiple Boolean control signals from a specification given as a quantified first-order formula (with a specific quantifier structure). Our approach uses uninterpreted functions to abstract details of the design. We construct an unsatisfiable SMT formula from the given specification. Then, from just one proof of unsatisfiability, we use a variant of Craig interpolation to compute multiple coordinated interpolants that implement the Boolean control signals. Our method avoids iterative learning and back-substitution of the control functions. We applied our approach to synthesize a controller for a simple two-stage pipelined processor, and present first experimental results. AU - Hofferek, Georg AU - Gupta, Ashutosh AU - Könighofer, Bettina AU - Jiang, Jie AU - Bloem, Roderick ID - 1385 T2 - 2013 Formal Methods in Computer-Aided Design TI - Synthesizing multiple boolean functions using interpolation on a single proof ER - TY - CONF AB - Choices made by nondeterministic word automata depend on both the past (the prefix of the word read so far) and the future (the suffix yet to be read). In several applications, most notably synthesis, the future is diverse or unknown, leading to algorithms that are based on deterministic automata. Hoping to retain some of the advantages of nondeterministic automata, researchers have studied restricted classes of nondeterministic automata. Three such classes are nondeterministic automata that are good for trees (GFT; i.e., ones that can be expanded to tree automata accepting the derived tree languages, thus whose choices should satisfy diverse futures), good for games (GFG; i.e., ones whose choices depend only on the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent deterministic automata). The theoretical properties and relative merits of the different classes are still open, having vagueness on whether they really differ from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also open is the possible succinctness of GFG and GFT automata compared to deterministic automata. We study these problems for ω-regular automata with all common acceptance conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction for GFG automata. AU - Boker, Udi AU - Kuperberg, Denis AU - Kupferman, Orna AU - Skrzypczak, Michał ID - 1387 IS - PART 2 TI - Nondeterminism in the presence of a diverse or unknown future VL - 7966 ER - TY - JOUR AB - We give a cohomological interpretation of both the Kac polynomial and the refined Donaldson-Thomas-invariants of quivers. This interpretation yields a proof of a conjecture of Kac from 1982 and gives a new perspective on recent work of Kontsevich-Soibelman. Thisis achieved by computing, via an arithmetic Fourier transform, the dimensions of the isotypical components of the cohomology of associated Nakajima quiver varieties under the action of a Weyl group. The generating function of the corresponding Poincare polynomials is an extension of Hua's formula for Kac polynomials of quivers involving Hall-Littlewood symmetric functions. The resulting formulae contain a wide range of information on the geometry of the quiver varieties. AU - Tamas Hausel AU - Letellier, Emmanuel AU - Rodríguez Villegas, Fernando ID - 1442 IS - 3 JF - Annals of Mathematics TI - Positivity for Kac polynomials and DT-invariants of quivers VL - 177 ER - TY - CHAP AB - Here we survey several results and conjectures on the cohomology of the total space of the Hitchin system: the moduli space of semi-stable rank n and degree d Higgs bundles on a complex algebraic curve C. The picture emerging is a dynamic mixture of ideas originating in theoretical physics such as gauge theory and mirror symmetry, Weil conjectures in arithmetic algebraic geometry, representation theory of finite groups of Lie type and Langlands duality in number theory. AU - Tamas Hausel ID - 1443 T2 - Handbook of Moduli: Volume II TI - Global topology of the Hitchin system VL - 25 ER - TY - JOUR AB - We study connections between the topology of generic character varieties of fundamental groups of punctured Riemann surfaces, Macdonald polynomials, quiver representations, Hilbert schemes on Cx × Cx, modular forms and multiplicities in tensor products of irreducible characters of finite general linear groups. AU - Tamas Hausel AU - Letellier, Emmanuel AU - Rodríguez Villegas, Fernando ID - 1469 JF - Advances in Mathematics TI - Arithmetic harmonic analysis on character and quiver varieties II VL - 234 ER - TY - JOUR AB - We show that a natural isomorphism between the rational cohomology groups of the two zero-dimensional Hilbert schemes of n-points of two surfaces, the affine plane minus the axes and the cotangent bundle of an elliptic curve, exchanges the weight filtration on the first set of cohomology groups with the perverse Leray filtration associated with a natural fibration on the second set of cohomology groups. We discuss some associated hard Lefschetz phenomena. AU - De Cataldo, Mark A AU - Tamas Hausel AU - Migliorini, Luca ID - 1470 JF - Journal of Singularities TI - Exchange between perverse and weight filtration for the Hilbert schemes of points of two surfaces VL - 7 ER - TY - JOUR AU - Aceto, Luca AU - Henzinger, Monika H AU - Sgall, Jiří ID - 11758 IS - 1 JF - Information and Computation SN - 0890-5401 TI - 38th International Colloquium on Automata, Languages and Programming VL - 222 ER - TY - JOUR AB - The development of a functional tissue requires coordination of the amplification of progenitors and their differentiation into specific cell types. The molecular basis for this coordination during myotome ontogeny is not well understood. Dermomytome progenitors that colonize the myotome first acquire myocyte identity and subsequently proliferate as Pax7-expressing progenitors before undergoing terminal differentiation. We show that the dynamics of sonic hedgehog (Shh) signaling is crucial for this transition in both avian and mouse embryos. Initially, Shh ligand emanating from notochord/floor plate reaches the dermomyotome, where it both maintains the proliferation of dermomyotome cells and promotes myogenic differentiation of progenitors that colonized the myotome. Interfering with Shh signaling at this stage produces small myotomes and accumulation of Pax7-expressing progenitors. An in vivo reporter of Shh activity combined with mouse genetics revealed the existence of both activator and repressor Shh activities operating on distinct subsets of cells during the epaxial myotomal maturation. In contrast to observations in mice, in avians Shh promotes the differentiation of both epaxial and hypaxial myotome domains. Subsequently, myogenic progenitors become refractory to Shh; this is likely to occur at the level of, or upstream of, smoothened signaling. The end of responsiveness to Shh coincides with, and is thus likely to enable, the transition into the growth phase of the myotome. AU - Kahane, Nitza AU - Ribes, Vanessa AU - Anna Kicheva AU - Briscoe, James AU - Kalcheim, Chaya ID - 1726 IS - 8 JF - Development TI - The transition from differentiation to growth during dermomyotome-derived myogenesis depends on temporally restricted hedgehog signaling VL - 140 ER - TY - JOUR AB - Cells at different positions in a developing tissue receive different concentrations of signaling molecules, called morphogens, and this influences their cell fate. Morphogen concentration gradients have been proposed to control patterning as well as growth in many developing tissues. Some outstanding questions about tissue patterning by morphogen gradients are the following: What are the mechanisms that regulate gradient formation and shape? Is the positional information encoded in the gradient sufficiently precise to determine the positions of target gene domain boundaries? What are the temporal dynamics of gradients and how do they relate to patterning and growth? These questions are inherently quantitative in nature and addressing them requires measuring morphogen concentrations in cells, levels of downstream signaling activity, and kinetics of morphogen transport. Here we first present methods for quantifying morphogen gradient shape in which the measurements can be calibrated to reflect actual morphogen concentrations. We then discuss using fluorescence recovery after photobleaching to study the kinetics of morphogen transport at the tissue level. Finally, we present particle tracking as a method to study morphogen intracellular trafficking. AU - Anna Kicheva AU - Holtzer, Laurent AU - Wartlick, Ortrud AU - Schmidt, Thomas S AU - González-Gaitán, Marcos A ID - 1727 IS - 5 JF - Cold Spring Harbor Protocols TI - Quantitative imaging of morphogen gradients in drosophila imaginal discs VL - 8 ER - TY - JOUR AB - We report on hole g-factor measurements in three terminal SiGe self-assembled quantum dot devices with a top gate electrode positioned very close to the nanostructure. Measurements of both the perpendicular as well as the parallel g-factor reveal significant changes for a small modulation of the top gate voltage. From the observed modulations, we estimate that, for realistic experimental conditions, hole spins can be electrically manipulated with Rabi frequencies in the order of 100 MHz. This work emphasises the potential of hole-based nano-devices for efficient spin manipulation by means of the g-tensor modulation technique. AU - Ares, Natalia AU - Georgios Katsaros AU - Golovach, Vitaly N AU - Zhang, Jianjun AU - Prager, Aaron A AU - Glazman, Leonid I AU - Schmidt, Oliver G AU - De Franceschi, Silvano ID - 1760 IS - 26 JF - Applied Physics Letters TI - SiGe quantum dots for fast hole spin Rabi oscillations VL - 103 ER - TY - JOUR AB - We report an electric-field-induced giant modulation of the hole g factor in SiGe nanocrystals. The observed effect is ascribed to a so-far overlooked contribution to the g factor that stems from the mixing between heavy- and light-hole wave functions. We show that the relative displacement between the confined heavy- and light-hole states, occurring upon application of the electric field, alters their mixing strength leading to a strong nonmonotonic modulation of the g factor. AU - Ares, Natalia AU - Golovach, Vitaly N AU - Georgios Katsaros AU - Stoffel, Mathieu AU - Fournel, Frank AU - Glazman, Leonid I AU - Schmidt, Oliver G AU - De Franceschi, Silvano ID - 1759 IS - 4 JF - Physical Review Letters TI - Nature of tunable hole g factors in quantum dots VL - 110 ER - TY - JOUR AB - The geometric aspects of quantum mechanics are emphasized most prominently by the concept of geometric phases, which are acquired whenever a quantum system evolves along a path in Hilbert space, that is, the space of quantum states of the system. The geometric phase is determined only by the shape of this path and is, in its simplest form, a real number. However, if the system has degenerate energy levels, then matrix-valued geometric state transformations, known as non-Abelian holonomies-the effect of which depends on the order of two consecutive paths-can be obtained. They are important, for example, for the creation of synthetic gauge fields in cold atomic gases or the description of non-Abelian anyon statistics. Moreover, there are proposals to exploit non-Abelian holonomic gates for the purposes of noise-resilient quantum computation. In contrast to Abelian geometric operations, non-Abelian ones have been observed only in nuclear quadrupole resonance experiments with a large number of spins, and without full characterization of the geometric process and its non-commutative nature. Here we realize non-Abelian non-adiabatic holonomic quantum operations on a single, superconducting, artificial three-level atom by applying a well-controlled, two-tone microwave drive. Using quantum process tomography, we determine fidelities of the resulting non-commuting gates that exceed 95 per cent. We show that two different quantum gates, originating from two distinct paths in Hilbert space, yield non-equivalent transformations when applied in different orders. This provides evidence for the non-Abelian character of the implemented holonomic quantum operations. In combination with a non-trivial two-quantum-bit gate, our method suggests a way to universal holonomic quantum computing. AU - Abdumalikov, Abdufarrukh A AU - Johannes Fink AU - Juliusson, K AU - Pechal, M AU - Berger, Stefan T AU - Wallraff, Andreas AU - Filipp, Stefan ID - 1785 IS - 7446 JF - Nature TI - Experimental realization of non-Abelian non-adiabatic geometric gates VL - 496 ER - TY - JOUR AB - When two indistinguishable single photons impinge at the two inputs of a beam splitter they coalesce into a pair of photons appearing in either one of its two outputs. This effect is due to the bosonic nature of photons and was first experimentally observed by Hong, Ou and Mandel. Here, we present the observation of the Hong-Ou-Mandel effect with two independent single-photon sources in the microwave frequency domain. We probe the indistinguishability of single photons, created with a controllable delay, in time-resolved second-order cross- and auto-correlation function measurements. Using quadrature amplitude detection we are able to resolve different photon numbers and detect coherence in and between the output arms. This scheme allows us to fully characterize the two-mode entanglement of the spatially separated beam-splitter output modes. Our experiments constitute a first step towards using two-photon interference at microwave frequencies for quantum communication and information processing. AU - Lang, C AU - Eichler, Christopher AU - Steffen, L. Kraig AU - Johannes Fink AU - Woolley, Matthew J AU - Blais, Alexandre AU - Wallraff, Andreas ID - 1787 IS - 6 JF - Nature Physics TI - Correlations, indistinguishability and entanglement in Hong-Ou-Mandel experiments at microwave frequencies VL - 9 ER - TY - JOUR AB - We report the experimental observation and a theoretical explanation of collective suppression of linewidths for multiple superconducting qubits coupled to a good cavity. This demonstrates how strong qubit-cavity coupling can significantly modify the dephasing and dissipation processes that might be expected for individual qubits, and can potentially improve coherence times in many-body circuit QED. AU - Nissen, Felix AU - Johannes Fink AU - Mlynek, Jonas A AU - Wallraff, Andreas AU - Keeling, Jonathan M ID - 1786 IS - 20 JF - Physical Review Letters TI - Collective suppression of linewidths in circuit QED VL - 110 ER - TY - JOUR AB - In the September 12, 2013 issue of Nature, the Epi4K Consortium (. Allen etal., 2013) reported sequencing 264patient trios with epileptic encephalopathies. The Consortium focused on genes exceptionally intolerant to sequence variations and found substantial interconnections with autism and intellectual disability gene networks. AU - Gaia Novarino AU - Baek, SeungTae AU - Gleeson, Joseph G ID - 1790 IS - 1 JF - Neuron TI - The sacred disease: The puzzling genetics of epileptic disorders VL - 80 ER - TY - JOUR AB - Complex I (NADH:ubiquinone oxidoreductase) is central to cellular energy production, being the first and largest enzyme of the respiratory chain in mitochondria. It couples electron transfer from NADH to ubiquinone with proton translocation across the inner mitochondrial membrane and is involved in a wide range of human neurodegenerative disorders. Mammalian complex I is composed of 44 different subunits, whereas the 'minimal' bacterial version contains 14 highly conserved 'core' subunits. The L-shaped assembly consists of hydrophilic and membrane domains. We have determined all known atomic structures of complex I, starting from the hydrophilic domain of Thermus thermophilus enzyme (eight subunits, nine Fe-S clusters), followed by the membrane domains of the Escherichia coli (six subunits, 55 transmembrane helices) and T. thermophilus (seven subunits, 64 transmembrane helices) enzymes, and finally culminating in a recent crystal structure of the entire intact complex I from T. thermophilus (536 kDa, 16 subunits, nine Fe-S clusters, 64 transmembrane helices). The structure suggests an unusual and unique coupling mechanism via longrange conformational changes. Determination of the structure of the entire complex was possible only through this step-by-step approach, building on from smaller subcomplexes towards the entire assembly. Large membrane proteins are notoriously difficult to crystallize, and so various non-standard and sometimes counterintuitive approaches were employed in order to achieve crystal diffraction to high resolution and solve the structures. These steps, as well as the implications from the final structure, are discussed in the present review. AU - Leonid Sazanov AU - Baradaran, Rozbeh AU - Efremov, Rouslan G AU - Berrisford, John M AU - Minhas, Gurdeep S ID - 1977 IS - 5 JF - Biochemical Society Transactions TI - A long road towards the structure of respiratory complex I, a giant molecular proton pump VL - 41 ER - TY - JOUR AB - Complex I is the first and largest enzyme of the respiratory chain and has a central role in cellular energy production through the coupling of NADH:ubiquinone electron transfer to proton translocation. It is also implicated in many common human neurodegenerative diseases. Here, we report the first crystal structure of the entire, intact complex I (from Thermus thermophilus) at 3.3 Å resolution. The structure of the 536-kDa complex comprises 16 different subunits, with a total of 64 transmembrane helices and 9 iron-sulphur clusters. The core fold of subunit Nqo8 (ND1 in humans) is, unexpectedly, similar to a half-channel of the antiporter-like subunits. Small subunits nearby form a linked second half-channel, which completes the fourth proton-translocation pathway (present in addition to the channels in three antiporter-like subunits). The quinone-binding site is unusually long, narrow and enclosed. The quinone headgroup binds at the deep end of this chamber, near iron-sulphur cluster N2. Notably, the chamber is linked to the fourth channel by a 'funnel' of charged residues. The link continues over the entire membrane domain as a flexible central axis of charged and polar residues, and probably has a leading role in the propagation of conformational changes, aided by coupling elements. The structure suggests that a unique, out-of-the-membrane quinone-reaction chamber enables the redox energy to drive concerted long-range conformational changes in the four antiporter-like domains, resulting in translocation of four protons per cycle. AU - Baradaran, Rozbeh AU - Berrisford, John M AU - Minhas, Gurdeep S AU - Leonid Sazanov ID - 1978 IS - 7438 JF - Nature TI - Crystal structure of the entire respiratory complex i VL - 494 ER - TY - JOUR AB - Although transitions of sex-determination mechanisms are frequent in species with homomorphic sex chromosomes, heteromorphic sex chromosomes are thought to represent a terminal evolutionary stage owing to chromosome-specific adaptations such as dosage compensation or an accumulation of sex-specific mutations. Here we show that an autosome of Drosophila, the dot chromosome, was ancestrally a differentiated X chromosome. We analyse the whole genome of true fruitflies (Tephritidae), flesh flies (Sarcophagidae) and soldier flies (Stratiomyidae) to show that genes located on the dot chromosome of Drosophila are X-linked in outgroup species, whereas Drosophila X-linked genes are autosomal. We date this chromosomal transition to early drosophilid evolution by sequencing the genome of other Drosophilidae. Our results reveal several puzzling aspects of Drosophila dot chromosome biology to be possible remnants of its former life as a sex chromosome, such as its minor feminizing role in sex determination or its targeting by a chromosome-specific regulatory mechanism. We also show that patterns of biased gene expression of the dot chromosome during early embryogenesis, oogenesis and spermatogenesis resemble that of the current X chromosome. Thus, although sex chromosomes are not necessarily evolutionary end points and can revert back to an autosomal inheritance, the highly specialized genome architecture of this former X chromosome suggests that severe fitness costs must be overcome for such a turnover to occur. AU - Beatriz Vicoso AU - Bachtrog, Doris ID - 1991 IS - 7458 JF - Nature TI - Reversal of an ancient sex chromosome to an autosome in Drosophila VL - 499 ER - TY - JOUR AB - The rod-shaped bacterium Escherichia coli selects the cell center as site of division with the help of the proteins MinC, MinD, and MinE. This protein system collectively oscillates between the two cell poles by alternately binding to the membrane in one of the two cell halves. This dynamic behavior, which emerges from the interaction of the ATPase MinD and its activator MinE on the cell membrane, has become a paradigm for protein self-organization. Recently, it has been found that not only the binding of MinD to the membrane, but also interactions of MinE with the membrane contribute to Min-protein self-organization. Here, we show that by accounting for this finding in a computational model, we can comprehensively describe all observed Min-protein patterns in vivo and in vitro. Furthermore, by varying the system's geometry, our computations predict patterns that have not yet been reported. We confirm these predictions experimentally. AU - Bonny, Mike AU - Fischer-Friedrich, Elisabeth AU - Martin Loose AU - Schwille, Petra AU - Kruse, Karsten ID - 1988 IS - 12 JF - PLoS Computational Biology TI - Membrane binding of MinE allows for a comprehensive description of Min-protein pattern formation VL - 9 ER - TY - JOUR AB - Many algorithms for inferring causality rely heavily on the faithfulness assumption. The main justification for imposing this assumption is that the set of unfaithful distributions has Lebesgue measure zero, since it can be seen as a collection of hypersurfaces in a hypercube. However, due to sampling error the faithfulness condition alone is not sufficient for statistical estimation, and strong-faithfulness has been proposed and assumed to achieve uniform or high-dimensional consistency. In contrast to the plain faithfulness assumption, the set of distributions that is not strong-faithful has nonzero Lebesgue measure and in fact, can be surprisingly large as we show in this paper. We study the strong-faithfulness condition from a geometric and combinatorial point of view and give upper and lower bounds on the Lebesgue measure of strong-faithful distributions for various classes of directed acyclic graphs. Our results imply fundamental limitations for the PC-algorithm and potentially also for other algorithms based on partial correlation testing in the Gaussian case. AU - Uhler, Caroline AU - Raskutti, Garvesh AU - Bühlmann, Peter AU - Yu, Bin ID - 2010 IS - 2 JF - The Annals of Statistics TI - Geometry of the faithfulness assumption in causal inference VL - 41 ER - TY - JOUR AB - Traditional statistical methods for confidentiality protection of statistical databases do not scale well to deal with GWAS databases especially in terms of guarantees regarding protection from linkage to external information. The more recent concept of differential privacy, introduced by the cryptographic community, is an approach which provides a rigorous definition of privacy with meaningful privacy guarantees in the presence of arbitrary external information, although the guarantees may come at a serious price in terms of data utility. Building on such notions, we propose new methods to release aggregate GWAS data without compromising an individual’s privacy. We present methods for releasing differentially private minor allele frequencies, chi-square statistics and p-values. We compare these approaches on simulated data and on a GWAS study of canine hair length involving 685 dogs. We also propose a privacy-preserving method for finding genome-wide associations based on a differentially-private approach to penalized logistic regression. AU - Uhler, Caroline AU - Slavkovic, Aleksandra AU - Fienberg, Stephen ID - 2009 IS - 1 JF - Journal of Privacy and Confidentiality TI - Privacy-preserving data sharing for genome-wide association studies VL - 5 ER - TY - JOUR AB - Sex chromosomes originate from autosomes. The accumulation of sexually antagonistic mutations on protosex chromosomes selects for a loss of recombination and sets in motion the evolutionary processes generating heteromorphic sex chromosomes. Recombination suppression and differentiation are generally viewed as the default path of sex chromosome evolution, and the occurrence of old, homomorphic sex chromosomes, such as those of ratite birds, has remained a mystery. Here, we analyze the genome and transcriptome of emu (Dromaius novaehollandiae) and confirm that most genes on the sex chromosome are shared between the Z and W. Surprisingly, however, levels of gene expression are generally sex-biased for all sex-linked genes relative to autosomes, including those in the pseudoautosomal region, and the male-bias increases after gonad formation. This expression bias suggests that the emu sex chromosomes have become masculinized, even in the absence of ZW differentiation. Thus, birds may have taken different evolutionary solutions to minimize the deleterious effects imposed by sexually antagonistic mutations: some lineages eliminate recombination along the protosex chromosomes to physically restrict sexually antagonistic alleles to one sex, whereas ratites evolved sex-biased expression to confine the product of a sexually antagonistic allele to the sex it benefits. This difference in conflict resolution may explain the preservation of recombining, homomorphic sex chromosomes in other lineages and illustrates the importance of sexually antagonistic mutations driving the evolution of sex chromosomes. AU - Beatriz Vicoso AU - Kaiser, Vera B AU - Bachtrog, Doris ID - 2074 IS - 16 JF - PNAS TI - Sex biased gene expression at homomorphic sex chromosomes in emus and its implication for sex chromosome evolution VL - 110 ER - TY - JOUR AB - Snakes exhibit genetic sex determination, with female heterogametic sex chromosomes (ZZ males, ZW females). Extensive cytogenetic work has suggested that the level of sex chromosome heteromorphism varies among species, with Boidae having entirely homomorphic sex chromosomes, Viperidae having completely heteromorphic sex chromosomes, and Colubridae showing partial differentiation. Here, we take a genomic approach to compare sex chromosome differentiation in these three snake families. We identify homomorphic sex chromosomes in boas (Boidae), but completely heteromorphic sex chromosomes in both garter snakes (Colubridae) and pygmy rattlesnake (Viperidae). Detection of W-linked gametologs enables us to establish the presence of evolutionary strata on garter and pygmy rattlesnake sex chromosomes where recombination was abolished at different time points. Sequence analysis shows that all strata are shared between pygmy rattlesnake and garter snake, i.e., recombination was abolished between the sex chromosomes before the two lineages diverged. The sex-biased transmission of the Z and its hemizygosity in females can impact patterns of molecular evolution, and we show that rates of evolution for Z-linked genes are increased relative to their pseudoautosomal homologs, both at synonymous and amino acid sites (even after controlling for mutational biases). This demonstrates that mutation rates are male-biased in snakes (male-driven evolution), but also supports faster-Z evolution due to differential selective effects on the Z. Finally, we perform a transcriptome analysis in boa and pygmy rattlesnake to establish baseline levels of sex-biased expression in homomorphic sex chromosomes, and show that heteromorphic ZW chromosomes in rattlesnakes lack chromosome-wide dosage compensation. Our study provides the first full scale overview of the evolution of snake sex chromosomes at the genomic level, thus greatly expanding our knowledge of reptilian and vertebrate sex chromosomes evolution. AU - Beatriz Vicoso AU - Emerson, Jr J. AU - Zektser, Yulia AU - Mahajan, Shivani AU - Bachtrog, Doris ID - 2076 IS - 8 JF - PLoS Biology TI - Comparative sex chromosome genomics in snakes: Differentiation evolutionary strata and lack of global dosage compensation VL - 11 ER - TY - JOUR AB - We present an interactive design system that allows non-expert users to create animated mechanical characters. Given an articulated character as input, the user iteratively creates an animation by sketching motion curves indicating how different parts of the character should move. For each motion curve, our framework creates an optimized mechanism that reproduces it as closely as possible. The resulting mechanisms are attached to the character and then connected to each other using gear trains, which are created in a semi-automated fashion. The mechanical assemblies generated with our system can be driven with a single input driver, such as a hand-operated crank or an electric motor, and they can be fabricated using rapid prototyping devices. We demonstrate the versatility of our approach by designing a wide range of mechanical characters, several of which we manufactured using 3D printing. While our pipeline is designed for characters driven by planar mechanisms, significant parts of it extend directly to non-planar mechanisms, allowing us to create characters with compelling 3D motions. AU - Coros, Stelian AU - Thomaszewski, Bernhard AU - Noris, Gioacchino AU - Sueda, Shinjiro AU - Forberg, Moira AU - Sumner, Robert W AU - Matusik, Wojciech AU - Bernd Bickel ID - 2108 IS - 4 JF - ACM Transactions on Graphics TI - Computational design of mechanical characters VL - 32 ER - TY - JOUR AB - We present a method for practical physical reproduction and design of homogeneous materials with desired subsurface scattering. Our process uses a collection of different pigments that can be suspended in a clear base material. Our goal is to determine pigment concentrations that best reproduce the appearance and subsurface scattering of a given target material. In order to achieve this task we first fabricate a collection of material samples composed of known mixtures of the available pigments with the base material. We then acquire their reflectance profiles using a custom-built measurement device. We use the same device to measure the reflectance profile of a target material. Based on the database of mappings from pigment concentrations to reflectance profiles, we use an optimization process to compute the concentration of pigments to best replicate the target material appearance. We demonstrate the practicality of our method by reproducing a variety of different translucent materials. We also present a tool that allows the user to explore the range of achievable appearances for a given set of pigments. AU - Papas, Marios AU - Regg, Christian AU - Jarosz, Wojciech AU - Bernd Bickel AU - Jackson, Philip V AU - Matusik, Wojciech AU - Marschner, Steve AU - Groß, Markus S ID - 2110 IS - 4 JF - ACM Transactions on Graphics TI - Fabricating translucent materials using continuous pigment mixtures VL - 32 ER - TY - JOUR AB - Animated animatronic figures are a unique way to give physical presence to a character. However, their movement and expressions are often limited due to mechanical constraints. In this paper, we propose a complete process for augmenting physical avatars using projector-based illumination, significantly increasing their expressiveness. Given an input animation, the system decomposes the motion into low-frequency motion that can be physically reproduced by the animatronic head and high-frequency details that are added using projected shading. At the core is a spatio-temporal optimization process that compresses the motion in gradient space, ensuring faithful motion replay while respecting the physical limitations of the system. We also propose a complete multi-camera and projection system, including a novel defocused projection and subsurface scattering compensation scheme. The result of our system is a highly expressive physical avatar that features facial details and motion otherwise unattainable due to physical constraints. AU - Bermano, Amit H AU - Bruschweiler, Philipp AU - Grundhöfer, Anselm AU - Iwai, Daisuke AU - Bernd Bickel AU - Groß, Markus S ID - 2111 IS - 6 JF - ACM Transactions on Graphics TI - Augmenting physical avatars using projector-based illumination VL - 32 ER - TY - JOUR AB - Most additive manufacturing technologies work by layering, i.e. slicing the shape and then generating each slice independently. This introduces an anisotropy into the process, often as different accuracies in the tangential and normal directions, but also in terms of other parameters such as build speed or tensile strength and strain. We model this as an anisotropic cubic element. Our approach then finds a compromise between modeling each part of the shape individually in the best possible direction and using one direction for the whole shape part. In particular, we compute an orthogonal basis and consider only the three basis vectors as slice normals (i.e. fabrication directions). Then we optimize a decomposition of the shape along this basis so that each part can be consistently sliced along one of the basis vectors. In simulation, we show that this approach is superior to slicing the whole shape in one direction, only. It also has clear benefits if the shape is larger than the build volume of the available equipment. AU - Hildebrand, Kristian AU - Bernd Bickel AU - Alexa, Marc ID - 2109 IS - 6 JF - Computers and Graphics (Pergamon) TI - Orthogonal slicing for additive manufacturing VL - 37 ER - TY - JOUR AB - We present a method for fabrication-oriented design of actuated deformable characters that allows a user to automatically create physical replicas of digitally designed characters using rapid manufacturing technologies. Given a deformable character and a set of target poses as input, our method computes a small set of actuators along with their locations on the surface and optimizes the internal material distribution such that the resulting character exhibits the desired deformation behavior. We approach this problem with a dedicated algorithm that combines finite-element analysis, sparse regularization, and constrained optimization. We validate our pipeline on a set of two- and three-dimensional example characters and present results in simulation and physically-fabricated prototypes. AU - Skouras, Mélina AU - Thomaszewski, Bernhard AU - Coros, Stelian AU - Bernd Bickel AU - Groß, Markus S ID - 2107 IS - 4 JF - ACM Transactions on Graphics TI - Computational design of actuated deformable characters VL - 32 ER - TY - JOUR AB - Force-deformation measurements of cloth exhibit significant hysteresis, and many researchers have identified internal friction as the source of this effect. However, it has not been incorporated into computer animation models of cloth. In this paper, we propose a model of internal friction based on an augmented reparameterization of Dahl's model, and we show that this model provides a good match to several important features of cloth hysteresis even with a minimal set of parameters. We also propose novel parameter estimation procedures that are based on simple and inexpensive setups and need only sparse data, as opposed to the complex hardware and dense data acquisition of previous methods. Finally, we provide an algorithm for the efficient simulation of internal friction, and we demonstrate it on simulation examples that show disparate behavior with and without internal friction. AU - Miguel, Eder AU - Tamstorf, Rasmus AU - Bradley, Derek J AU - Schvartzman, Sara C AU - Thomaszewski, Bernhard AU - Bernd Bickel AU - Matusik, Wojciech AU - Marschner, Steve AU - Otaduy, Miguel A ID - 2112 IS - 6 JF - ACM Transactions on Graphics TI - Modeling and estimation of internal friction in cloth VL - 32 ER - TY - JOUR AB - We prove new upper and lower bounds for Banach space-valued stochastic integrals with respect to a compensated Poisson random measure. Our estimates apply to Banach spaces with non-trivial martingale (co)type and extend various results in the literature. We also develop a Malliavin framework to interpret Poisson stochastic integrals as vector-valued Skorohod integrals, and prove a Clark-Ocone representation formula. AU - Dirksen, Sjoerd AU - Jan Maas AU - van Neerven, Jan M ID - 2117 JF - Electronic Journal of Probability TI - Poisson stochastic integration in Banach spaces VL - 18 ER - TY - JOUR AB - A new method fabricates custom surface reflectance and spatially varying bidirectional reflectance distribution functions (svBRDFs). Researchers optimize a microgeometry for a range of normal distribution functions and simulate the resulting surface's effective reflectance. Using the simulation's results, they reproduce an input svBRDF's appearance by distributing the microgeometry on the printed material's surface. This method lets people print svBRDFs on planar samples with current 3D printing technology, even with a limited set of printing materials. It extends naturally to printing svBRDFs on arbitrary shapes. AU - Rouiller, Olivier AU - Bernd Bickel AU - Kautz, Jan AU - Matusik, Wojciech AU - Alexa, Marc ID - 2113 IS - 6 JF - IEEE Computer Graphics and Applications TI - 3D printing spatially varying BRDFs VL - 33 ER - TY - JOUR AB - 3D printing is considered a disruptive technology with a potentially tremendous socioeconomic impact. The three articles in this special issue illustrate how novel computer graphics approaches are advancing such digital fabrication. AU - Bernd Bickel AU - Alexa, Marc ID - 2114 IS - 6 JF - IEEE Computer Graphics and Applications TI - Computational aspects of fabrication: Modeling, design and 3d printing VL - 33 ER - TY - JOUR AB - This paper continues the investigation of `Wasserstein-like' transportation distances for probability measures on discrete sets. We prove that the discrete transportation metrics on the d-dimensional discrete torus with mesh size 1/N converge, when N→∞, to the standard 2-Wasserstein distance W_2 on the continuous torus in the sense of Gromov-Hausdorff. This is the first convergence result for the recently developed discrete transportation metrics. The result shows the compatibility between these metrics and the well-established 2-Wasserstein metric. AU - Gigli, Nicola AU - Jan Maas ID - 2129 IS - 2 JF - SIAM Journal on Mathematical Analysis TI - Gromov-Hausdorff convergence of discrete transportation metrics VL - 45 ER - TY - JOUR AB - Recently it has been shown that pairs of atoms can form metastable bonds due to non-conservative forces induced by dissipation [Lemeshko&Weimer, Nature Comm. 4, 2230 (2013)]. Here we study the dynamics of interaction-induced coherent population trapping - the process responsible for the formation of dissipatively bound molecules. We derive the effective dissipative potentials induced between ultracold atoms by laser light, and study the time evolution of the scattering states. We demonstrate that binding occurs on short timescales of ~10 microseconds, even if the initial kinetic energy of the atoms significantly exceeds the depth of the dissipative potential. Dissipatively-bound molecules with preordained bond lengths and vibrational wavefunctions can be created and detected in current experiments with ultracold atoms. AU - Mikhail Lemeshko ID - 2139 IS - 17 JF - Frontiers Physics TI - Manipulating scattering of ultracold atoms with light-induced dissipation VL - 1 ER - TY - CONF AB - There is a trade-off between performance and correctness in implementing concurrent data structures. Better performance may be achieved at the expense of relaxing correctness, by redefining the semantics of data structures. We address such a redefinition of data structure semantics and present a systematic and formal framework for obtaining new data structures by quantitatively relaxing existing ones. We view a data structure as a sequential specification S containing all "legal" sequences over an alphabet of method calls. Relaxing the data structure corresponds to defining a distance from any sequence over the alphabet to the sequential specification: the k-relaxed sequential specification contains all sequences over the alphabet within distance k from the original specification. In contrast to other existing work, our relaxations are semantic (distance in terms of data structure states). As an instantiation of our framework, we present two simple yet generic relaxation schemes, called out-of-order and stuttering relaxation, along with several ways of computing distances. We show that the out-of-order relaxation, when further instantiated to stacks, queues, and priority queues, amounts to tolerating bounded out-of-order behavior, which cannot be captured by a purely syntactic relaxation (distance in terms of sequence manipulation, e.g. edit distance). We give concurrent implementations of relaxed data structures and demonstrate that bounded relaxations provide the means for trading correctness for performance in a controlled way. The relaxations are monotonic which further highlights the trade-off: increasing k increases the number of permitted sequences, which as we demonstrate can lead to better performance. Finally, since a relaxed stack or queue also implements a pool, we actually have new concurrent pool implementations that outperform the state-of-the-art ones. AU - Henzinger, Thomas A AU - Kirsch, Christoph AU - Payer, Hannes AU - Sezgin, Ali AU - Sokolova, Ana ID - 2181 SN - 978-1-4503-1832-7 T2 - Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming language TI - Quantitative relaxation of concurrent data structures ER - TY - CONF AB - We propose a general framework for abstraction with respect to quantitative properties, such as worst-case execution time, or power consumption. Our framework provides a systematic way for counter-example guided abstraction refinement for quantitative properties. The salient aspect of the framework is that it allows anytime verification, that is, verification algorithms that can be stopped at any time (for example, due to exhaustion of memory), and report approximations that improve monotonically when the algorithms are given more time. We instantiate the framework with a number of quantitative abstractions and refinement schemes, which differ in terms of how much quantitative information they keep from the original system. We introduce both state-based and trace-based quantitative abstractions, and we describe conditions that define classes of quantitative properties for which the abstractions provide over-approximations. We give algorithms for evaluating the quantitative properties on the abstract systems. We present algorithms for counter-example based refinements for quantitative properties for both state-based and segment-based abstractions. We perform a case study on worst-case execution time of executables to evaluate the anytime verification aspect and the quantitative abstractions we proposed. AU - Cerny, Pavol AU - Henzinger, Thomas A AU - Radhakrishna, Arjun ID - 2182 T2 - Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming language TI - Quantitative abstraction refinement ER - TY - CONF AB - A straight skeleton is a well-known geometric structure, and several algorithms exist to construct the straight skeleton for a given polygon or planar straight-line graph. In this paper, we ask the reverse question: Given the straight skeleton (in form of a planar straight-line graph, with some rays to infinity), can we reconstruct a planar straight-line graph for which this was the straight skeleton? We show how to reduce this problem to the problem of finding a line that intersects a set of convex polygons. We can find these convex polygons and all such lines in $O(nlog n)$ time in the Real RAM computer model, where $n$ denotes the number of edges of the input graph. We also explain how our approach can be used for recognizing Voronoi diagrams of points, thereby completing a partial solution provided by Ash and Bolker in 1985. AU - Biedl, Therese AU - Held, Martin AU - Huber, Stefan ID - 2209 TI - Recognizing straight skeletons and Voronoi diagrams and reconstructing their input ER - TY - JOUR AB - We introduce a new platform for quantum simulation of many-body systems based on nonspherical atoms or molecules with zero dipole moments but possessing a significant value of electric quadrupole moments. We consider a quadrupolar Fermi gas trapped in a 2D square optical lattice, and show that the peculiar symmetry and broad tunability of the quadrupole-quadrupole interaction results in a rich phase diagram encompassing unconventional BCS and charge density wave phases, and opens up a perspective to create a topological superfluid. Quadrupolar species, such as metastable alkaline-earth atoms and homonuclear molecules, are stable against chemical reactions and collapse and are readily available in experiment at high densities. AU - Bhongale, Satyan AU - Mathey, Ludwig AU - Zhao, Erhai AU - Yelin, Susanne AU - Lemeshko, Mikhail ID - 2204 IS - 15 JF - Physical Review Letters TI - Quantum phases of quadrupolar fermi gases in optical lattices VL - 110 ER - TY - JOUR AB - Magnetic impurities embedded in inert solids can exhibit long coherence times and interact with one another via their intrinsic anisotropic dipolar interaction. We argue that, as a consequence of these properties, disordered ensembles of magnetic impurities provide an effective platform for realizing a controllable, tunable version of the dipolar quantum spin glass seen in LiHoxY1-xF4. Specifically, we propose and analyze a system composed of dysprosium atoms embedded in solid helium. We describe the phase diagram of the system and discuss the realizability and detectability of the quantum spin glass and antiglass phases. AU - Mikhail Lemeshko AU - Yao, Norman Y AU - Gorshkov, Alexey V AU - Weimer, Hendrik AU - Bennett, Steven D AU - Momose, Takamasa AU - Gopalakrishnan, Sarang ID - 2206 IS - 1 JF - Physical Review B - Condensed Matter and Materials Physics TI - Controllable quantum spin glasses with magnetic impurities embedded in quantum solids VL - 88 ER - TY - GEN AB - The goal of the present article is to review the major developments that have led to the current understanding of molecule-field interactions and experimental methods for manipulating molecules with electromagnetic fields. Molecule-field interactions are at the core of several, seemingly distinct areas of molecular physics. This is reflected in the organisation of this article, which includes sections on field control of molecular beams, external field traps for cold molecules, control of molecular orientation and molecular alignment, manipulation of molecules by non-conservative forces, ultracold molecules and ultracold chemistry, controlled many-body phenomena, entanglement of molecules and dipole arrays, and stability of molecular systems in high-frequency super-intense laser fields. The article contains 852 references. AU - Mikhail Lemeshko AU - Krems, Roman V AU - Doyle, John M AU - Kais, Sabre ID - 2205 IS - 12-13 T2 - Molecular Physics TI - Manipulation of molecules with electromagnetic fields VL - 111 ER - TY - JOUR AB - The formation of molecules and supramolecular structures results from bonding by conservative forces acting among electrons and nuclei and giving rise to equilibrium configurations defined by minima of the interaction potential. Here we show that bonding can also occur by the non-conservative forces responsible for interaction-induced coherent population trapping. The bound state arises in a dissipative process and manifests itself as a stationary state at a preordained interatomic distance. Remarkably, such a dissipative bonding is present even when the interactions among the atoms are purely repulsive. The dissipative bound states can be created and studied spectroscopically in present-day experiments with ultracold atoms or molecules and can potentially serve for cooling strongly interacting quantum gases. AU - Mikhail Lemeshko AU - Weimer, Hendrik ID - 2207 JF - Nature Communications TI - Dissipative binding of atoms by non-conservative forces VL - 4 ER - TY - CONF AB - A straight skeleton is a well-known geometric structure, and several algorithms exist to construct the straight skeleton for a given polygon. In this paper, we ask the reverse question: Given the straight skeleton (in form of a tree with a drawing in the plane, but with the exact position of the leaves unspecified), can we reconstruct the polygon? We show that in most cases there exists at most one polygon; in the remaining case there is an infinite number of polygons determined by one angle that can range in an interval. We can find this (set of) polygon(s) in linear time in the Real RAM computer model. AU - Biedl, Therese AU - Held, Martin AU - Huber, Stefan ID - 2210 T2 - 29th European Workshop on Computational Geometry TI - Reconstructing polygons from embedded straight skeletons ER - TY - CONF AB - We describe new extensions of the Vampire theorem prover for computing tree interpolants. These extensions generalize Craig interpolation in Vampire, and can also be used to derive sequence interpolants. We evaluated our implementation on a large number of examples over the theory of linear integer arithmetic and integer-indexed arrays, with and without quantifiers. When compared to other methods, our experiments show that some examples could only be solved by our implementation. AU - Blanc, Régis AU - Gupta, Ashutosh AU - Kovács, Laura AU - Kragl, Bernhard ID - 2237 TI - Tree interpolation in Vampire VL - 8312 ER - TY - CONF AB - We study the problem of achieving a given value in Markov decision processes (MDPs) with several independent discounted reward objectives. We consider a generalised version of discounted reward objectives, in which the amount of discounting depends on the states visited and on the objective. This definition extends the usual definition of discounted reward, and allows to capture the systems in which the value of different commodities diminish at different and variable rates. We establish results for two prominent subclasses of the problem, namely state-discount models where the discount factors are only dependent on the state of the MDP (and independent of the objective), and reward-discount models where they are only dependent on the objective (but not on the state of the MDP). For the state-discount models we use a straightforward reduction to expected total reward and show that the problem whether a value is achievable can be solved in polynomial time. For the reward-discount model we show that memory and randomisation of the strategies are required, but nevertheless that the problem is decidable and it is sufficient to consider strategies which after a certain number of steps behave in a memoryless way. For the general case, we show that when restricted to graphs (i.e. MDPs with no randomisation), pure strategies and discount factors of the form 1/n where n is an integer, the problem is in PSPACE and finite memory suffices for achieving a given value. We also show that when the discount factors are not of the form 1/n, the memory required by a strategy can be infinite. AU - Chatterjee, Krishnendu AU - Forejt, Vojtěch AU - Wojtczak, Dominik ID - 2238 TI - Multi-objective discounted reward verification in graphs and MDPs VL - 8312 ER - TY - CONF AB - We show that modal logic over universally first-order definable classes of transitive frames is decidable. More precisely, let K be an arbitrary class of transitive Kripke frames definable by a universal first-order sentence. We show that the global and finite global satisfiability problems of modal logic over K are decidable in NP, regardless of choice of K. We also show that the local satisfiability and the finite local satisfiability problems of modal logic over K are decidable in NEXPTIME. AU - Michaliszyn, Jakub AU - Otop, Jan ID - 2243 TI - Elementary modal logics over transitive structures VL - 23 ER - TY - CONF AB - We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a compact two-dimensional surface ℳ with boundary. Each αi and each βj is either an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. AU - Matoušek, Jiří AU - Sedgwick, Eric AU - Tancer, Martin AU - Wagner, Uli ID - 2244 TI - Untangling two systems of noncrossing curves VL - 8242 ER - TY - CONF AB - The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors. As a tool in the reduction, we show that there is a “lossy mode” for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple constructions of deterministic encryption, lossy trapdoor functions and reusable extractors. Our approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly showed the existence of a “lossy mode” for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio. AU - Alwen, Joel F AU - Krenn, Stephan AU - Pietrzak, Krzysztof Z AU - Wichs, Daniel ID - 2259 IS - 1 TI - Learning with rounding, revisited: New reduction properties and applications VL - 8042 ER - TY - CONF AB - In a digital signature scheme with message recovery, rather than transmitting the message m and its signature σ, a single enhanced signature τ is transmitted. The verifier is able to recover m from τ and at the same time verify its authenticity. The two most important parameters of such a scheme are its security and overhead |τ| − |m|. A simple argument shows that for any scheme with “n bits security” |τ| − |m| ≥ n, i.e., the overhead is lower bounded by the security parameter n. Currently, the best known constructions in the random oracle model are far from this lower bound requiring an overhead of n + logq h , where q h is the number of queries to the random oracle. In this paper we give a construction which basically matches the n bit lower bound. We propose a simple digital signature scheme with n + o(logq h ) bits overhead, where q h denotes the number of random oracle queries. Our construction works in two steps. First, we propose a signature scheme with message recovery having optimal overhead in a new ideal model, the random invertible function model. Second, we show that a four-round Feistel network with random oracles as round functions is tightly “public-indifferentiable” from a random invertible function. At the core of our indifferentiability proof is an almost tight upper bound for the expected number of edges of the densest “small” subgraph of a random Cayley graph, which may be of independent interest. AU - Kiltz, Eike AU - Pietrzak, Krzysztof Z AU - Szegedy, Mario ID - 2258 TI - Digital signatures with minimal overhead from indifferentiable random invertible functions VL - 8042 ER - TY - JOUR AB - Linked (Open) Data - bibliographic data on the Semantic Web. Report of the Working Group on Linked Data to the plenary assembly of the Austrian Library Network (translation of the title). Linked Data stands for a certain approach to publishing data on the Web. The underlying idea is to harmonise heterogeneous data sources of different origin in order to improve their accessibility and interoperability, effectively making them queryable as a big distributed database. This report summarises relevant developments in Europe as well as the Linked Data Working Group‘s strategic and technical considerations regarding the publishing of the Austrian Library Network’s (OBV’s) bibliographic datasets. It concludes with the mutual agreement that the implementation of Linked Data principles within the OBV can only be taken into consideration accompanied by a discussion about the provision of the datasets under a free license. AU - Danowski, Patrick AU - Goldfarb, Doron AU - Schaffner, Verena AU - Seidler, Wolfram ID - 2256 IS - 3/4 JF - VÖB Mitteilungen TI - Linked (Open) Data - Bibliographische Daten im Semantic Web VL - 66 ER - TY - CONF AB - Direct Anonymous Attestation (DAA) is one of the most complex cryptographic protocols deployed in practice. It allows an embedded secure processor known as a Trusted Platform Module (TPM) to attest to the configuration of its host computer without violating the owner’s privacy. DAA has been standardized by the Trusted Computing Group and ISO/IEC. The security of the DAA standard and all existing schemes is analyzed in the random-oracle model. We provide the first constructions of DAA in the standard model, that is, without relying on random oracles. Our constructions use new building blocks, including the first efficient signatures of knowledge in the standard model, which have many applications beyond DAA. AU - Bernhard, David AU - Fuchsbauer, Georg AU - Ghadafi, Essam ID - 2260 TI - Efficient signatures of knowledge and DAA in the standard model VL - 7954 ER - TY - JOUR AB - Faithful progression through the cell cycle is crucial to the maintenance and developmental potential of stem cells. Here, we demonstrate that neural stem cells (NSCs) and intermediate neural progenitor cells (NPCs) employ a zinc-finger transcription factor specificity protein 2 (Sp2) as a cell cycle regulator in two temporally and spatially distinct progenitor domains. Differential conditional deletion of Sp2 in early embryonic cerebral cortical progenitors, and perinatal olfactory bulb progenitors disrupted transitions through G1, G2 and M phases, whereas DNA synthesis appeared intact. Cell-autonomous function of Sp2 was identified by deletion of Sp2 using mosaic analysis with double markers, which clearly established that conditional Sp2-null NSCs and NPCs are M phase arrested in vivo. Importantly, conditional deletion of Sp2 led to a decline in the generation of NPCs and neurons in the developing and postnatal brains. Our findings implicate Sp2-dependent mechanisms as novel regulators of cell cycle progression, the absence of which disrupts neurogenesis in the embryonic and postnatal brain. AU - Liang, Huixuan AU - Xiao, Guanxi AU - Yin, Haifeng AU - Hippenmeyer, Simon AU - Horowitz, Jonathan AU - Ghashghaei, Troy ID - 2264 IS - 3 JF - Development TI - Neural development is dependent on the function of specificity protein 2 in cell cycle progression VL - 140 ER - TY - JOUR AB - This paper presents a parallel, implementation-friendly analytic visibility method for triangular meshes. Together with an analytic filter convolution, it allows for a fully analytic solution to anti-aliased 3D mesh rendering on parallel hardware. Building on recent works in computational geometry, we present a new edge-triangle intersection algorithm and a novel method to complete the boundaries of all visible triangle regions after a hidden line elimination step. All stages of the method are embarrassingly parallel and easily implementable on parallel hardware. A GPU implementation is discussed and performance characteristics of the method are shown and compared to traditional sampling-based rendering methods. AU - Thomas Auzinger AU - Wimmer, Michael AU - Stefan Jeschke ID - 2269 IS - 124 JF - Computer Graphics Forum TI - Analytic Visibility on the GPU VL - 32 ER - TY - CONF AB - Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher- ent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive Weighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs. AU - Bachrach, Yoram AU - Kohli, Pushmeet AU - Kolmogorov, Vladimir AU - Zadimoghaddam, Morteza ID - 2270 TI - Optimal Coalition Structures in Cooperative Graph Games ER - TY - GEN AB - We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results. AU - Vladimir Kolmogorov ID - 2273 TI - Reweighted message passing revisited ER - TY - JOUR AB - It is firmly established that interactions between neurons and glia are fundamental across species for the correct establishment of a functional brain. Here, we found that the glia of the Drosophila larval brain display an essential non-autonomous role during the development of the optic lobe. The optic lobe develops from neuroepithelial cells that proliferate by dividing symmetrically until they switch to asymmetric/differentiative divisions that generate neuroblasts. The proneural gene lethal of scute (l9sc) is transiently activated by the epidermal growth factor receptor (EGFR)-Ras signal transduction pathway at the leading edge of a proneural wave that sweeps from medial to lateral neuroepithelium, promoting this switch. This process is tightly regulated by the tissue-autonomous function within the neuroepithelium of multiple signaling pathways, including EGFR-Ras and Notch. This study shows that the Notch ligand Serrate (Ser) is expressed in the glia and it forms a complex in vivo with Notch and Canoe, which colocalize at the adherens junctions of neuroepithelial cells. This complex is crucial for interactions between glia and neuroepithelial cells during optic lobe development. Ser is tissue-autonomously required in the glia where it activates Notch to regulate its proliferation, and non-autonomously in the neuroepithelium where Ser induces Notch signaling to avoid the premature activation of the EGFR-Ras pathway and hence of L9sc. Interestingly, different Notch activity reporters showed very different expression patterns in the glia and in the neuroepithelium, suggesting the existence of tissue-specific factors that promote the expression of particular Notch target genes or/and a reporter response dependent on different thresholds of Notch signaling. AU - Pérez Gómez, Raquel AU - Slovakova, Jana AU - Rives Quinto, Noemí AU - Krejčí, Alena AU - Carmena, Ana ID - 2278 IS - 21 JF - Journal of Cell Science TI - A serrate-notch-canoe complex mediates essential interactions between glia and neuroepithelial cells during Drosophila optic lobe development VL - 126 ER - TY - CONF AB - The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions. AU - Gridchyn, Igor AU - Kolmogorov, Vladimir ID - 2276 TI - Potts model, parametric maxflow and k-submodular functions ER - TY - JOUR AB - The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application-chromosome organization in the human cell nucleus-is discussed briefly, and some illustrative results are presented. AU - Uhler, Caroline AU - Wright, Stephen ID - 2280 IS - 4 JF - SIAM Review TI - Packing ellipsoids with overlap VL - 55 ER - TY - JOUR AB - Negative frequency-dependent selection should result in equal sex ratios in large populations of dioecious flowering plants, but deviations from equality are commonly reported. A variety of ecological and genetic factors can explain biased sex ratios, although the mechanisms involved are not well understood. Most dioecious species are long-lived and/or clonal complicating efforts to identify stages during the life cycle when biases develop. We investigated the demographic correlates of sex-ratio variation in two chromosome races of Rumex hastatulus, an annual, wind-pollinated colonizer of open habitats from the southern USA. We examined sex ratios in 46 populations and evaluated the hypothesis that the proximity of males in the local mating environment, through its influence on gametophytic selection, is the primary cause of female-biased sex ratios. Female-biased sex ratios characterized most populations of R. hastatulus (mean sex ratio = 0.62), with significant female bias in 89% of populations. Large, high-density populations had the highest proportion of females, whereas smaller, low-density populations had sex ratios closer to equality. Progeny sex ratios were more female biased when males were in closer proximity to females, a result consistent with the gametophytic selection hypothesis. Our results suggest that interactions between demographic and genetic factors are probably the main cause of female-biased sex ratios in R. hastatulus. The annual life cycle of this species may limit the scope for selection against males and may account for the weaker degree of bias in comparison with perennial Rumex species. AU - Pickup, Melinda AU - Barrett, Spencer ID - 2287 IS - 3 JF - Ecology and Evolution TI - The influence of demography and local mating environment on sex ratios in a wind-pollinated dioecious plant VL - 3 ER - TY - JOUR AB - Epithelial spreading is a common and fundamental aspect of various developmental and disease-related processes such as epithelial closure and wound healing. A key challenge for epithelial tissues undergoing spreading is to increase their surface area without disrupting epithelial integrity. Here we show that orienting cell divisions by tension constitutes an efficient mechanism by which the enveloping cell layer (EVL) releases anisotropic tension while undergoing spreading during zebrafish epiboly. The control of EVL cell-division orientation by tension involves cell elongation and requires myosin II activity to align the mitotic spindle with the main tension axis. We also found that in the absence of tension-oriented cell divisions and in the presence of increased tissue tension, EVL cells undergo ectopic fusions, suggesting that the reduction of tension anisotropy by oriented cell divisions is required to prevent EVL cells from fusing. We conclude that cell-division orientation by tension constitutes a key mechanism for limiting tension anisotropy and thus promoting tissue spreading during EVL epiboly. AU - Campinho, Pedro AU - Behrndt, Martin AU - Ranft, Jonas AU - Risler, Thomas AU - Minc, Nicolas AU - Heisenberg, Carl-Philipp J ID - 2282 JF - Nature Cell Biology TI - Tension-oriented cell divisions limit anisotropic tissue tension in epithelial spreading during zebrafish epiboly VL - 15 ER - TY - JOUR AB - Pathogens exert a strong selection pressure on organisms to evolve effective immune defences. In addition to individual immunity, social organisms can act cooperatively to produce collective defences. In many ant species, queens have the option to found a colony alone or in groups with other, often unrelated, conspecifics. These associations are transient, usually lasting only as long as each queen benefits from the presence of others. In fact, once the first workers emerge, queens fight to the death for dominance. One potential advantage of co-founding may be that queens benefit from collective disease defences, such as mutual grooming, that act against common soil pathogens. We test this hypothesis by exposing single and co-founding queens to a fungal parasite, in order to assess whether queens in co-founding associations have improved survival. Surprisingly, co-foundresses exposed to the entomopathogenic fungus Metarhizium did not engage in cooperative disease defences, and consequently, we find no direct benefit of multiple queens on survival. However, an indirect benefit was observed, with parasite-exposed queens producing more brood when they co-founded, than when they were alone. We suggest this is due to a trade-off between reproduction and immunity. Additionally, we report an extraordinary ability of the queens to tolerate an infection for long periods after parasite exposure. Our study suggests that there are no social immunity benefits for co-founding ant queens, but that in parasite-rich environments, the presence of additional queens may nevertheless improve the chances of colony founding success. AU - Pull, Christopher AU - Hughes, William AU - Brown, Markus ID - 2283 IS - 12 JF - Naturwissenschaften TI - Tolerating an infection: an indirect benefit of co-founding queen associations in the ant Lasius niger VL - 100 ER - TY - JOUR AB - The spatiotemporal control of cell divisions is a key factor in epithelial morphogenesis and patterning. Mao et al (2013) now describe how differential rates of proliferation within the Drosophila wing disc epithelium give rise to anisotropic tissue tension in peripheral/proximal regions of the disc. Such global tissue tension anisotropy in turn determines the orientation of cell divisions by controlling epithelial cell elongation. AU - Campinho, Pedro AU - Heisenberg, Carl-Philipp J ID - 2286 IS - 21 JF - EMBO Journal TI - The force and effect of cell proliferation VL - 32 ER - TY - JOUR AB - Formal verification aims to improve the quality of software by detecting errors before they do harm. At the basis of formal verification is the logical notion of correctness, which purports to capture whether or not a program behaves as desired. We suggest that the boolean partition of software into correct and incorrect programs falls short of the practical need to assess the behavior of software in a more nuanced fashion against multiple criteria. We therefore propose to introduce quantitative fitness measures for programs, specifically for measuring the function, performance, and robustness of reactive programs such as concurrent processes. This article describes the goals of the ERC Advanced Investigator Project QUAREM. The project aims to build and evaluate a theory of quantitative fitness measures for reactive models. Such a theory must strive to obtain quantitative generalizations of the paradigms that have been success stories in qualitative reactive modeling, such as compositionality, property-preserving abstraction and abstraction refinement, model checking, and synthesis. The theory will be evaluated not only in the context of software and hardware engineering, but also in the context of systems biology. In particular, we will use the quantitative reactive models and fitness measures developed in this project for testing hypotheses about the mechanisms behind data from biological experiments. AU - Henzinger, Thomas A ID - 2289 IS - 4 JF - Computer Science Research and Development TI - Quantitative reactive modeling and verification VL - 28 ER -