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 -