TY - JOUR
AB - We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study.
AU - Svoreňová, Mária
AU - Kretinsky, Jan
AU - Chmelik, Martin
AU - Chatterjee, Krishnendu
AU - Cěrná, Ivana
AU - Belta, Cǎlin
ID - 1407
IS - 2
JF - Nonlinear Analysis: Hybrid Systems
TI - Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games
VL - 23
ER -
TY - JOUR
AB - We consider N×N Hermitian random matrices H consisting of blocks of size M≥N6/7. The matrix elements are i.i.d. within the blocks, close to a Gaussian in the four moment matching sense, but their distribution varies from block to block to form a block-band structure, with an essential band width M. We show that the entries of the Green’s function G(z)=(H−z)−1 satisfy the local semicircle law with spectral parameter z=E+iη down to the real axis for any η≫N−1, using a combination of the supersymmetry method inspired by Shcherbina (J Stat Phys 155(3): 466–499, 2014) and the Green’s function comparison strategy. Previous estimates were valid only for η≫M−1. The new estimate also implies that the eigenvectors in the middle of the spectrum are fully delocalized.
AU - Bao, Zhigang
AU - Erdös, László
ID - 1528
IS - 3-4
JF - Probability Theory and Related Fields
SN - 01788051
TI - Delocalization for a class of random block band matrices
VL - 167
ER -
TY - CONF
AB - We study probabilistic models of natural images and extend the autoregressive family of PixelCNN models by incorporating latent variables. Subsequently, we describe two new generative image models that exploit different image transformations as latent variables: a quantized grayscale view of the image or a multi-resolution image pyramid. The proposed models tackle two known shortcomings of existing PixelCNN models: 1) their tendency to focus on low-level image details, while largely ignoring high-level image information, such as object shapes, and 2) their computationally costly procedure for image sampling. We experimentally demonstrate benefits of our LatentPixelCNN models, in particular showing that they produce much more realistically looking image samples than previous state-of-the-art probabilistic models.
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 1000
SN - 978-151085514-4
TI - PixelCNN models with auxiliary variables for natural image modeling
VL - 70
ER -
TY - CONF
AB - We present a computational approach for designing CurveUps, curvy shells that form from an initially flat state. They consist of small rigid tiles that are tightly held together by two pre-stretched elastic sheets attached to them. Our method allows the realization of smooth, doubly curved surfaces that can be fabricated as a flat piece. Once released, the restoring forces of the pre-stretched sheets support the object to take shape in 3D. CurveUps are structurally stable in their target configuration. The design process starts with a target surface. Our method generates a tile layout in 2D and optimizes the distribution, shape, and attachment areas of the tiles to obtain a configuration that is fabricable and in which the curved up state closely matches the target. Our approach is based on an efficient approximate model and a local optimization strategy for an otherwise intractable nonlinear optimization problem. We demonstrate the effectiveness of our approach for a wide range of shapes, all realized as physical prototypes.
AU - Guseinov, Ruslan
AU - Miguel, Eder
AU - Bickel, Bernd
ID - 1001
IS - 4
TI - CurveUps: Shaping objects from flat plates with tension-actuated curvature
VL - 36
ER -
TY - CONF
AB - We present an interactive design system to create functional mechanical objects. Our computational approach allows novice users to retarget an existing mechanical template to a user-specified input shape. Our proposed representation for a mechanical template encodes a parameterized mechanism, mechanical constraints that ensure a physically valid configuration, spatial relationships of mechanical parts to the user-provided shape, and functional constraints that specify an intended functionality. We provide an intuitive interface and optimization-in-the-loop approach for finding a valid configuration of the mechanism and the shape to ensure that higher-level functional goals are met. Our algorithm interactively optimizes the mechanism while the user manipulates the placement of mechanical components and the shape. Our system allows users to efficiently explore various design choices and to synthesize customized mechanical objects that can be fabricated with rapid prototyping technologies. We demonstrate the efficacy of our approach by retargeting various mechanical templates to different shapes and fabricating the resulting functional mechanical objects.
AU - Zhang, Ran
AU - Auzinger, Thomas
AU - Ceylan, Duygu
AU - Li, Wilmot
AU - Bickel, Bernd
ID - 1002
IS - 4
SN - 07300301
TI - Functionality-aware retargeting of mechanisms to 3D shapes
VL - 36
ER -
TY - CONF
AB - Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. Search problems for NGs include finding special strategy profiles such as a Nash equilibrium and a globally optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state spaces. We describe an abstraction-refinement methodology for reasoning about NGs. Our methodology is based on an abstraction function that maps the state space of an NG to a much smaller state space. We search for a global optimum and a Nash equilibrium by reasoning on an under- and an overapproximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. Our experimental results demonstrate the efficiency of the methodology.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Kupferman, Orna
ID - 1003
SN - 10450823
TI - An abstraction-refinement methodology for reasoning about network games
ER -
TY - JOUR
AB - The fundamental tasks of the root system are, besides anchoring, mediating interactions between plant and soil and providing the plant with water and nutrients. The architecture of the root system is controlled by endogenous mechanisms that constantly integrate environmental signals, such as availability of nutrients and water. Extremely important for efficient soil exploitation and survival under less favorable conditions is the developmental flexibility of the root system that is largely determined by its postembryonic branching capacity. Modulation of initiation and outgrowth of lateral roots provides roots with an exceptional plasticity, allows optimal adjustment to underground heterogeneity, and enables effective soil exploitation and use of resources. Here we discuss recent advances in understanding the molecular mechanisms that shape the plant root system and integrate external cues to adapt to the changing environment.
AU - Ötvös, Krisztina
AU - Benková, Eva
ID - 1004
JF - Current Opinion in Genetics & Development
SN - 0959437X
TI - Spatiotemporal mechanisms of root branching
VL - 45
ER -
TY - JOUR
AB - Background: The phenomenon of immune priming, i.e. enhanced protection following a secondary exposure to a pathogen, has now been demonstrated in a wide range of invertebrate species. Despite accumulating phenotypic evidence, knowledge of its mechanistic underpinnings is currently very limited. Here we used the system of the red flour beetle, Tribolium castaneum and the insect pathogen Bacillus thuringiensis (Bt) to further our molecular understanding of the oral immune priming phenomenon. We addressed how ingestion of bacterial cues (derived from spore supernatants) of an orally pathogenic and non-pathogenic Bt strain affects gene expression upon later challenge exposure, using a whole-transcriptome sequencing approach. Results: Whereas gene expression of individuals primed with the orally non-pathogenic strain showed minor changes to controls, we found that priming with the pathogenic strain induced regulation of a large set of distinct genes, many of which are known immune candidates. Intriguingly, the immune repertoire activated upon priming and subsequent challenge qualitatively differed from the one mounted upon infection with Bt without previous priming. Moreover, a large subset of priming-specific genes showed an inverse regulation compared to their regulation upon challenge only. Conclusions: Our data demonstrate that gene expression upon infection is strongly affected by previous immune priming. We hypothesise that this shift in gene expression indicates activation of a more targeted and efficient response towards a previously encountered pathogen, in anticipation of potential secondary encounter.
AU - Greenwood, Jenny
AU - Milutinovic, Barbara
AU - Peuß, Robert
AU - Behrens, Sarah
AU - Essar, Daniela
AU - Rosenstiel, Philip
AU - Schulenburg, Hinrich
AU - Kurtz, Joachim
ID - 1006
IS - 1
JF - BMC Genomics
SN - 14712164
TI - Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae
VL - 18
ER -
TY - JOUR
AB - A nonlinear system possesses an invariance with respect to a set of transformations if its output dynamics remain invariant when transforming the input, and adjusting the initial condition accordingly. Most research has focused on invariances with respect to time-independent pointwise transformations like translational-invariance (u(t) -> u(t) + p, p in R) or scale-invariance (u(t) -> pu(t), p in R>0). In this article, we introduce the concept of s0-invariances with respect to continuous input transformations exponentially growing/decaying over time. We show that s0-invariant systems not only encompass linear time-invariant (LTI) systems with transfer functions having an irreducible zero at s0 in R, but also that the input/output relationship of nonlinear s0-invariant systems possesses properties well known from their linear counterparts. Furthermore, we extend the concept of s0-invariances to second- and higher-order s0-invariances, corresponding to invariances with respect to transformations of the time-derivatives of the input, and encompassing LTI systems with zeros of multiplicity two or higher. Finally, we show that nth-order 0-invariant systems realize – under mild conditions – nth-order nonlinear differential operators: when excited by an input of a characteristic functional form, the system’s output converges to a constant value only depending on the nth (nonlinear) derivative of the input.
AU - Lang, Moritz
AU - Sontag, Eduardo
ID - 1007
JF - Automatica
SN - 00051098
TI - Zeros of nonlinear systems with input invariances
VL - 81C
ER -
TY - CONF
AB - A standard objective in partially-observable Markov decision processes (POMDPs) is to find a policy that maximizes the expected discounted-sum payoff. However, such policies may still permit unlikely but highly undesirable outcomes, which is problematic especially in safety-critical applications. Recently, there has been a surge of interest in POMDPs where the goal is to maximize the probability to ensure that the payoff is at least a given threshold, but these approaches do not consider any optimization beyond satisfying this threshold constraint. In this work we go beyond both the “expectation” and “threshold” approaches and consider a “guaranteed payoff optimization (GPO)” problem for POMDPs, where we are given a threshold t and the objective is to find a policy σ such that a) each possible outcome of σ yields a discounted-sum payoff of at least t, and b) the expected discounted-sum payoff of σ is optimal (or near-optimal) among all policies satisfying a). We present a practical approach to tackle the GPO problem and evaluate it on standard POMDP benchmarks.
AU - Chatterjee, Krishnendu
AU - Novotny, Petr
AU - Pérez, Guillermo
AU - Raskin, Jean
AU - Zikelic, Djordje
ID - 1009
T2 - Proceedings of the 31st AAAI Conference on Artificial Intelligence
TI - Optimizing expectation with guarantees in POMDPs
VL - 5
ER -
TY - JOUR
AB - We prove a local law in the bulk of the spectrum for random Gram matrices XX∗, a generalization of sample covariance matrices, where X is a large matrix with independent, centered entries with arbitrary variances. The limiting eigenvalue density that generalizes the Marchenko-Pastur law is determined by solving a system of nonlinear equations. Our entrywise and averaged local laws are on the optimal scale with the optimal error bounds. They hold both in the square case (hard edge) and in the properly rectangular case (soft edge). In the latter case we also establish a macroscopic gap away from zero in the spectrum of XX∗.
AU - Alt, Johannes
AU - Erdös, László
AU - Krüger, Torben H
ID - 1010
JF - Electronic Journal of Probability
SN - 10836489
TI - Local law for random Gram matrices
VL - 22
ER -
TY - CONF
AB - Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly equivalent, are standard models for interprocedural analysis. Yet RSMs are more convenient as they (a) explicitly model function calls and returns, and (b) specify many natural parameters for algorithmic analysis, e.g., the number of entries and exits. We consider a general framework where RSM transitions are labeled from a semiring and path properties are algebraic with semiring operations, which can model, e.g., interprocedural reachability and dataflow analysis problems. Our main contributions are new algorithms for several fundamental problems. As compared to a direct translation of RSMs to PDSs and the best-known existing bounds of PDSs, our analysis algorithm improves the complexity for finite-height semirings (that subsumes reachability and standard dataflow properties). We further consider the problem of extracting distance values from the representation structures computed by our algorithm, and give efficient algorithms that distinguish the complexity of a one-time preprocessing from the complexity of each individual query. Another advantage of our algorithm is that our improvements carry over to the concurrent setting, where we improve the bestknown complexity for the context-bounded analysis of concurrent RSMs. Finally, we provide a prototype implementation that gives a significant speed-up on several benchmarks from the SLAM/SDV project.
AU - Chatterjee, Krishnendu
AU - Kragl, Bernhard
AU - Mishra, Samarth
AU - Pavlogiannis, Andreas
ED - Yang, Hongseok
ID - 1011
SN - 03029743
TI - Faster algorithms for weighted recursive state machines
VL - 10201
ER -
TY - JOUR
AB - From microwave ovens to satellite television to the GPS and data services on our mobile phones, microwave technology is everywhere today. But one technology that has so far failed to prove its worth in this wavelength regime is quantum communication that uses the states of single photons as information carriers. This is because single microwave photons, as opposed to classical microwave signals, are extremely vulnerable to noise from thermal excitations in the channels through which they travel. Two new independent studies, one by Ze-Liang Xiang at Technische Universität Wien (Vienna), Austria, and colleagues [1] and another by Benoît Vermersch at the University of Innsbruck, also in Austria, and colleagues [2] now describe a theoretical protocol for microwave quantum communication that is resilient to thermal and other types of noise. Their approach could become a powerful technique to establish fast links between superconducting data processors in a future all-microwave quantum network.
AU - Fink, Johannes M
ID - 1013
IS - 32
JF - Physics
TI - Viewpoint: Microwave quantum states beat the heat
VL - 10
ER -
TY - JOUR
AB - We consider the large-scale regularity of solutions to second-order linear elliptic equations with random coefficient fields. In contrast to previous works on regularity theory for random elliptic operators, our interest is in the regularity at the boundary: We consider problems posed on the half-space with homogeneous Dirichlet boundary conditions and derive an associated C1,α-type large-scale regularity theory in the form of a corresponding decay estimate for the homogenization-adapted tilt-excess. This regularity theory entails an associated Liouville-type theorem. The results are based on the existence of homogenization correctors adapted to the half-space setting, which we construct-by an entirely deterministic argument-as a modification of the homogenization corrector on the whole space. This adaption procedure is carried out inductively on larger scales, crucially relying on the regularity theory already established on smaller scales.
AU - Fischer, Julian L
AU - Raithel, Claudia
ID - 1014
IS - 1
JF - SIAM Journal on Mathematical Analysis
SN - 00361410
TI - Liouville principles and a large-scale regularity theory for random elliptic operators on the half-space
VL - 49
ER -
TY - JOUR
AB - Vortices are commonly observed in the context of classical hydrodynamics: from whirlpools after stirring the coffee in a cup to a violent atmospheric phenomenon such as a tornado, all classical vortices are characterized by an arbitrary circulation value of the local velocity field. On the other hand the appearance of vortices with quantized circulation represents one of the fundamental signatures of macroscopic quantum phenomena. In two-dimensional superfluids quantized vortices play a key role in determining finite-temperature properties, as the superfluid phase and the normal state are separated by a vortex unbinding transition, the Berezinskii-Kosterlitz-Thouless transition. Very recent experiments with two-dimensional superfluid fermions motivate the present work: we present theoretical results based on the renormalization group showing that the universal jump of the superfluid density and the critical temperature crucially depend on the interaction strength, providing a strong benchmark for forthcoming investigations.
AU - Bighin, Giacomo
AU - Salasnich, Luca
ID - 1015
JF - Scientific Reports
SN - 20452322
TI - Vortices and antivortices in two-dimensional ultracold Fermi gases
VL - 7
ER -
TY - JOUR
AB - The development of the vertebrate central nervous system is reliant on a complex cascade of biological processes that include mitotic division, relocation of migrating neurons, and the extension of dendritic and axonal processes. Each of these cellular events requires the diverse functional repertoire of the microtubule cytoskeleton for the generation of forces, assembly of macromolecular complexes and transport of molecules and organelles. The tubulins are a multi-gene family that encode for the constituents of microtubules, and have been implicated in a spectrum of neurological disorders. Evidence is building that different tubulins tune the functional properties of the microtubule cytoskeleton dependent on the cell type, developmental profile and subcellular localisation. Here we review of the origins of the functional specification of the tubulin gene family in the developing brain at a transcriptional, translational, and post-transcriptional level. We remind the reader that tubulins are not just loading controls for your average Western blot.
AU - Breuss, Martin
AU - Leca, Ines
AU - Gstrein, Thomas
AU - Hansen, Andi H
AU - Keays, David
ID - 1017
JF - Molecular and Cellular Neuroscience
SN - 10447431
TI - Tubulins and brain development: The origins of functional specification
VL - 84
ER -
TY - JOUR
AB - Cellulose is the most abundant biopolymer on Earth. Cellulose fibers, such as the one extracted form cotton or woodpulp, have been used by humankind for hundreds of years to make textiles and paper. Here we show how, by engineering light-matter interaction, we can optimize light scattering using exclusively cellulose nanocrystals. The produced material is sustainable, biocompatible, and when compared to ordinary microfiber-based paper, it shows enhanced scattering strength (×4), yielding a transport mean free path as low as 3.5 μm in the visible light range. The experimental results are in a good agreement with the theoretical predictions obtained with a diffusive model for light propagation.
AU - Caixeiro, Soraya
AU - Peruzzo, Matilda
AU - Onelli, Olimpia
AU - Vignolini, Silvia
AU - Sapienza, Riccardo
ID - 1020
IS - 9
JF - ACS Applied Materials and Interfaces
SN - 19448244
TI - Disordered cellulose based nanostructures for enhanced light scattering
VL - 9
ER -
TY - JOUR
AB - Most flows in nature and engineering are turbulent because of their large velocities and spatial scales. Laboratory experiments on rotating quasi-Keplerian flows, for which the angular velocity decreases radially but the angular momentum increases, are however laminar at Reynolds numbers exceeding one million. This is in apparent contradiction to direct numerical simulations showing that in these experiments turbulence transition is triggered by the axial boundaries. We here show numerically that as the Reynolds number increases, turbulence becomes progressively confined to the boundary layers and the flow in the bulk fully relaminarizes. Our findings support that turbulence is unlikely to occur in isothermal constant-density quasi-Keplerian flows.
AU - Lopez Alonso, Jose M
AU - Avila, Marc
ID - 1021
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Boundary layer turbulence in experiments on quasi Keplerian flows
VL - 817
ER -
TY - JOUR
AB - We introduce a multiscale topological description of the Megaparsec web-like cosmic matter distribution. Betti numbers and topological persistence offer a powerful means of describing the rich connectivity structure of the cosmic web and of its multiscale arrangement of matter and galaxies. Emanating from algebraic topology and Morse theory, Betti numbers and persistence diagrams represent an extension and deepening of the cosmologically familiar topological genus measure and the related geometric Minkowski functionals. In addition to a description of the mathematical background, this study presents the computational procedure for computing Betti numbers and persistence diagrams for density field filtrations. The field may be computed starting from a discrete spatial distribution of galaxies or simulation particles. The main emphasis of this study concerns an extensive and systematic exploration of the imprint of different web-like morphologies and different levels of multiscale clustering in the corresponding computed Betti numbers and persistence diagrams. To this end, we use Voronoi clustering models as templates for a rich variety of web-like configurations and the fractal-like Soneira-Peebles models exemplify a range of multiscale configurations. We have identified the clear imprint of cluster nodes, filaments, walls, and voids in persistence diagrams, along with that of the nested hierarchy of structures in multiscale point distributions. We conclude by outlining the potential of persistent topology for understanding the connectivity structure of the cosmic web, in large simulations of cosmic structure formation and in the challenging context of the observed galaxy distribution in large galaxy surveys.
AU - Pranav, Pratyush
AU - Edelsbrunner, Herbert
AU - Van De Weygaert, Rien
AU - Vegter, Gert
AU - Kerber, Michael
AU - Jones, Bernard
AU - Wintraecken, Mathijs
ID - 1022
IS - 4
JF - Monthly Notices of the Royal Astronomical Society
SN - 00358711
TI - The topology of the cosmic web in terms of persistent Betti numbers
VL - 465
ER -
TY - JOUR
AB - We consider products of independent square non-Hermitian random matrices. More precisely, let X1,…, Xn be independent N × N random matrices with independent entries (real or complex with independent real and imaginary parts) with zero mean and variance 1/N. Soshnikov-O’Rourke [19] and Götze-Tikhomirov [15] showed that the empirical spectral distribution of the product of n random matrices with iid entries converges to (equation found). We prove that if the entries of the matrices X1,…, Xn are independent (but not necessarily identically distributed) and satisfy uniform subexponential decay condition, then in the bulk the convergence of the ESD of X1,…, Xn to (0.1) holds up to the scale N–1/2+ε.
AU - Nemish, Yuriy
ID - 1023
JF - Electronic Journal of Probability
SN - 10836489
TI - Local law for the product of independent non-Hermitian random matrices with independent entries
VL - 22
ER -
TY - JOUR
AB - Optogenetics and photopharmacology provide spatiotemporally precise control over protein interactions and protein function in cells and animals. Optogenetic methods that are sensitive to green light and can be used to break protein complexes are not broadly available but would enable multichromatic experiments with previously inaccessible biological targets. Herein, we repurposed cobalamin (vitamin B12) binding domains of bacterial CarH transcription factors for green-light-induced receptor dissociation. In cultured cells, we observed oligomerization-induced cell signaling for the fibroblast growth factor receptor 1 fused to cobalamin-binding domains in the dark that was rapidly eliminated upon illumination. In zebrafish embryos expressing fusion receptors, green light endowed control over aberrant fibroblast growth factor signaling during development. Green-light-induced domain dissociation and light-inactivated receptors will critically expand the optogenetic toolbox for control of biological processes.
AU - Kainrath, Stephanie
AU - Stadler, Manuela
AU - Gschaider-Reichhart, Eva
AU - Distel, Martin
AU - Janovjak, Harald L
ID - 1028
IS - 16
JF - Angewandte Chemie - International Edition
SN - 14337851
TI - Green-light-induced inactivation of receptor signaling using cobalamin-binding domains
VL - 56
ER -
TY - JOUR
AB - We investigate effects of quasiparticle poisoning in a Majorana island with strong tunnel coupling to normal-metal leads. In addition to the main Coulomb blockade diamonds, "shadow" diamonds appear, shifted by 1e in gate voltage, consistent with transport through an excited (poisoned) state of the island. Comparison to a simple model yields an estimate of parity lifetime for the strongly coupled island (∼1 μs) and sets a bound for a weakly coupled island (>10 μs). Fluctuations in the gate-voltage spacing of Coulomb peaks at high field, reflecting Majorana hybridization, are enhanced by the reduced lever arm at strong coupling. When converted from gate voltage to energy units, fluctuations are consistent with previous measurements.
AU - Albrecht, S M
AU - Hansen, Esben
AU - Higginbotham, Andrew P
AU - Kuemmeth, Ferdinand
AU - Jespersen, Thomas
AU - Nygård, Jesper
AU - Krogstrup, Peter
AU - Danon, Jeroen
AU - Flensberg, Karsten
AU - Marcus, Charles
ID - 103
IS - 13
JF - APS Physics, Physical Review Letters
TI - Transport signatures of quasiparticle poisoning in a majorana island
VL - 118
ER -
TY - JOUR
AB - Auf der Suche nach einem Bibliothekssystem entschied sich die Forschungseinrichtung IST Austria im Jahr 2014 für das Open-Source-Produkt Koha. In einem ersten Schritt wurden zunächst Grundfunktionen aktiviert um im Anschluss diverse zusätzliche Tools zum Einsatz zu bringen. Die große Flexibilität des Systems erlaubt maßgeschneiderte Lösungen für unterschiedlichste Institutionen. Trotz Herausforderungen kann die Bibliothek auf eine erfolgreiche Implementierung zurückblicken.
AU - Villányi, Márton
ID - 1030
IS - 1
JF - Informationspraxis
SN - 2297-3249
TI - Ein freies Bibliothekssystem für wissenschaftliche Bibliotheken – Werkstattbericht der IST Austria Library
VL - 3
ER -
TY - JOUR
AB - Background: Metabolic engineering and synthetic biology of cyanobacteria offer a promising sustainable alternative approach for fossil-based ethylene production, by using sunlight via oxygenic photosynthesis, to convert carbon dioxide directly into ethylene. Towards this, both well-studied cyanobacteria, i.e., Synechocystis sp PCC 6803 and Synechococcus elongatus PCC 7942, have been engineered to produce ethylene by introducing the ethylene-forming enzyme (Efe) from Pseudomonas syringae pv. phaseolicola PK2 (the Kudzu strain), which catalyzes the conversion of the ubiquitous tricarboxylic acid cycle intermediate 2-oxoglutarate into ethylene. Results: This study focuses on Synechocystis sp PCC 6803 and shows stable ethylene production through the integration of a codon-optimized version of the efe gene under control of the Ptrc promoter and the core Shine-Dalgarno sequence (5\'-AGGAGG-3\') as the ribosome-binding site (RBS), at the slr0168 neutral site. We have increased ethylene production twofold by RBS screening and further investigated improving ethylene production from a single gene copy of efe, using multiple tandem promoters and by putting our best construct on an RSF1010-based broad-host-self-replicating plasmid, which has a higher copy number than the genome. Moreover, to raise the intracellular amounts of the key Efe substrate, 2-oxoglutarate, from which ethylene is formed, we constructed a glycogen-synthesis knockout mutant (glgC) and introduced the ethylene biosynthetic pathway in it. Under nitrogen limiting conditions, the glycogen knockout strain has increased intracellular 2-oxoglutarate levels; however, surprisingly, ethylene production was lower in this strain than in the wild-type background. Conclusion: Making use of different RBS sequences, production of ethylene ranging over a 20-fold difference has been achieved. However, a further increase of production through multiple tandem promoters and a broad-host plasmid was not achieved speculating that the transcription strength and the gene copy number are not the limiting factors in our system.
AU - Veetil, Vinod
AU - Angermayr, Andreas
AU - Hellingwerf, Klaas
ID - 1061
IS - 1
JF - Microbial Cell Factories
SN - 14752859
TI - Ethylene production with engineered Synechocystis sp PCC 6803 strains
VL - 16
ER -
TY - JOUR
AB - Severe environmental change can drive a population extinct unless the population adapts in time to the new conditions (“evolutionary rescue”). How does biparental sexual reproduction influence the chances of population persistence compared to clonal reproduction or selfing? In this article, we set up a one‐locus two‐allele model for adaptation in diploid species, where rescue is contingent on the establishment of the mutant homozygote. Reproduction can occur by random mating, selfing, or clonally. Random mating generates and destroys the rescue mutant; selfing is efficient at generating it but at the same time depletes the heterozygote, which can lead to a low mutant frequency in the standing genetic variation. Due to these (and other) antagonistic effects, we find a nontrivial dependence of population survival on the rate of sex/selfing, which is strongly influenced by the dominance coefficient of the mutation before and after the environmental change. Importantly, since mating with the wild‐type breaks the mutant homozygote up, a slow decay of the wild‐type population size can impede rescue in randomly mating populations.
AU - Uecker, Hildegard
ID - 1063
IS - 4
JF - Evolution
SN - 00143820
TI - Evolutionary rescue in randomly mating, selfing, and clonal populations
VL - 71
ER -
TY - JOUR
AB - We consider the problem of reachability in pushdown graphs. We study the problem for pushdown graphs with constant treewidth. Even for pushdown graphs with treewidth 1, for the reachability problem we establish the following: (i) the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem would contradict the k-clique conjecture and imply faster combinatorial algorithms for cliques in graphs.
AU - Chatterjee, Krishnendu
AU - Osang, Georg F
ID - 1065
JF - Information Processing Letters
SN - 00200190
TI - Pushdown reachability with constant treewidth
VL - 122
ER -
TY - JOUR
AB - Embryo morphogenesis relies on highly coordinated movements of different tissues. However, remarkably little is known about how tissues coordinate their movements to shape the embryo. In zebrafish embryogenesis, coordinated tissue movements first become apparent during “doming,” when the blastoderm begins to spread over the yolk sac, a process involving coordinated epithelial surface cell layer expansion and mesenchymal deep cell intercalations. Here, we find that active surface cell expansion represents the key process coordinating tissue movements during doming. By using a combination of theory and experiments, we show that epithelial surface cells not only trigger blastoderm expansion by reducing tissue surface tension, but also drive blastoderm thinning by inducing tissue contraction through radial deep cell intercalations. Thus, coordinated tissue expansion and thinning during doming relies on surface cells simultaneously controlling tissue surface tension and radial tissue contraction.
AU - Morita, Hitoshi
AU - Grigolon, Silvia
AU - Bock, Martin
AU - Krens, Gabriel
AU - Salbreux, Guillaume
AU - Heisenberg, Carl-Philipp J
ID - 1067
IS - 4
JF - Developmental Cell
SN - 15345807
TI - The physical basis of coordinated tissue spreading in zebrafish gastrulation
VL - 40
ER -
TY - JOUR
AB - Given a finite set of points in Rn and a radius parameter, we study the Čech, Delaunay–Čech, Delaunay (or alpha), and Wrap complexes in the light of generalized discrete Morse theory. Establishing the Čech and Delaunay complexes as sublevel sets of generalized discrete Morse functions, we prove that the four complexes are simple-homotopy equivalent by a sequence of simplicial collapses, which are explicitly described by a single discrete gradient field.
AU - Bauer, Ulrich
AU - Edelsbrunner, Herbert
ID - 1072
IS - 5
JF - Transactions of the American Mathematical Society
TI - The Morse theory of Čech and delaunay complexes
VL - 369
ER -
TY - JOUR
AB - Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation.
AU - Čadek, Martin
AU - Krcál, Marek
AU - Vokřínek, Lukáš
ID - 1073
IS - 4
JF - Discrete & Computational Geometry
SN - 01795376
TI - Algorithmic solvability of the lifting extension problem
VL - 54
ER -
TY - JOUR
AB - Recently it has become feasible to detect long blocks of nearly identical sequence shared between pairs of genomes. These IBD blocks are direct traces of recent coalescence events and, as such, contain ample signal to infer recent demography. Here, we examine sharing of such blocks in two-dimensional populations with local migration. Using a diffusion approximation to trace genetic ancestry, we derive analytical formulae for patterns of isolation by distance of IBD blocks, which can also incorporate recent population density changes. We introduce an inference scheme that uses a composite likelihood approach to fit these formulae. We then extensively evaluate our theory and inference method on a range of scenarios using simulated data. We first validate the diffusion approximation by showing that the theoretical results closely match the simulated block sharing patterns. We then demonstrate that our inference scheme can accurately and robustly infer dispersal rate and effective density, as well as bounds on recent dynamics of population density. To demonstrate an application, we use our estimation scheme to explore the fit of a diffusion model to Eastern European samples in the POPRES data set. We show that ancestry diffusing with a rate of σ ≈ 50–100 km/√gen during the last centuries, combined with accelerating population growth, can explain the observed exponential decay of block sharing with increasing pairwise sample distance.
AU - Ringbauer, Harald
AU - Coop, Graham
AU - Barton, Nicholas H
ID - 1074
IS - 3
JF - Genetics
SN - 00166731
TI - Inferring recent demography from isolation by distance of long shared sequence blocks
VL - 205
ER -
TY - CHAP
AU - Wenzl, Bernhard
ED - Parker, Joshua
ED - Poole, Ralph
ID - 1075
SN - 978-3643908124
T2 - Austria and America: 20th-Century Cross-Cultural Encounters
TI - An American in Allied-occupied Austria: John Dos Passos Reports on "The Vienna Frontier"
VL - 15
ER -
TY - JOUR
AB - Signatures of the Coulomb corrections in the photoelectron momentum distribution during laser-induced ionization of atoms or ions in tunneling and multiphoton regimes are investigated analytically in the case of a one-dimensional problem. A high-order Coulomb-corrected strong-field approximation is applied, where the exact continuum state in the S matrix is approximated by the eikonal Coulomb-Volkov state including the second-order corrections to the eikonal. Although without high-order corrections our theory coincides with the known analytical R-matrix (ARM) theory, we propose a simplified procedure for the matrix element derivation. Rather than matching the eikonal Coulomb-Volkov wave function with the bound state as in the ARM theory to remove the Coulomb singularity, we calculate the matrix element via the saddle-point integration method by time as well as by coordinate, and in this way avoiding the Coulomb singularity. The momentum shift in the photoelectron momentum distribution with respect to the ARM theory due to high-order corrections is analyzed for tunneling and multiphoton regimes. The relation of the quantum corrections to the tunneling delay time is discussed.
AU - Klaiber, Michael
AU - Daněk, Jiří
AU - Yakaboylu, Enderalp
AU - Hatsagortsyan, Karen
AU - Keitel, Christoph
ID - 1076
IS - 2
JF - Physical Review A - Atomic, Molecular, and Optical Physics
SN - 24699926
TI - Strong-field ionization via a high-order Coulomb-corrected strong-field approximation
VL - 95
ER -
TY - JOUR
AB - Viral capsids are structurally constrained by interactions among the amino acids (AAs) of their constituent proteins. Therefore, epistasis is expected to evolve among physically interacting sites and to influence the rates of substitution. To study the evolution of epistasis, we focused on the major structural protein of the fX174 phage family by first reconstructing the ancestral protein sequences of 18 species using a Bayesian statistical framework. The inferred ancestral reconstruction differed at eight AAs, for a total of 256 possible ancestral haplotypes. For each ancestral haplotype and the extant species, we estimated, in silico, the distribution of free energies and epistasis of the capsid structure. We found that free energy has not significantly increased but epistasis has. We decomposed epistasis up to fifth order and found that higher-order epistasis sometimes compensates pairwise interactions making the free energy seem additive. The dN/dS ratio is low, suggesting strong purifying selection, and that structure is under stabilizing selection. We synthesized phages carrying ancestral haplotypes of the coat protein gene and measured their fitness experimentally. Our findings indicate that stabilizing mutations can have higher fitness, and that fitness optima do not necessarily coincide with energy minima.
AU - Fernandes Redondo, Rodrigo A
AU - Vladar, Harold
AU - Włodarski, Tomasz
AU - Bollback, Jonathan P
ID - 1077
IS - 126
JF - Journal of the Royal Society Interface
SN - 17425689
TI - Evolutionary interplay between structure, energy and epistasis in the coat protein of the fX174 phage family
VL - 14
ER -
TY - JOUR
AB - One of the key questions in understanding plant development is how single cells behave in a larger context of the tissue. Therefore, it requires the observation of the whole organ with a high spatial- as well as temporal resolution over prolonged periods of time, which may cause photo-toxic effects. This protocol shows a plant sample preparation method for light-sheet microscopy, which is characterized by mounting the plant vertically on the surface of a gel. The plant is mounted in such a way that the roots are submerged in a liquid medium while the leaves remain in the air. In order to ensure photosynthetic activity of the plant, a custom-made lighting system illuminates the leaves. To keep the roots in darkness the water surface is covered with sheets of black plastic foil. This method allows long-term imaging of plant organ development in standardized conditions.
AU - Von Wangenheim, Daniel
AU - Hauschild, Robert
AU - Friml, Jirí
ID - 1078
IS - 119
JF - Journal of visualized experiments JoVE
TI - Light sheet fluorescence microscopy of plant roots growing on the surface of a gel
VL - 2017
ER -
TY - JOUR
AB - We study the ionization problem in the Thomas-Fermi-Dirac-von Weizsäcker theory for atoms and molecules. We prove the nonexistence of minimizers for the energy functional when the number of electrons is large and the total nuclear charge is small. This nonexistence result also applies to external potentials decaying faster than the Coulomb potential. In the case of arbitrary nuclear charges, we obtain the nonexistence of stable minimizers and radial minimizers.
AU - Nam, Phan
AU - Van Den Bosch, Hanne
ID - 1079
IS - 2
JF - Mathematical Physics, Analysis and Geometry
SN - 13850172
TI - Nonexistence in Thomas Fermi-Dirac-von Weizsäcker theory with small nuclear charges
VL - 20
ER -
TY - JOUR
AB - Reconstructing the evolutionary history of metastases is critical for understanding their basic biological principles and has profound clinical implications. Genome-wide sequencing data has enabled modern phylogenomic methods to accurately dissect subclones and their phylogenies from noisy and impure bulk tumour samples at unprecedented depth. However, existing methods are not designed to infer metastatic seeding patterns. Here we develop a tool, called Treeomics, to reconstruct the phylogeny of metastases and map subclones to their anatomic locations. Treeomics infers comprehensive seeding patterns for pancreatic, ovarian, and prostate cancers. Moreover, Treeomics correctly disambiguates true seeding patterns from sequencing artifacts; 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumour heterogeneity among distinct samples. In silico benchmarking on simulated tumour phylogenies across a wide range of sample purities (15–95%) and sequencing depths (25-800 × ) demonstrates the accuracy of Treeomics compared with existing methods.
AU - Reiter, Johannes
AU - Makohon Moore, Alvin
AU - Gerold, Jeffrey
AU - Božić, Ivana
AU - Chatterjee, Krishnendu
AU - Iacobuzio Donahue, Christine
AU - Vogelstein, Bert
AU - Nowak, Martin
ID - 1080
JF - Nature Communications
SN - 20411723
TI - Reconstructing metastatic seeding patterns of human cancers
VL - 8
ER -
TY - JOUR
AB - Sex chromosomes evolve once recombination is halted between a homologous pair of chromosomes. The dominant model of sex chromosome evolution posits that recombination is suppressed between emerging X and Y chromosomes in order to resolve sexual conflict. Here we test this model using whole genome and transcriptome resequencing data in the guppy, a model for sexual selection with many Y-linked colour traits. We show that although the nascent Y chromosome encompasses nearly half of the linkage group, there has been no perceptible degradation of Y chromosome gene content or activity. Using replicate wild populations with differing levels of sexually antagonistic selection for colour, we also show that sexual selection leads to greater expansion of the non-recombining region and increased Y chromosome divergence. These results provide empirical support for longstanding models of sex chromosome catalysis, and suggest an important role for sexual selection and sexual conflict in genome evolution.
AU - Wright, Alison
AU - Darolti, Iulia
AU - Bloch, Natasha
AU - Oostra, Vicencio
AU - Sandkam, Benjamin
AU - Buechel, Séverine
AU - Kolm, Niclas
AU - Breden, Felix
AU - Vicoso, Beatriz
AU - Mank, Judith
ID - 1085
JF - Nature Communications
SN - 20411723
TI - Convergent recombination suppression suggests role of sexual selection in guppy sex chromosome formation
VL - 8
ER -
TY - JOUR
AB - Characterisation of G protein-coupled receptors (GPCR) relies on the availability of a toolbox of ligands that selectively modulate different functional states of the receptors. To uncover such molecules, we explored a unique strategy for ligand discovery that takes advantage of the evolutionary conservation of the 600-million-year-old oxytocin/vasopressin signalling system. We isolated the insect oxytocin/vasopressin orthologue inotocin from the black garden ant (Lasius niger), identified and cloned its cognate receptor and determined its pharmacological properties on the insect and human oxytocin/vasopressin receptors. Subsequently, we identified a functional dichotomy: inotocin activated the insect inotocin and the human vasopressin V1b receptors, but inhibited the human V1aR. Replacement of Arg8 of inotocin by D-Arg8 led to a potent, stable and competitive V1aR-antagonist ([D-Arg8]-inotocin) with a 3,000-fold binding selectivity for the human V1aR over the other three subtypes, OTR, V1bR and V2R. The Arg8/D-Arg8 ligand-pair was further investigated to gain novel insights into the oxytocin/vasopressin peptide-receptor interaction, which led to the identification of key residues of the receptors that are important for ligand functionality and selectivity. These observations could play an important role for development of oxytocin/vasopressin receptor modulators that would enable clear distinction of the physiological and pathological responses of the individual receptor subtypes.
AU - Di Giglio, Maria
AU - Muttenthaler, Markus
AU - Harpsøe, Kasper
AU - Liutkeviciute, Zita
AU - Keov, Peter
AU - Eder, Thomas
AU - Rattei, Thomas
AU - Arrowsmith, Sarah
AU - Wray, Susan
AU - Marek, Ales
AU - Elbert, Tomas
AU - Alewood, Paul
AU - Gloriam, David
AU - Gruber, Christian
ID - 1086
JF - Scientific Reports
TI - Development of a human vasopressin V1a-receptor antagonist from an evolutionary-related insect neuropeptide
VL - 7
ER -
TY - JOUR
AB - Using extensive direct numerical simulations, the dynamics of laminar-turbulent fronts in pipe flow is investigated for Reynolds numbers between and 5500. We here investigate the physical distinction between the fronts of weak and strong slugs both by analysing the turbulent kinetic energy budget and by comparing the downstream front motion to the advection speed of bulk turbulent structures. Our study shows that weak downstream fronts travel slower than turbulent structures in the bulk and correspond to decaying turbulence at the front. At the downstream front speed becomes faster than the advection speed, marking the onset of strong fronts. In contrast to weak fronts, turbulent eddies are generated at strong fronts by feeding on the downstream laminar flow. Our study also suggests that temporal fluctuations of production and dissipation at the downstream laminar-turbulent front drive the dynamical switches between the two types of front observed up to.
AU - Song, Baofang
AU - Barkley, Dwight
AU - Hof, Björn
AU - Avila, Marc
ID - 1087
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Speed and structure of turbulent fronts in pipe flow
VL - 813
ER -
TY - JOUR
AB - We discuss properties of distributions that are multivariate totally positive of order two (MTP2) related to conditional independence. In particular, we show that any independence model generated by an MTP2 distribution is a compositional semigraphoid which is upward-stable and singleton-transitive. In addition, we prove that any MTP2 distribution satisfying an appropriate support condition is faithful to its concentration graph. Finally, we analyze factorization properties of MTP2 distributions and discuss ways of constructing MTP2 distributions; in particular we give conditions on the log-linear parameters of a discrete distribution which ensure MTP2 and characterize conditional Gaussian distributions which satisfy MTP2.
AU - Fallat, Shaun
AU - Lauritzen, Steffen
AU - Sadeghi, Kayvan
AU - Uhler, Caroline
AU - Wermuth, Nanny
AU - Zwiernik, Piotr
ID - 1089
IS - 3
JF - Annals of Statistics
SN - 00905364
TI - Total positivity in Markov structures
VL - 45
ER -
TY - JOUR
AB - In the early visual system, cells of the same type perform the same computation in different places of the visual field. How these cells code together a complex visual scene is unclear. A common assumption is that cells of a single-type extract a single-stimulus feature to form a feature map, but this has rarely been observed directly. Using large-scale recordings in the rat retina, we show that a homogeneous population of fast OFF ganglion cells simultaneously encodes two radically different features of a visual scene. Cells close to a moving object code quasilinearly for its position, while distant cells remain largely invariant to the object's position and, instead, respond nonlinearly to changes in the object's speed. We develop a quantitative model that accounts for this effect and identify a disinhibitory circuit that mediates it. Ganglion cells of a single type thus do not code for one, but two features simultaneously. This richer, flexible neural map might also be present in other sensory systems.
AU - Deny, Stephane
AU - Ferrari, Ulisse
AU - Mace, Emilie
AU - Yger, Pierre
AU - Caplette, Romain
AU - Picaud, Serge
AU - Tkacik, Gasper
AU - Marre, Olivier
ID - 1104
IS - 1
JF - Nature Communications
SN - 20411723
TI - Multiplexed computations in retinal ganglion cells of a single type
VL - 8
ER -
TY - JOUR
AB - The generation, migration, and differentiation of neurons requires the functional integrity of the microtubule cytoskeleton. Mutations in the tubulin gene family are known to cause various neurological diseases including lissencephaly, ocular motor disorders, polymicrogyria and amyotrophic lateral sclerosis. We have previously reported that mutations in TUBB5 cause microcephaly that is accompanied by severe intellectual impairment and motor delay. Here we present the characterization of a Tubb5 mouse model that allows for the conditional expression of the pathogenic E401K mutation. Homozygous knockin animals exhibit a severe reduction in brain size and in body weight. These animals do not show any significant impairment in general activity, anxiety, or in the acoustic startle response, however, present with notable defects in motor coordination. When assessed on the static rod apparatus mice took longer to orient and often lost their balance completely. Interestingly, mutant animals also showed defects in prepulse inhibition, a phenotype associated with sensorimotor gating and considered an endophenotype for schizophrenia. This study provides insight into the behavioral consequences of tubulin gene mutations.
AU - Breuss, Martin
AU - Hansen, Andi H
AU - Landler, Lukas
AU - Keays, David
ID - 1107
JF - Behavioural Brain Research
SN - 01664328
TI - Brain specific knockin of the pathogenic Tubb5 E401K allele causes defects in motor coordination and prepulse inhibition
VL - 323
ER -
TY - CONF
AB - In this work we study the learnability of stochastic processes with respect to the conditional risk, i.e. the existence of a learning algorithm that improves its next-step performance with the amount of observed data. We introduce a notion of pairwise discrepancy between conditional distributions at different times steps and show how certain properties of these discrepancies can be used to construct a successful learning algorithm. Our main results are two theorems that establish criteria for learnability for many classes of stochastic processes, including all special cases studied previously in the literature.
AU - Zimin, Alexander
AU - Lampert, Christoph
ID - 1108
TI - Learning theory for conditional risk minimization
VL - 54
ER -
TY - JOUR
AB - Rotation of molecules embedded in He nanodroplets is explored by a combination of fs laser-induced alignment experiments and angulon quasiparticle theory. We demonstrate that at low fluence of the fs alignment pulse, the molecule and its solvation shell can be set into coherent collective rotation lasting long enough to form revivals. With increasing fluence, however, the revivals disappear -- instead, rotational dynamics as rapid as for an isolated molecule is observed during the first few picoseconds. Classical calculations trace this phenomenon to transient decoupling of the molecule from its He shell. Our results open novel opportunities for studying non-equilibrium solute-solvent dynamics and quantum thermalization.
AU - Shepperson, Benjamin
AU - Søndergaard, Anders
AU - Christiansen, Lars
AU - Kaczmarczyk, Jan
AU - Zillich, Robert
AU - Lemeshko, Mikhail
AU - Stapelfeldt, Henrik
ID - 1109
IS - 20
JF - Physical Review Letters
TI - Laser-induced rotation of iodine molecules in helium nanodroplets: Revivals and breaking-free
VL - 118
ER -
TY - JOUR
AB - The phytohormone auxin is a major determinant and regulatory component important for plant development. Auxin transport between cells is mediated by a complex system of transporters such as AUX1/LAX, PIN, and ABCB proteins, and their localization and activity is thought to be influenced by phosphatases and kinases. Flavonols have been shown to alter auxin transport activity and changes in flavonol accumulation in the Arabidopsis thaliana rol1-2 mutant cause defects in auxin transport and seedling development. A new mutation in ROOTS CURL IN NPA 1 (RCN1), encoding a regulatory subunit of the phosphatase PP2A, was found to suppress the growth defects of rol1-2 without changing the flavonol content. rol1-2 rcn1-3 double mutants show wild type-like auxin transport activity while levels of free auxin are not affected by rcn1-3. In the rol1-2 mutant, PIN2 shows a flavonol-induced basal-to-apical shift in polar localization which is reversed in the rol1-2 rcn1-3 to basal localization. In vivo analysis of PINOID action, a kinase known to influence PIN protein localization in a PP2A-antagonistic manner, revealed a negative impact of flavonols on PINOID activity. Together, these data suggest that flavonols affect auxin transport by modifying the antagonistic kinase/phosphatase equilibrium.
AU - Kuhn, Benjamin
AU - Nodzyński, Tomasz
AU - Errafi, Sanae
AU - Bucher, Rahel
AU - Gupta, Shibu
AU - Aryal, Bibek
AU - Dobrev, Petre
AU - Bigler, Laurent
AU - Geisler, Markus
AU - Zažímalová, Eva
AU - Friml, Jirí
AU - Ringli, Christoph
ID - 1110
JF - Scientific Reports
SN - 20452322
TI - Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity
VL - 7
ER -
TY - JOUR
AB - Adaptation depends critically on the effects of new mutations and their dependency on the genetic background in which they occur. These two factors can be summarized by the fitness landscape. However, it would require testing all mutations in all backgrounds, making the definition and analysis of fitness landscapes mostly inaccessible. Instead of postulating a particular fitness landscape, we address this problem by considering general classes of landscapes and calculating an upper limit for the time it takes for a population to reach a fitness peak, circumventing the need to have full knowledge about the fitness landscape. We analyze populations in the weak-mutation regime and characterize the conditions that enable them to quickly reach the fitness peak as a function of the number of sites under selection. We show that for additive landscapes there is a critical selection strength enabling populations to reach high-fitness genotypes, regardless of the distribution of effects. This threshold scales with the number of sites under selection, effectively setting a limit to adaptation, and results from the inevitable increase in deleterious mutational pressure as the population adapts in a space of discrete genotypes. Furthermore, we show that for the class of all unimodal landscapes this condition is sufficient but not necessary for rapid adaptation, as in some highly epistatic landscapes the critical strength does not depend on the number of sites under selection; effectively removing this barrier to adaptation.
AU - Heredia, Jorge
AU - Trubenova, Barbora
AU - Sudholt, Dirk
AU - Paixao, Tiago
ID - 1111
IS - 2
JF - Genetics
SN - 00166731
TI - Selection limits to adaptive walks on correlated landscapes
VL - 205
ER -
TY - JOUR
AB - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth.
AU - Fulek, Radoslav
AU - Pelsmajer, Michael
AU - Schaefer, Marcus
ID - 1113
IS - 1
JF - Journal of Graph Algorithms and Applications
TI - Hanani-Tutte for radial planarity
VL - 21
ER -
TY - JOUR
AB - Nonequilibrium phase transitions exist in damped-driven open quantum systems when the continuous tuning of an external parameter leads to a transition between two robust steady states. In second-order transitions this change is abrupt at a critical point, whereas in first-order transitions the two phases can coexist in a critical hysteresis domain. Here, we report the observation of a first-order dissipative quantum phase transition in a driven circuit quantum electrodynamics system. It takes place when the photon blockade of the driven cavity-atom system is broken by increasing the drive power. The observed experimental signature is a bimodal phase space distribution with varying weights controlled by the drive strength. Our measurements show an improved stabilization of the classical attractors up to the millisecond range when the size of the quantum system is increased from one to three artificial atoms. The formation of such robust pointer states could be used for new quantum measurement schemes or to investigate multiphoton phases of finite-size, nonlinear, open quantum systems.
AU - Fink, Johannes M
AU - Dombi, András
AU - Vukics, András
AU - Wallraff, Andreas
AU - Domokos, Peter
ID - 1114
IS - 1
JF - Physical Review X
SN - 21603308
TI - Observation of the photon blockade breakdown phase transition
VL - 7
ER -
TY - CONF
AB - Time-triggered switched networks are a deterministic communication infrastructure used by real-time distributed embedded systems. Due to the criticality of the applications running over them, developers need to ensure that end-to-end communication is dependable and predictable. Traditional approaches assume static networks that are not flexible to changes caused by reconfigurations or, more importantly, faults, which are dealt with in the application using redundancy. We adopt the concept of handling faults in the switches from non-real-time networks while maintaining the required predictability.
We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. For a given network with a forwarding scheme and a constant ℓ, we compute the {\em score} of the scheme, namely the probability (induced by faults) that at least ℓ messages arrive on time. We reduce the scoring problem to a reachability problem on a Markov chain with a "product-like" structure. Its special structure allows us to reason about it symbolically, and reduce the scoring problem to #SAT. Our solution is generic and can be adapted to different networks and other contexts. Also, we show the computational complexity of the scoring problem is #P-complete, and we study methods to estimate the score. We evaluate the effectiveness of our techniques with an implementation.
AU - Avni, Guy
AU - Goel, Shubham
AU - Henzinger, Thomas A
AU - Rodríguez Navas, Guillermo
ID - 1116
SN - 03029743
TI - Computing scores of forwarding schemes in switched networks with probabilistic faults
VL - 10206
ER -
TY - JOUR
AB - GABAergic synapses in brain circuits generate inhibitory output signals with submillisecond latency and temporal precision. Whether the molecular identity of the release sensor contributes to these signaling properties remains unclear. Here, we examined the Ca^2+ sensor of exocytosis at GABAergic basket cell (BC) to Purkinje cell (PC) synapses in cerebellum. Immunolabeling suggested that BC terminals selectively expressed synaptotagmin 2 (Syt2), whereas synaptotagmin 1 (Syt1) was enriched in excitatory terminals. Genetic elimination of Syt2 reduced action potential-evoked release to ∼10%, identifying Syt2 as the major Ca^2+ sensor at BC-PC synapses. Differential adenovirus-mediated rescue revealed that Syt2 triggered release with shorter latency and higher temporal precision and mediated faster vesicle pool replenishment than Syt1. Furthermore, deletion of Syt2 severely reduced and delayed disynaptic inhibition following parallel fiber stimulation. Thus, the selective use of Syt2 as release sensor at BC-PC synapses ensures fast and efficient feedforward inhibition in cerebellar microcircuits. #bioimagingfacility-author
AU - Chen, Chong
AU - Arai, Itaru
AU - Satterield, Rachel
AU - Young, Samuel
AU - Jonas, Peter M
ID - 1117
IS - 3
JF - Cell Reports
SN - 22111247
TI - Synaptotagmin 2 is the fast Ca2+ sensor at a central inhibitory synapse
VL - 18
ER -
TY - JOUR
AB - Sharp wave-ripple (SWR) oscillations play a key role in memory consolidation during non-rapid eye movement sleep, immobility, and consummatory behavior. However, whether temporally modulated synaptic excitation or inhibition underlies the ripples is controversial. To address this question, we performed simultaneous recordings of excitatory and inhibitory postsynaptic currents (EPSCs and IPSCs) and local field potentials (LFPs) in the CA1 region of awake mice in vivo. During SWRs, inhibition dominated over excitation, with a peak conductance ratio of 4.1 ± 0.5. Furthermore, the amplitude of SWR-associated IPSCs was positively correlated with SWR magnitude, whereas that of EPSCs was not. Finally, phase analysis indicated that IPSCs were phase-locked to individual ripple cycles, whereas EPSCs were uniformly distributed in phase space. Optogenetic inhibition indicated that PV+ interneurons provided a major contribution to SWR-associated IPSCs. Thus, phasic inhibition, but not excitation, shapes SWR oscillations in the hippocampal CA1 region in vivo.
AU - Gan, Jian
AU - Weng, Shih-Ming
AU - Pernia-Andrade, Alejandro
AU - Csicsvari, Jozsef L
AU - Jonas, Peter M
ID - 1118
IS - 2
JF - Neuron
TI - Phase-locked inhibition, but not excitation, underlies hippocampal ripple oscillations in awake mice in vivo
VL - 93
ER -
TY - JOUR
AB - Understanding the behavior of molecules interacting with superfluid helium represents a formidable challenge and, in general, requires approaches relying on large-scale numerical simulations. Here we demonstrate that experimental data collected over the last 20 years provide evidence that molecules immersed in superfluid helium form recently-predicted angulon quasiparticles [Phys. Rev. Lett. 114, 203001 (2015)]. Most importantly, casting the many-body problem in terms of angulons amounts to a drastic simplification and yields effective molecular moments of inertia as straightforward analytic solutions of a simple microscopic Hamiltonian. The outcome of the angulon theory is in good agreement with experiment for a broad range of molecular impurities, from heavy to medium-mass to light species. These results pave the way to understanding molecular rotation in liquid and crystalline phases in terms of the angulon quasiparticle.
AU - Lemeshko, Mikhail
ID - 1119
IS - 9
JF - Physical Review Letters
SN - 00319007
TI - Quasiparticle approach to molecules interacting with quantum solvents
VL - 118
ER -
TY - JOUR
AB - The existence of a self-localization transition in the polaron problem has been under an active debate ever since Landau suggested it 83 years ago. Here we reveal the self-localization transition for the rotational analogue of the polaron -- the angulon quasiparticle. We show that, unlike for the polarons, self-localization of angulons occurs at finite impurity-bath coupling already at the mean-field level. The transition is accompanied by the spherical-symmetry breaking of the angulon ground state and a discontinuity in the first derivative of the ground-state energy. Moreover, the type of the symmetry breaking is dictated by the symmetry of the microscopic impurity-bath interaction, which leads to a number of distinct self-localized states. The predicted effects can potentially be addressed in experiments on cold molecules trapped in superfluid helium droplets and ultracold quantum gases, as well as on electronic excitations in solids and Bose-Einstein condensates.
AU - Li, Xiang
AU - Seiringer, Robert
AU - Lemeshko, Mikhail
ID - 1120
IS - 3
JF - Physical Review A
SN - 24699926
TI - Angular self-localization of impurities rotating in a bosonic bath
VL - 95
ER -
TY - JOUR
AB - The hippocampus is thought to initiate systems-wide mnemonic processes through the reactivation of previously acquired spatial and episodic memory traces, which can recruit the entorhinal cortex as a first stage of memory redistribution to other brain areas. Hippocampal reactivation occurs during sharp wave-ripples, in which synchronous network firing encodes sequences of places.We investigated the coordination of this replay by recording assembly activity simultaneously in the CA1 region of the hippocampus and superficial layers of the medial entorhinal cortex. We found that entorhinal cell assemblies can replay trajectories independently of the hippocampus and sharp wave-ripples. This suggests that the hippocampus is not the sole initiator of spatial and episodic memory trace reactivation. Memory systems involved in these processes may include nonhierarchical, parallel components.
AU - O'Neill, Joseph
AU - Boccara, Charlotte
AU - Stella, Federico
AU - Schönenberger, Philipp
AU - Csicsvari, Jozsef L
ID - 1132
IS - 6321
JF - Science
SN - 00368075
TI - Superficial layers of the medial entorhinal cortex replay independently of the hippocampus
VL - 355
ER -
TY - JOUR
AB - It is a common knowledge that an effective interaction of a quantum impurity with an electromagnetic field can be screened by surrounding charge carriers, whether mobile or static. Here we demonstrate that very strong, "anomalous" screening can take place in the presence of a neutral, weakly polarizable environment, due to an exchange of orbital angular momentum between the impurity and the bath. Furthermore, we show that it is possible to generalize all phenomena related to isolated impurities in an external field to the case when a many-body environment is present, by casting the problem in terms of the angulon quasiparticle. As a result, the relevant observables such as the effective Rabi frequency, geometric phase, and impurity spatial alignment are straightforward to evaluate in terms of a single parameter: the angular-momentum-dependent screening factor.
AU - Yakaboylu, Enderalp
AU - Lemeshko, Mikhail
ID - 1133
IS - 8
JF - Physical Review Letters
SN - 00319007
TI - Anomalous screening of quantum impurities by a neutral environment
VL - 118
ER -
TY - JOUR
AB - We show that matrix elements of functions of N × N Wigner matrices fluctuate on a scale of order N−1/2 and we identify the limiting fluctuation. Our result holds for any function f of the matrix that has bounded variation thus considerably relaxing the regularity requirement imposed in [7, 11].
AU - Erdös, László
AU - Schröder, Dominik J
ID - 1144
JF - Electronic Communications in Probability
TI - Fluctuations of functions of Wigner matrices
VL - 21
ER -
TY - JOUR
AB - We propose a new memetic strategy that can solve the multi-physics, complex inverse problems, formulated as the multi-objective optimization ones, in which objectives are misfits between the measured and simulated states of various governing processes. The multi-deme structure of the strategy allows for both, intensive, relatively cheap exploration with a moderate accuracy and more accurate search many regions of Pareto set in parallel. The special type of selection operator prefers the coherent alternative solutions, eliminating artifacts appearing in the particular processes. The additional accuracy increment is obtained by the parallel convex searches applied to the local scalarizations of the misfit vector. The strategy is dedicated for solving ill-conditioned problems, for which inverting the single physical process can lead to the ambiguous results. The skill of the selection in artifact elimination is shown on the benchmark problem, while the whole strategy was applied for identification of oil deposits, where the misfits are related to various frequencies of the magnetic and electric waves of the magnetotelluric measurements. 2016 Elsevier B.V.
AU - Gajda-Zagorska, Ewa P
AU - Schaefer, Robert
AU - Smołka, Maciej
AU - Pardo, David
AU - Alvarez Aramberri, Julen
ID - 1152
JF - Journal of Computational Science
SN - 18777503
TI - A multi objective memetic inverse solver reinforced by local optimization methods
VL - 18
ER -
TY - THES
AB - This dissertation concerns the automatic verification of probabilistic systems and programs with arrays by statistical and logical methods. Although statistical and logical methods are different in nature, we show that they can be successfully combined for system analysis. In the first part of the dissertation we present a new statistical algorithm for the verification of probabilistic systems with respect to unbounded properties, including linear temporal logic. Our algorithm often performs faster than the previous approaches, and at the same time requires less information about the system. In addition, our method can be generalized to unbounded quantitative properties such as mean-payoff bounds. In the second part, we introduce two techniques for comparing probabilistic systems. Probabilistic systems are typically compared using the notion of equivalence, which requires the systems to have the equal probability of all behaviors. However, this notion is often too strict, since probabilities are typically only empirically estimated, and any imprecision may break the relation between processes. On the one hand, we propose to replace the Boolean notion of equivalence by a quantitative distance of similarity. For this purpose, we introduce a statistical framework for estimating distances between Markov chains based on their simulation runs, and we investigate which distances can be approximated in our framework. On the other hand, we propose to compare systems with respect to a new qualitative logic, which expresses that behaviors occur with probability one or a positive probability. This qualitative analysis is robust with respect to modeling errors and applicable to many domains. In the last part, we present a new quantifier-free logic for integer arrays, which allows us to express counting. Counting properties are prevalent in array-manipulating programs, however they cannot be expressed in the quantified fragments of the theory of arrays. We present a decision procedure for our logic, and provide several complexity results.
AU - Daca, Przemyslaw
ID - 1155
TI - Statistical and logical methods for property checking
ER -
TY - JOUR
AB - Auxin steers numerous physiological processes in plants, making the tight control of its endogenous levels and spatiotemporal distribution a necessity. This regulation is achieved by different mechanisms, including auxin biosynthesis, metabolic conversions, degradation, and transport. Here, we introduce cis-cinnamic acid (c-CA) as a novel and unique addition to a small group of endogenous molecules affecting in planta auxin concentrations. c-CA is the photo-isomerization product of the phenylpropanoid pathway intermediate trans-CA (t-CA). When grown on c-CA-containing medium, an evolutionary diverse set of plant species were shown to exhibit phenotypes characteristic for high auxin levels, including inhibition of primary root growth, induction of root hairs, and promotion of adventitious and lateral rooting. By molecular docking and receptor binding assays, we showed that c-CA itself is neither an auxin nor an anti-auxin, and auxin profiling data revealed that c-CA does not significantly interfere with auxin biosynthesis. Single cell-based auxin accumulation assays showed that c-CA, and not t-CA, is a potent inhibitor of auxin efflux. Auxin signaling reporters detected changes in spatiotemporal distribution of the auxin response along the root of c-CA-treated plants, and long-distance auxin transport assays showed no inhibition of rootward auxin transport. Overall, these results suggest that the phenotypes of c-CA-treated plants are the consequence of a local change in auxin accumulation, induced by the inhibition of auxin efflux. This work reveals a novel mechanism how plants may regulate auxin levels and adds a novel, naturally occurring molecule to the chemical toolbox for the studies of auxin homeostasis.
AU - Steenackers, Ward
AU - Klíma, Petr
AU - Quareshy, Mussa
AU - Cesarino, Igor
AU - Kumpf, Robert
AU - Corneillie, Sander
AU - Araújo, Pedro
AU - Viaene, Tom
AU - Goeminne, Geert
AU - Nowack, Moritz
AU - Ljung, Karin
AU - Friml, Jirí
AU - Blakeslee, Joshua
AU - Novák, Ondřej
AU - Zažímalová, Eva
AU - Napier, Richard
AU - Boerjan, Wout
AU - Vanholme, Bartel
ID - 1159
IS - 1
JF - Plant Physiology
SN - 00320889
TI - Cis-cinnamic acid is a novel natural auxin efflux inhibitor that promotes lateral root formation
VL - 173
ER -
TY - JOUR
AB - We investigate fundamental nonlinear dynamics of ferrofluidic Taylor-Couette flow - flow confined be-tween two concentric independently rotating cylinders - consider small aspect ratio by solving the ferro-hydrodynamical equations, carrying out systematic bifurcation analysis. Without magnetic field, we find steady flow patterns, previously observed with a simple fluid, such as those containing normal one- or two vortex cells, as well as anomalous one-cell and twin-cell flow states. However, when a symmetry-breaking transverse magnetic field is present, all flow states exhibit stimulated, finite two-fold mode. Various bifurcations between steady and unsteady states can occur, corresponding to the transitions between the two-cell and one-cell states. While unsteady, axially oscillating flow states can arise, we also detect the emergence of new unsteady flow states. In particular, we uncover two new states: one contains only the azimuthally oscillating solution in the configuration of the twin-cell flow state, and an-other a rotating flow state. Topologically, these flow states are a limit cycle and a quasiperiodic solution on a two-torus, respectively. Emergence of new flow states in addition to observed ones with classical fluid, indicates that richer but potentially more controllable dynamics in ferrofluidic flows, as such flow states depend on the external magnetic field.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1160
JF - Scientific Reports
SN - 20452322
TI - Dynamics of ferrofluidic flow in the Taylor-Couette system with a small aspect ratio
VL - 7
ER -
TY - JOUR
AB - Selected universal experimental properties of high-temperature superconducting (HTS) cuprates have been singled out in the last decade. One of the pivotal challenges in this field is the designation of a consistent interpretation framework within which we can describe quantitatively the universal features of those systems. Here we analyze in a detailed manner the principal experimental data and compare them quantitatively with the approach based on a single-band model of strongly correlated electrons supplemented with strong antiferromagnetic (super)exchange interaction (the so-called t−J−U model). The model rationale is provided by estimating its microscopic parameters on the basis of the three-band approach for the Cu-O plane. We use our original full Gutzwiller wave-function solution by going beyond the renormalized mean-field theory (RMFT) in a systematic manner. Our approach reproduces very well the observed hole doping (δ) dependence of the kinetic-energy gain in the superconducting phase, one of the principal non-Bardeen-Cooper-Schrieffer features of the cuprates. The calculated Fermi velocity in the nodal direction is practically δ-independent and its universal value agrees very well with that determined experimentally. Also, a weak doping dependence of the Fermi wave vector leads to an almost constant value of the effective mass in a pure superconducting phase which is both observed in experiment and reproduced within our approach. An assessment of the currently used models (t−J, Hubbard) is carried out and the results of the canonical RMFT as a zeroth-order solution are provided for comparison to illustrate the necessity of the introduced higher-order contributions.
AU - Spałek, Jozef
AU - Zegrodnik, Michał
AU - Kaczmarczyk, Jan
ID - 1162
IS - 2
JF - Physical Review B - Condensed Matter and Materials Physics
SN - 24699950
TI - Universal properties of high temperature superconductors from real space pairing t-J-U model and its quantitative comparison with experiment
VL - 95
ER -
TY - JOUR
AB - Optimum experimental design theory has recently been extended for parameter estimation in copula models. The use of these models allows one to gain in flexibility by considering the model parameter set split into marginal and dependence parameters. However, this separation also leads to the natural issue of estimating only a subset of all model parameters. In this work, we treat this problem with the application of the (Formula presented.)-optimality to copula models. First, we provide an extension of the corresponding equivalence theory. Then, we analyze a wide range of flexible copula models to highlight the usefulness of (Formula presented.)-optimality in many possible scenarios. Finally, we discuss how the usage of the introduced design criterion also relates to the more general issue of copula selection and optimal design for model discrimination.
AU - Perrone, Elisa
AU - Rappold, Andreas
AU - Müller, Werner
ID - 1168
IS - 3
JF - Statistical Methods and Applications
TI - D inf s optimality in copula models
VL - 26
ER -
TY - JOUR
AB - Dispersal is a crucial factor in natural evolution, since it determines the habitat experienced by any population and defines the spatial scale of interactions between individuals. There is compelling evidence for systematic differences in dispersal characteristics within the same population, i.e., genotype-dependent dispersal. The consequences of genotype-dependent dispersal on other evolutionary phenomena, however, are poorly understood. In this article we investigate the effect of genotype-dependent dispersal on spatial gene frequency patterns, using a generalization of the classical diffusion model of selection and dispersal. Dispersal is characterized by the variance of dispersal (diffusion coefficient) and the mean displacement (directional advection term). We demonstrate that genotype-dependent dispersal may change the qualitative behavior of Fisher waves, which change from being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between genotypes increases. The speed of any wave is partitioned into components due to selection, genotype-dependent variance of dispersal, and genotype-dependent mean displacement. We apply our findings to wave fronts maintained by selection against heterozygotes. Furthermore, we identify a benefit of increased variance of dispersal, quantify its effect on the speed of the wave, and discuss the implications for the evolution of dispersal strategies.
AU - Novak, Sebastian
AU - Kollár, Richard
ID - 1169
IS - 1
JF - Genetics
SN - 00166731
TI - Spatial gene frequency waves under genotype dependent dispersal
VL - 205
ER -
TY - JOUR
AB - We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.
AU - Edelsbrunner, Herbert
AU - Glazyrin, Alexey
AU - Musin, Oleg
AU - Nikitenko, Anton
ID - 1173
IS - 5
JF - Combinatorica
SN - 02099683
TI - The Voronoi functional is maximized by the Delaunay triangulation in the plane
VL - 37
ER -
TY - CONF
AB - Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\'13, CRYPTO\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.
AU - Skórski, Maciej
ID - 1174
SN - 18688969
TI - Lower bounds on key derivation for square-friendly applications
VL - 66
ER -
TY - CONF
AB - We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.
AU - Alwen, Joel F
AU - De Rezende, Susanna
AU - Nordstrom, Jakob
AU - Vinyals, Marc
ED - Papadimitriou, Christos
ID - 1175
SN - 18688969
TI - Cumulative space in black-white pebbling and resolution
VL - 67
ER -
TY - CONF
AB - The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A.
AU - Alwen, Joel F
AU - Blocki, Jeremiah
ID - 1176
SN - 978-150905761-0
TI - Towards practical attacks on Argon2i and balloon hashing
ER -
TY - CONF
AB - For any pair (X, Z) of correlated random variables we can think of Z as a randomized function of X. If the domain of Z is small, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as simulating auxiliary inputs. This idea of simulating auxiliary information turns out to be a very usefull tool, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: (a) We present a novel boosting algorithm for constructing the simulator. This boosting proof is of independent interest, as it shows how to handle “negative mass” issues when constructing probability measures by shifting distinguishers in descent algorithms. Our technique essentially fixes the flaw in the TCC’14 paper “How to Fake Auxiliary Inputs”. (b) The complexity of our simulator is better than in previous works, including results derived from the uniform min-max theorem due to Vadhan and Zheng. To achieve (s,ϵ) -indistinguishability we need the complexity O(s⋅25ℓϵ−2) in time/circuit size, which improve previous bounds by a factor of ϵ−2. In particular, with we get meaningful provable security for the EUROCRYPT’09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like
AU - Skórski, Maciej
ID - 1178
TI - Simulating auxiliary inputs, revisited
VL - 9985
ER -
TY - JOUR
AB - In this article we define an algebraic vertex of a generalized polyhedron and show that the set of algebraic vertices is the smallest set of points needed to define the polyhedron. We prove that the indicator function of a generalized polytope P is a linear combination of indicator functions of simplices whose vertices are algebraic vertices of P. We also show that the indicator function of any generalized polyhedron is a linear combination, with integer coefficients, of indicator functions of cones with apices at algebraic vertices and line-cones. The concept of an algebraic vertex is closely related to the Fourier–Laplace transform. We show that a point v is an algebraic vertex of a generalized polyhedron P if and only if the tangent cone of P, at v, has non-zero Fourier–Laplace transform.
AU - Akopyan, Arseniy
AU - Bárány, Imre
AU - Robins, Sinai
ID - 1180
JF - Advances in Mathematics
SN - 00018708
TI - Algebraic vertices of non-convex polyhedra
VL - 308
ER -
TY - JOUR
AB - We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol.
AU - Kiltz, Eike
AU - Pietrzak, Krzysztof Z
AU - Venturi, Daniele
AU - Cash, David
AU - Jain, Abhishek
ID - 1187
IS - 4
JF - Journal of Cryptology
TI - Efficient authentication from hard learning problems
VL - 30
ER -
TY - JOUR
AB - Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed.
AU - Kollár, Richard
AU - Novak, Sebastian
ID - 1191
IS - 3
JF - Bulletin of Mathematical Biology
TI - Existence of traveling waves for the generalized F–KPP equation
VL - 79
ER -
TY - CONF
AB - The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 1192
SN - 978-161197478-2
TI - Even delta-matroids and the complexity of planar Boolean CSPs
ER -
TY - CONF
AB - Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples.
AU - Chatterjee, Krishnendu
AU - Novotny, Petr
AU - Zikelic, Djordje
ID - 1194
IS - 1
SN - 07308566
TI - Stochastic invariants for probabilistic termination
VL - 52
ER -
TY - JOUR
AB - We consider a model of fermions interacting via point interactions, defined via a certain weighted Dirichlet form. While for two particles the interaction corresponds to infinite scattering length, the presence of further particles effectively decreases the interaction strength. We show that the model becomes trivial in the thermodynamic limit, in the sense that the free energy density at any given particle density and temperature agrees with the corresponding expression for non-interacting particles.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 1198
IS - 3
JF - Letters in Mathematical Physics
SN - 03779017
TI - Triviality of a model of particles with point interactions in the thermodynamic limit
VL - 107
ER -
TY - JOUR
AB - Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.
AU - Barton, Nicholas H
ID - 1199
JF - Heredity
TI - How does epistasis influence the response to selection?
VL - 118
ER -
TY - JOUR
AB - The eigenvalue distribution of the sum of two large Hermitian matrices, when one of them is conjugated by a Haar distributed unitary matrix, is asymptotically given by the free convolution of their spectral distributions. We prove that this convergence also holds locally in the bulk of the spectrum, down to the optimal scales larger than the eigenvalue spacing. The corresponding eigenvectors are fully delocalized. Similar results hold for the sum of two real symmetric matrices, when one is conjugated by Haar orthogonal matrix.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 1207
IS - 3
JF - Communications in Mathematical Physics
SN - 00103616
TI - Local law of addition of random matrices on optimal scale
VL - 349
ER -
TY - JOUR
AB - We study parameter estimation in linear Gaussian covariance models, which are p-dimensional Gaussian models with linear constraints on the covariance matrix. Maximum likelihood estimation for this class of models leads to a non-convex optimization problem which typically has many local maxima. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution, we provide sufficient conditions for any hill climbing method to converge to the global maximum. Although we are primarily interested in the case in which n≫p, the proofs of our results utilize large sample asymptotic theory under the scheme n/p→γ>1. Remarkably, our numerical simulations indicate that our results remain valid for p as small as 2. An important consequence of this analysis is that, for sample sizes n≃14p, maximum likelihood estimation for linear Gaussian covariance models behaves as if it were a convex optimization problem. © 2016 The Royal Statistical Society and Blackwell Publishing Ltd.
AU - Zwiernik, Piotr
AU - Uhler, Caroline
AU - Richards, Donald
ID - 1208
IS - 4
JF - Journal of the Royal Statistical Society. Series B: Statistical Methodology
SN - 13697412
TI - Maximum likelihood estimation for linear Gaussian covariance models
VL - 79
ER -
TY - JOUR
AB - Systems such as fluid flows in channels and pipes or the complex Ginzburg–Landau system, defined over periodic domains, exhibit both continuous symmetries, translational and rotational, as well as discrete symmetries under spatial reflections or complex conjugation. The simplest, and very common symmetry of this type is the equivariance of the defining equations under the orthogonal group O(2). We formulate a novel symmetry reduction scheme for such systems by combining the method of slices with invariant polynomial methods, and show how it works by applying it to the Kuramoto–Sivashinsky system in one spatial dimension. As an example, we track a relative periodic orbit through a sequence of bifurcations to the onset of chaos. Within the symmetry-reduced state space we are able to compute and visualize the unstable manifolds of relative periodic orbits, their torus bifurcations, a transition to chaos via torus breakdown, and heteroclinic connections between various relative periodic orbits. It would be very hard to carry through such analysis in the full state space, without a symmetry reduction such as the one we present here.
AU - Budanur, Nazmi B
AU - Cvitanović, Predrag
ID - 1211
IS - 3-4
JF - Journal of Statistical Physics
TI - Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system
VL - 167
ER -
TY - JOUR
AB - Since 2006, reprogrammed cells have increasingly been used as a biomedical research technique in addition to neuro-psychiatric methods. These rapidly evolving techniques allow for the generation of neuronal sub-populations, and have sparked interest not only in monogenetic neuro-psychiatric diseases, but also in poly-genetic and poly-aetiological disorders such as schizophrenia (SCZ) and bipolar disorder (BPD). This review provides a summary of 19 publications on reprogrammed adult somatic cells derived from patients with SCZ, and five publications using this technique in patients with BPD. As both disorders are complex and heterogeneous, there is a plurality of hypotheses to be tested in vitro. In SCZ, data on alterations of dopaminergic transmission in vitro are sparse, despite the great explanatory power of the so-called DA hypothesis of SCZ. Some findings correspond to perturbations of cell energy metabolism, and observations in reprogrammed cells suggest neuro-developmental alterations. Some studies also report on the efficacy of medicinal compounds to revert alterations observed in cellular models. However, due to the paucity of replication studies, no comprehensive conclusions can be drawn from studies using reprogrammed cells at the present time. In the future, findings from cell culture methods need to be integrated with clinical, epidemiological, pharmacological and imaging data in order to generate a more comprehensive picture of SCZ and BPD.
AU - Sauerzopf, Ulrich
AU - Sacco, Roberto
AU - Novarino, Gaia
AU - Niello, Marco
AU - Weidenauer, Ana
AU - Praschak Rieder, Nicole
AU - Sitte, Harald
AU - Willeit, Matthaeus
ID - 1228
IS - 1
JF - European Journal of Neuroscience
TI - Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence
VL - 45
ER -
TY - JOUR
AB - The Leidenfrost effect occurs when an object near a hot surface vaporizes rapidly enough to lift itself up and hover. Although well understood for liquids and stiff sublimable solids, nothing is known about the effect with materials whose stiffness lies between these extremes. Here we introduce a new phenomenon that occurs with vaporizable soft solids - the elastic Leidenfrost effect. By dropping hydrogel spheres onto hot surfaces we find that, rather than hovering, they energetically bounce several times their diameter for minutes at a time. With high-speed video during a single impact, we uncover high-frequency microscopic gap dynamics at the sphere/substrate interface. We show how these otherwise-hidden agitations constitute work cycles that harvest mechanical energy from the vapour and sustain the bouncing. Our findings suggest a new strategy for injecting mechanical energy into a widely used class of soft materials, with potential relevance to fields such as active matter, soft robotics and microfluidics.
AU - Waitukaitis, Scott R
AU - Zuiderwijk, Antal
AU - Souslov, Anton
AU - Coulais, Corentin
AU - Van Hecke, Martin
ID - 123
IS - 11
JF - Nature Physics
TI - Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing
VL - 13
ER -
TY - JOUR
AB - We study the lengths of curves passing through a fixed number of points on the boundary of a convex shape in the plane. We show that, for any convex shape K, there exist four points on the boundary of K such that the length of any curve passing through these points is at least half of the perimeter of K. It is also shown that the same statement does not remain valid with the additional constraint that the points are extreme points of K. Moreover, the factor ½ cannot be achieved with any fixed number of extreme points. We conclude the paper with a few other inequalities related to the perimeter of a convex shape.
AU - Akopyan, Arseniy
AU - Vysotsky, Vladislav
ID - 909
IS - 7
JF - The American Mathematical Monthly
SN - 00029890
TI - On the lengths of curves passing through boundary points of a planar convex shape
VL - 124
ER -
TY - JOUR
AB - Frequency-independent selection is generally considered as a force that acts to reduce the genetic variation in evolving populations, yet rigorous arguments for this idea are scarce. When selection fluctuates in time, it is unclear whether frequency-independent selection may maintain genetic polymorphism without invoking additional mechanisms. We show that constant frequency-independent selection with arbitrary epistasis on a well-mixed haploid population eliminates genetic variation if we assume linkage equilibrium between alleles. To this end, we introduce the notion of frequency-independent selection at the level of alleles, which is sufficient to prove our claim and contains the notion of frequency-independent selection on haploids. When selection and recombination are weak but of the same order, there may be strong linkage disequilibrium; numerical calculations show that stable equilibria are highly unlikely. Using the example of a diallelic two-locus model, we then demonstrate that frequency-independent selection that fluctuates in time can maintain stable polymorphism if linkage disequilibrium changes its sign periodically. We put our findings in the context of results from the existing literature and point out those scenarios in which the possible role of frequency-independent selection in maintaining genetic variation remains unclear.
AU - Novak, Sebastian
AU - Barton, Nicholas H
ID - 910
IS - 2
JF - Genetics
TI - When does frequency-independent selection maintain genetic variation?
VL - 207
ER -
TY - CONF
AB - We develop a probabilistic technique for colorizing grayscale natural images. In light of the intrinsic uncertainty of this task, the proposed probabilistic framework has numerous desirable properties. In particular, our model is able to produce multiple plausible and vivid colorizations for a given grayscale image and is one of the first colorization models to provide a proper stochastic sampling scheme. Moreover, our training procedure is supported by a rigorous theoretical framework that does not require any ad hoc heuristics and allows for efficient modeling and learning of the joint pixel color distribution.We demonstrate strong quantitative and qualitative experimental results on the CIFAR-10 dataset and the challenging ILSVRC 2012 dataset.
AU - Royer, Amélie
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 911
TI - Probabilistic image colorization
ER -
TY - JOUR
AB - We consider a many-body system of fermionic atoms interacting via a local pair potential and subject to an external potential within the framework of Bardeen-Cooper-Schrieffer (BCS) theory. We measure the free energy of the whole sample with respect to the free energy of a reference state which allows us to define a BCS functional with boundary conditions at infinity. Our main result is a lower bound for this energy functional in terms of expressions that typically appear in Ginzburg-Landau functionals.
AU - Deuchert, Andreas
ID - 912
IS - 8
JF - Journal of Mathematical Physics
SN - 00222488
TI - A lower bound for the BCS functional with boundary conditions at infinity
VL - 58
ER -
TY - JOUR
AB - Pools of air cooled by partial rain evaporation span up to several hundreds of kilometers in nature and typically last less than 1 day, ultimately losing their identity to the large-scale flow. These fundamentally differ in character from the radiatively-driven dry pools defining convective aggregation. Advancement in remote sensing and in computer capabilities has promoted exploration of how precipitation-induced cold pool processes modify the convective spectrum and life cycle. This contribution surveys current understanding of such cold pools over the tropical and subtropical oceans. In shallow convection with low rain rates, the cold pools moisten, preserving the near-surface equivalent potential temperature or increasing it if the surface moisture fluxes cannot ventilate beyond the new surface layer; both conditions indicate downdraft origin air from within the boundary layer. When rain rates exceed ∼ 2 mm h−1, convective-scale downdrafts can bring down drier air of lower equivalent potential temperature from above the boundary layer. The resulting density currents facilitate the lifting of locally thermodynamically favorable air and can impose an arc-shaped mesoscale cloud organization. This organization allows clouds capable of reaching 4–5 km within otherwise dry environments. These are more commonly observed in the northern hemisphere trade wind regime, where the flow to the intertropical convergence zone is unimpeded by the equator. Their near-surface air properties share much with those shown from cold pools sampled in the equatorial Indian Ocean. Cold pools are most effective at influencing the mesoscale organization when the atmosphere is moist in the lower free troposphere and dry above, suggesting an optimal range of water vapor paths. Outstanding questions on the relationship between cold pools, their accompanying moisture distribution and cloud cover are detailed further. Near-surface water vapor rings are documented in one model inside but near the cold pool edge; these are not consistent with observations, but do improve with smaller horizontal grid spacings.
AU - Zuidema, Paquita
AU - Torri, Giuseppe
AU - MULLER, Caroline J
AU - Chandra, Arunchandra
ID - 9137
IS - 6
JF - Surveys in Geophysics
KW - Geochemistry and Petrology
KW - Geophysics
SN - 0169-3298
TI - A survey of precipitation-induced atmospheric cold pools over oceans and their interactions with the larger-scale environment
VL - 38
ER -
TY - JOUR
AB - Convective self-aggregation, the spontaneous organization of initially scattered convection into isolated convective clusters despite spatially homogeneous boundary conditions and forcing, was first recognized and studied in idealized numerical simulations. While there is a rich history of observational work on convective clustering and organization, there have been only a few studies that have analyzed observations to look specifically for processes related to self-aggregation in models. Here we review observational work in both of these categories and motivate the need for more of this work. We acknowledge that self-aggregation may appear to be far-removed from observed convective organization in terms of time scales, initial conditions, initiation processes, and mean state extremes, but we argue that these differences vary greatly across the diverse range of model simulations in the literature and that these comparisons are already offering important insights into real tropical phenomena. Some preliminary new findings are presented, including results showing that a self-aggregation simulation with square geometry has too broad distribution of humidity and is too dry in the driest regions when compared with radiosonde records from Nauru, while an elongated channel simulation has realistic representations of atmospheric humidity and its variability. We discuss recent work increasing our understanding of how organized convection and climate change may interact, and how model discrepancies related to this question are prompting interest in observational comparisons. We also propose possible future directions for observational work related to convective aggregation, including novel satellite approaches and a ground-based observational network.
AU - Holloway, Christopher E.
AU - Wing, Allison A.
AU - Bony, Sandrine
AU - MULLER, Caroline J
AU - Masunaga, Hirohiko
AU - L’Ecuyer, Tristan S.
AU - Turner, David D.
AU - Zuidema, Paquita
ID - 9138
IS - 6
JF - Surveys in Geophysics
KW - Geochemistry and Petrology
KW - Geophysics
SN - 0169-3298
TI - Observing convective aggregation
VL - 38
ER -
TY - JOUR
AB - Infections with potentially lethal pathogens may negatively affect an individual’s lifespan and decrease its reproductive value. The terminal investment hypothesis predicts that individuals faced with a reduced survival should invest more into reproduction instead of maintenance and growth. Several studies suggest that individuals are indeed able to estimate their body condition and to increase their reproductive effort with approaching death, while other studies gave ambiguous results. We investigate whether queens of a perennial social insect (ant) are able to boost their reproduction following infection with an obligate killing pathogen. Social insect queens are special with regard to reproduction and aging, as they outlive conspecific non-reproductive workers. Moreover, in the ant Cardiocondyla obscurior, fecundity increases with queen age. However, it remained unclear whether this reflects negative reproductive senescence or terminal investment in response to approaching death. Here, we test whether queens of C. obscurior react to infection with the entomopathogenic fungus Metarhizium brunneum by an increased egg-laying rate. We show that a fungal infection triggers a reinforced investment in reproduction in queens. This adjustment of the reproductive rate by ant queens is consistent with predictions of the terminal investment hypothesis and is reported for the first time in a social insect.
AU - Giehr, Julia
AU - Grasse, Anna V
AU - Cremer, Sylvia
AU - Heinze, Jürgen
AU - Schrempf, Alexandra
ID - 914
IS - 7
JF - Royal Society Open Science
SN - 20545703
TI - Ant queens increase their reproductive efforts after pathogen infection
VL - 4
ER -
TY - CONF
AB - We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.
AU - Swoboda, Paul
AU - Andres, Bjoern
ID - 915
SN - 978-153860457-1
TI - A message passing algorithm for the minimum cost multicut problem
VL - 2017
ER -
TY - JOUR
AB - Previous numerical studies of the dissipation of internal tides in idealized settings suggest the existence of a critical latitude (~29°) where dissipation is enhanced. But observations only indicate a modest enhancement at this latitude. To resolve this difference between observational and numerical results, the authors study the latitudinal dependence of internal tides’ dissipation in more realistic conditions. In particular, the ocean is not a quiescent medium; the presence of large-scale currents or mesoscale eddies can impact the propagation and dissipation of internal tides. This paper investigates the impact of a weak background mean current in numerical simulations. The authors focus on the local dissipation of high spatial mode internal waves near their generation site. The vertical profile of dissipation and its variation with latitude without the mean current are consistent with earlier studies. But adding a weak mean current has a major impact on the latitudinal distribution of dissipation. The peak at the critical latitude disappears, and the dissipation is closer to a constant, albeit with two weak peaks at ~25° and ~35° latitude. This disappearance results from the Doppler shift of the internal tides’ frequency, which hinders the nonlinear transfer of energy to small-scale secondary waves via the parametric subharmonic instability (PSI). The new two weak peaks correspond to the Doppler-shifted critical latitudes of the left- and right-propagating waves. The results are confirmed in simulations with simple sinusoidal topography. Thus, although nonlinear transfers via PSI are efficient at dissipating internal tides, the exact location of the dissipation is sensitive to large-scale oceanic conditions.
AU - Richet, O.
AU - MULLER, Caroline J
AU - Chomaz, J.-M.
ID - 9152
IS - 6
JF - Journal of Physical Oceanography
KW - Oceanography
SN - 0022-3670
TI - Impact of a mean current on the internal tide energy dissipation at the critical latitude
VL - 47
ER -
TY - CONF
AB - We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.
AU - Swoboda, Paul
AU - Rother, Carsten
AU - Abu Alhaija, Carsten
AU - Kainmueller, Dagmar
AU - Savchynskyy, Bogdan
ID - 916
SN - 978-153860457-1
TI - A study of lagrangean decompositions and dual ascent solvers for graph matching
VL - 2017
ER -
TY - CONF
AB - We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.
AU - Swoboda, Paul
AU - Kuske, Jan
AU - Savchynskyy, Bogdan
ID - 917
SN - 978-153860457-1
TI - A dual ascent framework for Lagrangean decomposition of combinatorial problems
VL - 2017
ER -
TY - JOUR
AB - An electro-optomechanical device capable of microwave-to-optics conversion has recently been demonstrated, with the vision of enabling optical networks of superconducting qubits. Here we present an improved converter design that uses a three-dimensional microwave cavity for coupling between the microwave transmission line and an integrated LC resonator on the converter chip. The new design simplifies the optical assembly and decouples it from the microwave part of the setup. Experimental demonstrations show that the modular device assembly allows us to flexibly tune the microwave coupling to the converter chip while maintaining small loss. We also find that electromechanical experiments are not impacted by the additional microwave cavity. Our design is compatible with a high-finesse optical cavity and will improve optical performance.
AU - Menke, Tim
AU - Burns, Peter
AU - Higginbotham, Andrew P
AU - Kampel, N S
AU - Peterson, Robert
AU - Cicak, Katarina
AU - Simmonds, Raymond
AU - Regal, Cindy
AU - Lehnert, Konrad
ID - 93
IS - 9
JF - Review of Scientific Instruments
TI - Reconfigurable re-entrant cavity for wireless coupling to an electro-optomechanical device
VL - 88
ER -
TY - THES
AB - The thesis encompasses several topics of plant cell biology which were studied in the model plant Arabidopsis thaliana. Chapter 1 concerns the plant hormone auxin and its polar transport through cells and tissues. The highly controlled, directional transport of auxin is facilitated by plasma membrane-localized transporters. Transporters from the PIN family direct auxin transport due to their polarized localizations at cell membranes. Substantial effort has been put into research on cellular trafficking of PIN proteins, which is thought to underlie their polar distribution. I participated in a forward genetic screen aimed at identifying novel regulators of PIN polarity. The screen yielded several genes which may be involved in PIN polarity regulation or participate in polar auxin transport by other means. Chapter 2 focuses on the endomembrane system, with particular attention to clathrin-mediated endocytosis. The project started with identification of several proteins that interact with clathrin light chains. Among them, I focused on two putative homologues of auxilin, which in non-plant systems is an endocytotic factor known for uncoating clathrin-coated vesicles in the final step of endocytosis. The body of my work consisted of an in-depth characterization of transgenic A. thaliana lines overexpressing these putative auxilins in an inducible manner. Overexpression of these proteins leads to an inhibition of endocytosis, as documented by imaging of cargoes and clathrin-related endocytic machinery. An extension of this work is an investigation into a concept of homeostatic regulation acting between distinct transport processes in the endomembrane system. With auxilin overexpressing lines, where endocytosis is blocked specifically, I made observations on the mutual relationship between two opposite trafficking processes of secretion and endocytosis. In Chapter 3, I analyze cortical microtubule arrays and their relationship to auxin signaling and polarized growth in elongating cells. In plants, microtubules are organized into arrays just below the plasma membrane, and it is thought that their function is to guide membrane-docked cellulose synthase complexes. These, in turn, influence cell wall structure and cell shape by directed deposition of cellulose fibres. In elongating cells, cortical microtubule arrays are able to reorient in relation to long cell axis, and these reorientations have been linked to cell growth and to signaling of growth-regulating factors such as auxin or light. In this chapter, I am addressing the causal relationship between microtubule array reorientation, growth, and auxin signaling. I arrive at a model where array reorientation is not guided by auxin directly, but instead is only controlled by growth, which, in turn, is regulated by auxin.
AU - Adamowski, Maciek
ID - 938
TI - Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana
ER -
TY - JOUR
AB - We reveal the existence of continuous families of guided single-mode solitons in planar waveguides with weakly nonlinear active core and absorbing boundaries. Stable propagation of TE and TM-polarized solitons is accompanied by attenuation of all other modes, i.e., the waveguide features properties of conservative and dissipative systems. If the linear spectrum of the waveguide possesses exceptional points, which occurs in the case of TM polarization, an originally focusing (defocusing) material nonlinearity may become effectively defocusing (focusing). This occurs due to the geometric phase of the carried eigenmode when the surface impedance encircles the exceptional point. In its turn, the change of the effective nonlinearity ensures the existence of dark (bright) solitons in spite of focusing (defocusing) Kerr nonlinearity of the core. The existence of an exceptional point can also result in anomalous enhancement of the effective nonlinearity. In terms of practical applications, the nonlinearity of the reported waveguide can be manipulated by controlling the properties of the absorbing cladding.
AU - Midya, Bikashkali
AU - Konotop, Vladimir
ID - 939
IS - 3
JF - Physical Review Letters
SN - 00319007
TI - Waveguides with absorbing boundaries: Nonlinearity controlled by an exceptional point and solitons
VL - 119
ER -
TY - JOUR
AB - We introduce a method for breaking Lorentz reciprocity based upon the noncommutation of frequency conversion and delay. The method requires no magnetic materials or resonant physics, allowing for the design of scalable and broadband nonreciprocal circuits. With this approach, two types of gyrators - universal building blocks for linear, nonreciprocal circuits - are constructed. Using one of these gyrators, we create a circulator with >15 dB of isolation across the 5-9 GHz band. Our designs may be readily extended to any platform with suitable frequency conversion elements, including semiconducting devices for telecommunication or an on-chip superconducting implementation for quantum information processing.
AU - Rosenthal, Eric
AU - Chapman, Benjamin
AU - Higginbotham, Andrew P
AU - Kerckhoff, Joseph
AU - Lehnert, Konrad
ID - 94
IS - 14
JF - APS Physics, Physical Review Letters
TI - Breaking Lorentz reciprocity with frequency conversion and delay
VL - 119
ER -
TY - JOUR
AB - Like many developing tissues, the vertebrate neural tube is patterned by antiparallel morphogen gradients. To understand how these inputs are interpreted, we measured morphogen signaling and target gene expression in mouse embryos and chick ex vivo assays. From these data, we derived and validated a characteristic decoding map that relates morphogen input to the positional identity of neural progenitors. Analysis of the observed responses indicates that the underlying interpretation strategy minimizes patterning errors in response to the joint input of noisy opposing gradients. We reverse-engineered a transcriptional network that provides a mechanistic basis for the observed cell fate decisions and accounts for the precision and dynamics of pattern formation. Together, our data link opposing gradient dynamics in a growing tissue to precise pattern formation.
AU - Zagórski, Marcin P
AU - Tabata, Yoji
AU - Brandenberg, Nathalie
AU - Lutolf, Matthias
AU - Tkacik, Gasper
AU - Bollenbach, Tobias
AU - Briscoe, James
AU - Kicheva, Anna
ID - 943
IS - 6345
JF - Science
SN - 00368075
TI - Decoding of position in the developing neural tube from antiparallel morphogen gradients
VL - 356
ER -
TY - JOUR
AB - While chromosome-wide dosage compensation of the X chromosome has been found in many species, studies in ZW clades have indicated that compensation of the Z is more localized and/or incomplete. In the ZW Lepidoptera, some species show complete compensation of the Z chromosome, while others lack full equalization, but what drives these inconsistencies is unclear. Here, we compare patterns of male and female gene expression on the Z chromosome of two closely related butterfly species, Papilio xuthus and Papilio machaon, and in multiple tissues of two moths species, Plodia interpunctella and Bombyx mori, which were previously found to differ in the extent to which they equalize Z-linked gene expression between the sexes. We find that, while some species and tissues seem to have incomplete dosage compensation, this is in fact due to the accumulation of male-biased genes and the depletion of female-biased genes on the Z chromosome. Once this is accounted for, the Z chromosome is fully compensated in all four species, through the up-regulation of Z expression in females and in some cases additional down-regulation in males. We further find that both sex-biased genes and Z-linked genes have increased rates of expression divergence in this clade, and that this can lead to fast shifts in patterns of gene expression even between closely related species. Taken together, these results show that the uneven distribution of sex-biased genes on sex chromosomes can confound conclusions about dosage compensation and that Z chromosome-wide dosage compensation is not only possible but ubiquitous among Lepidoptera.
AU - Huylmans, Ann K
AU - Macon, Ariana
AU - Vicoso, Beatriz
ID - 945
IS - 10
JF - Molecular Biology and Evolution
SN - 07374038
TI - Global dosage compensation is ubiquitous in Lepidoptera, but counteracted by the masculinization of the Z chromosome
VL - 34
ER -
TY - JOUR
AB - Roots navigate through soil integrating environmental signals to orient their growth. The Arabidopsis root is a widely used model for developmental, physiological and cell biological studies. Live imaging greatly aids these efforts, but the horizontal sample position and continuous root tip displacement present significant difficulties. Here, we develop a confocal microscope setup for vertical sample mounting and integrated directional illumination. We present TipTracker – a custom software for automatic tracking of diverse moving objects usable on various microscope setups. Combined, this enables observation of root tips growing along the natural gravity vector over prolonged periods of time, as well as the ability to induce rapid gravity or light stimulation. We also track migrating cells in the developing zebrafish embryo, demonstrating the utility of this system in the acquisition of high-resolution data sets of dynamic samples. We provide detailed descriptions of the tools enabling the easy implementation on other microscopes.
AU - Von Wangenheim, Daniel
AU - Hauschild, Robert
AU - Fendrych, Matyas
AU - Barone, Vanessa
AU - Benková, Eva
AU - Friml, Jirí
ID - 946
JF - eLife
TI - Live tracking of moving samples in confocal microscopy for vertically grown roots
VL - 6
ER -
TY - JOUR
AB - Viewing the ways a living cell can organize its metabolism as the phase space of a physical system, regulation can be seen as the ability to reduce the entropy of that space by selecting specific cellular configurations that are, in some sense, optimal. Here we quantify the amount of regulation required to control a cell's growth rate by a maximum-entropy approach to the space of underlying metabolic phenotypes, where a configuration corresponds to a metabolic flux pattern as described by genome-scale models. We link the mean growth rate achieved by a population of cells to the minimal amount of metabolic regulation needed to achieve it through a phase diagram that highlights how growth suppression can be as costly (in regulatory terms) as growth enhancement. Moreover, we provide an interpretation of the inverse temperature β controlling maximum-entropy distributions based on the underlying growth dynamics. Specifically, we show that the asymptotic value of β for a cell population can be expected to depend on (i) the carrying capacity of the environment, (ii) the initial size of the colony, and (iii) the probability distribution from which the inoculum was sampled. Results obtained for E. coli and human cells are found to be remarkably consistent with empirical evidence.
AU - De Martino, Daniele
AU - Capuani, Fabrizio
AU - De Martino, Andrea
ID - 947
IS - 1
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
SN - 24700045
TI - Quantifying the entropic cost of cellular growth control
VL - 96
ER -
TY - CONF
AB - Two-player games on graphs are widely studied in formal methods as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. Both players have separate budgets, which sum up to $1$. In each turn, a bidding takes place. Both players submit bids simultaneously, and a bid is legal if it does not exceed the available budget. The winner of the bidding pays his bid to the other player and moves the token. For reachability objectives, repeated bidding games have been studied and are called Richman games. There, a central question is the existence and computation of threshold budgets; namely, a value t\in [0,1] such that if\PO's budget exceeds $t$, he can win the game, and if\PT's budget exceeds 1-t, he can win the game. We focus on parity games and mean-payoff games. We show the existence of threshold budgets in these games, and reduce the problem of finding them to Richman games. We also determine the strategy-complexity of an optimal strategy. Our most interesting result shows that memoryless strategies suffice for mean-payoff bidding games.
AU - Avni, Guy
AU - Henzinger, Thomas A
AU - Chonev, Ventsislav K
ID - 950
SN - 1868-8969
TI - Infinite-duration bidding games
VL - 85
ER -