TY - CONF AB - Transfer learning has received a lot of attention in the machine learning community over the last years, and several effective algorithms have been developed. However, relatively little is known about their theoretical properties, especially in the setting of lifelong learning, where the goal is to transfer information to tasks for which no data have been observed so far. In this work we study lifelong learning from a theoretical perspective. Our main result is a PAC-Bayesian generalization bound that offers a unified view on existing paradigms for transfer learning, such as the transfer of parameters or the transfer of low-dimensional representations. We also use the bound to derive two principled lifelong learning algorithms, and we show that these yield results comparable with existing methods. AU - Pentina, Anastasia AU - Lampert, Christoph ID - 2160 TI - A PAC-Bayesian bound for Lifelong Learning VL - 32 ER - TY - THES AB - A variety of developmental and disease related processes depend on epithelial cell sheet spreading. In order to gain insight into the biophysical mechanism(s) underlying the tissue morphogenesis we studied the spreading of an epithelium during the early development of the zebrafish embryo. In zebrafish epiboly the enveloping cell layer (EVL), a simple squamous epithelium, spreads over the yolk cell to completely engulf it at the end of gastrulation. Previous studies have proposed that an actomyosin ring forming within the yolk syncytial layer (YSL) acts as purse string that through constriction along its circumference pulls on the margin of the EVL. Direct biophysical evidence for this hypothesis has however been missing. The aim of the thesis was to understand how the actomyosin ring may generate pulling forces onto the EVL and what cellular mechanism(s) may facilitate the spreading of the epithelium. Using laser ablation to measure cortical tension within the actomyosin ring we found an anisotropic tension distribution, which was highest along the circumference of the ring. However the low degree of anisotropy was incompatible with the actomyosin ring functioning as a purse string only. Additionally, we observed retrograde cortical flow from vegetal parts of the ring into the EVL margin. Interpreting the experimental data using a theoretical distribution that models the tissues as active viscous gels led us to proposen that the actomyosin ring has a twofold contribution to EVL epiboly. It not only acts as a purse string through constriction along its circumference, but in addition constriction along the width of the ring generates pulling forces through friction-resisted cortical flow. Moreover, when rendering the purse string mechanism unproductive EVL epiboly proceeded normally indicating that the flow-friction mechanism is sufficient to drive the process. Aiming to understand what cellular mechanism(s) may facilitate the spreading of the epithelium we found that tension-oriented EVL cell divisions limit tissue anisotropy by releasing tension along the division axis and promote epithelial spreading. Notably, EVL cells undergo ectopic cell fusion in conditions in which oriented-cell division is impaired or the epithelium is mechanically challenged. Taken together our study of EVL epiboly suggests a novel mechanism of force generation for actomyosin rings through friction-resisted cortical flow and highlights the importance of tension-oriented cell divisions in epithelial morphogenesis. AU - Behrndt, Martin ID - 1403 TI - Forces driving epithelial spreading in zebrafish epiboly ER - TY - CHAP AB - Im Rahmen meiner Arbeit mit der kollektiven Krankheitsabwehr in Ameisengesellschaften interessiert mich vor allem, wie sich die Kolonien als Ganzes gegen Krankheiten wehren können. Warum ist dieses Thema der Krankheitsdynamik in Gruppen so wichtig? Ein Vergleich von solitär lebenden Individuen mit Individuen, die in sozialen Gruppen zusammenleben, zeigt die Kosten und die Vorteile des Gruppenlebens: Einerseits haben Individuen in sozialen Gruppen aufgrund der hohen Dichte, in der die Tiere zusammenleben, den hohen Interaktionsraten, die sie miteinander haben, und der engen Verwandtschaft, die sie verbindet, ein höheres Ansteckungsrisiko. Andererseits kann die individuelle Krankheitsabwehr durch die kollektive Abwehr in den Gruppen ergänzt werden. AU - Cremer, Sylvia ID - 1888 SN - 2366-2875 T2 - Soziale Insekten in einer sich wandelnden Welt TI - Soziale Immunität: Wie sich der Staat gegen Pathogene wehrt Bayerische Akademie der Wissenschaften VL - 43 ER - TY - GEN AB - The classical sphere packing problem asks for the best (infinite) arrangement of non-overlapping unit balls which cover as much space as possible. We define a generalized version of the problem, where we allow each ball a limited amount of overlap with other balls. We study two natural choices of overlap measures and obtain the optimal lattice packings in a parameterized family of lattices which contains the FCC, BCC, and integer lattice. AU - Iglesias Ham, Mabel AU - Kerber, Michael AU - Uhler, Caroline ID - 2012 T2 - arXiv TI - Sphere packing with limited overlap ER - TY - JOUR AB - DNA has become a prime material for assembling complex three-dimensional objects that promise utility in various areas of application. However, achieving user-defined goals with DNA objects has been hampered by the difficulty to prepare them at arbitrary concentrations and in user-defined solution conditions. Here, we describe a method that solves this problem. The method is based on poly(ethylene glycol)-induced depletion of species with high molecular weight. We demonstrate that our method is applicable to a wide spectrum of DNA shapes and that it achieves excellent recovery yields of target objects up to 97 %, while providing efficient separation from non-integrated DNA strands. DNA objects may be prepared at concentrations up to the limit of solubility, including the possibility for bringing DNA objects into a solid phase. Due to the fidelity and simplicity of our method we anticipate that it will help to catalyze the development of new types of applications that use self-assembled DNA objects. AU - Stahl, Evi AU - Martin, Thomas AU - Praetorius, Florian M AU - Dietz, Hendrik ID - 14301 IS - 47 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Facile and scalable preparation of pure and dense DNA origami solutions VL - 126 ER - TY - JOUR AU - Sweeney, Lora Beatrice Jaeger AU - Kelley, Darcy B ID - 7699 IS - 10 JF - Current Opinion in Neurobiology SN - 0959-4388 TI - Harnessing vocal patterns for social communication VL - 28 ER - TY - JOUR AB - We consider two-dimensional Bose-Einstein condensates with attractive interaction, described by the Gross-Pitaevskii functional. Minimizers of this functional exist only if the interaction strength a satisfies {Mathematical expression}, where Q is the unique positive radial solution of {Mathematical expression} in {Mathematical expression}. We present a detailed analysis of the behavior of minimizers as a approaches a*, where all the mass concentrates at a global minimum of the trapping potential. AU - Guo, Yujin AU - Seiringer, Robert ID - 2281 IS - 2 JF - Letters in Mathematical Physics TI - On the mass concentration for Bose-Einstein condensates with attractive interactions VL - 104 ER - TY - JOUR AB - Maximum entropy models are the least structured probability distributions that exactly reproduce a chosen set of statistics measured in an interacting network. Here we use this principle to construct probabilistic models which describe the correlated spiking activity of populations of up to 120 neurons in the salamander retina as it responds to natural movies. Already in groups as small as 10 neurons, interactions between spikes can no longer be regarded as small perturbations in an otherwise independent system; for 40 or more neurons pairwise interactions need to be supplemented by a global interaction that controls the distribution of synchrony in the population. Here we show that such “K-pairwise” models—being systematic extensions of the previously used pairwise Ising models—provide an excellent account of the data. We explore the properties of the neural vocabulary by: 1) estimating its entropy, which constrains the population's capacity to represent visual information; 2) classifying activity patterns into a small set of metastable collective modes; 3) showing that the neural codeword ensembles are extremely inhomogenous; 4) demonstrating that the state of individual neurons is highly predictable from the rest of the population, allowing the capacity for error correction. AU - Tkacik, Gasper AU - Marre, Olivier AU - Amodei, Dario AU - Schneidman, Elad AU - Bialek, William AU - Berry, Michael ID - 2257 IS - 1 JF - PLoS Computational Biology SN - 1553734X TI - Searching for collective behavior in a large network of sensory neurons VL - 10 ER - TY - JOUR AB - The copper-catalyzed diboration of ketones followed by an acid-catalyzed elimination leads to the formation of 1,1-disubstituted and trisubstituted vinyl boronate esters with moderate to good yields and selectivity. Addition of tosic acid to the crude diboration products provides the corresponding vinyl boronate esters upon elimination. The trisubstituted vinyl boronate esters are formed as the (Z)-olefin isomer, which was established by subjecting the products to a Suzuki–Miyaura coupling reaction to obtain alkenes of known geometry. AU - Guan, Weiye AU - Michael, Alicia Kathleen AU - McIntosh, Melissa L. AU - Koren-Selfridge, Liza AU - Scott, John P. AU - Clark, Timothy B. ID - 15161 IS - 15 JF - The Journal of Organic Chemistry KW - Organic Chemistry SN - 0022-3263 TI - Stereoselective formation of trisubstituted vinyl boronate esters by the acid-mediated elimination of α-hydroxyboronate esters VL - 79 ER - TY - JOUR AB - Selection for disease control is believed to have contributed to shape the organisation of insect societies — leading to interaction patterns that mitigate disease transmission risk within colonies, conferring them ‘organisational immunity’. Recent studies combining epidemiological models with social network analysis have identified general properties of interaction networks that may hinder propagation of infection within groups. These can be prophylactic and/or induced upon pathogen exposure. Here we review empirical evidence for these two types of organisational immunity in social insects and describe the individual-level behaviours that underlie it. We highlight areas requiring further investigation, and emphasise the need for tighter links between theory and empirical research and between individual-level and collective-level analyses. AU - Stroeymeyt, Nathalie AU - Casillas Perez, Barbara E AU - Cremer, Sylvia ID - 1999 IS - 1 JF - Current Opinion in Insect Science TI - Organisational immunity in social insects VL - 5 ER - 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 -