TY - JOUR
AB - We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.
AU - Achlioptas, Dimitris
AU - Iliopoulos, Fotis
AU - Kolmogorov, Vladimir
ID - 7412
IS - 5
JF - SIAM Journal on Computing
SN - 0097-5397
TI - A local lemma for focused stochastical algorithms
VL - 48
ER -
TY - JOUR
AB - We consider Bose gases consisting of N particles trapped in a box with volume one and interacting through a repulsive potential with scattering length of order N−1 (Gross–Pitaevskii regime). We determine the ground state energy and the low-energy excitation spectrum, up to errors vanishing as N→∞. Our results confirm Bogoliubov’s predictions.
AU - Boccato, Chiara
AU - Brennecke, Christian
AU - Cenatiempo, Serena
AU - Schlein, Benjamin
ID - 7413
IS - 2
JF - Acta Mathematica
SN - 0001-5962
TI - Bogoliubov theory in the Gross–Pitaevskii limit
VL - 222
ER -
TY - JOUR
AU - Knaus, Lisa
AU - Tarlungeanu, Dora-Clara
AU - Novarino, Gaia
ID - 7414
IS - Supplement 6
JF - European Neuropsychopharmacology
SN - 0924-977X
TI - S.16.03 A homozygous missense mutation in SLC7A5 leads to autism spectrum disorder and microcephaly
VL - 29
ER -
TY - JOUR
AU - Morandell, Jasmin
AU - Nicolas, Armel
AU - Schwarz, Lena A
AU - Novarino, Gaia
ID - 7415
IS - Supplement 6
JF - European Neuropsychopharmacology
SN - 0924-977X
TI - S.16.05 Illuminating the role of the e3 ubiquitin ligase cullin3 in brain development and autism
VL - 29
ER -
TY - JOUR
AB - Multiple importance sampling (MIS) has become an indispensable tool in Monte Carlo rendering, widely accepted as a near-optimal solution for combining different sampling techniques. But an MIS combination, using the common balance or power heuristics, often results in an overly defensive estimator, leading to high variance. We show that by generalizing the MIS framework, variance can be substantially reduced. Specifically, we optimize one of the combined sampling techniques so as to decrease the overall variance of the resulting MIS estimator. We apply the approach to the computation of direct illumination due to an HDR environment map and to the computation of global illumination using a path guiding algorithm. The implementation can be as simple as subtracting a constant value from the tabulated sampling density done entirely in a preprocessing step. This produces a consistent noise reduction in all our tests with no negative influence on run time, no artifacts or bias, and no failure cases.
AU - Karlík, Ondřej
AU - Šik, Martin
AU - Vévoda, Petr
AU - Skrivan, Tomas
AU - Křivánek, Jaroslav
ID - 7418
IS - 6
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - MIS compensation: Optimizing sampling techniques in multiple importance sampling
VL - 38
ER -
TY - JOUR
AB - β1-integrins mediate cell–matrix interactions and their trafficking is important in the dynamic regulation of cell adhesion, migration and malignant processes, including cancer cell invasion. Here, we employ an RNAi screen to characterize regulators of integrin traffic and identify the association of Golgi-localized gamma ear-containing Arf-binding protein 2 (GGA2) with β1-integrin, and its role in recycling of active but not inactive β1-integrin receptors. Silencing of GGA2 limits active β1-integrin levels in focal adhesions and decreases cancer cell migration and invasion, which is in agreement with its ability to regulate the dynamics of active integrins. By using the proximity-dependent biotin identification (BioID) method, we identified two RAB family small GTPases, i.e. RAB13 and RAB10, as novel interactors of GGA2. Functionally, RAB13 silencing triggers the intracellular accumulation of active β1-integrin, and reduces integrin activity in focal adhesions and cell migration similarly to GGA2 depletion, indicating that both facilitate active β1-integrin recycling to the plasma membrane. Thus, GGA2 and RAB13 are important specificity determinants for integrin activity-dependent traffic.
AU - Sahgal, Pranshu
AU - Alanko, Jonna H
AU - Icha, Jaroslav
AU - Paatero, Ilkka
AU - Hamidi, Hellyeh
AU - Arjonen, Antti
AU - Pietilä, Mika
AU - Rokka, Anne
AU - Ivaska, Johanna
ID - 7420
IS - 11
JF - Journal of Cell Science
SN - 0021-9533
TI - GGA2 and RAB13 promote activity-dependent β1-integrin recycling
VL - 132
ER -
TY - JOUR
AB - X and Y chromosomes can diverge when rearrangements block recombination between them. Here we present the first genomic view of a reciprocal translocation that causes two physically unconnected pairs of chromosomes to be coinherited as sex chromosomes. In a population of the common frog (Rana temporaria), both pairs of X and Y chromosomes show extensive sequence differentiation, but not degeneration of the Y chromosomes. A new method based on gene trees shows both chromosomes are sex‐linked. Furthermore, the gene trees from the two Y chromosomes have identical topologies, showing they have been coinherited since the reciprocal translocation occurred. Reciprocal translocations can thus reshape sex linkage on a much greater scale compared with inversions, the type of rearrangement that is much better known in sex chromosome evolution, and they can greatly amplify the power of sexually antagonistic selection to drive genomic rearrangement. Two more populations show evidence of other rearrangements, suggesting that this species has unprecedented structural polymorphism in its sex chromosomes.
AU - Toups, Melissa A
AU - Rodrigues, Nicolas
AU - Perrin, Nicolas
AU - Kirkpatrick, Mark
ID - 7421
IS - 8
JF - Molecular Ecology
SN - 0962-1083
TI - A reciprocal translocation radically reshapes sex‐linked inheritance in the common frog
VL - 28
ER -
TY - JOUR
AB - Biochemical reactions often occur at low copy numbers but at once in crowded and diverse environments. Space and stochasticity therefore play an essential role in biochemical networks. Spatial-stochastic simulations have become a prominent tool for understanding how stochasticity at the microscopic level influences the macroscopic behavior of such systems. While particle-based models guarantee the level of detail necessary to accurately describe the microscopic dynamics at very low copy numbers, the algorithms used to simulate them typically imply trade-offs between computational efficiency and biochemical accuracy. eGFRD (enhanced Green’s Function Reaction Dynamics) is an exact algorithm that evades such trade-offs by partitioning the N-particle system into M ≤ N analytically tractable one- and two-particle systems; the analytical solutions (Green’s functions) then are used to implement an event-driven particle-based scheme that allows particles to make large jumps in time and space while retaining access to their state variables at arbitrary simulation times. Here we present “eGFRD2,” a new eGFRD version that implements the principle of eGFRD in all dimensions, thus enabling efficient particle-based simulation of biochemical reaction-diffusion processes in the 3D cytoplasm, on 2D planes representing membranes, and on 1D elongated cylinders representative of, e.g., cytoskeletal tracks or DNA; in 1D, it also incorporates convective motion used to model active transport. We find that, for low particle densities, eGFRD2 is up to 6 orders of magnitude faster than conventional Brownian dynamics. We exemplify the capabilities of eGFRD2 by simulating an idealized model of Pom1 gradient formation, which involves 3D diffusion, active transport on microtubules, and autophosphorylation on the membrane, confirming recent experimental and theoretical results on this system to hold under genuinely stochastic conditions.
AU - Sokolowski, Thomas R
AU - Paijmans, Joris
AU - Bossen, Laurens
AU - Miedema, Thomas
AU - Wehrens, Martijn
AU - Becker, Nils B.
AU - Kaizu, Kazunari
AU - Takahashi, Koichi
AU - Dogterom, Marileen
AU - ten Wolde, Pieter Rein
ID - 7422
IS - 5
JF - The Journal of Chemical Physics
SN - 0021-9606
TI - eGFRD in all dimensions
VL - 150
ER -
TY - JOUR
AB - We compare finite rank perturbations of the following three ensembles of complex rectangular random matrices: First, a generalised Wishart ensemble with one random and two fixed correlation matrices introduced by Borodin and Péché, second, the product of two independent random matrices where one has correlated entries, and third, the case when the two random matrices become also coupled through a fixed matrix. The singular value statistics of all three ensembles is shown to be determinantal and we derive double contour integral representations for their respective kernels. Three different kernels are found in the limit of infinite matrix dimension at the origin of the spectrum. They depend on finite rank perturbations of the correlation and coupling matrices and are shown to be integrable. The first kernel (I) is found for two independent matrices from the second, and two weakly coupled matrices from the third ensemble. It generalises the Meijer G-kernel for two independent and uncorrelated matrices. The third kernel (III) is obtained for the generalised Wishart ensemble and for two strongly coupled matrices. It further generalises the perturbed Bessel kernel of Desrosiers and Forrester. Finally, kernel (II), found for the ensemble of two coupled matrices, provides an interpolation between the kernels (I) and (III), generalising previous findings of part of the authors.
AU - Akemann, Gernot
AU - Checinski, Tomasz
AU - Liu, Dangzheng
AU - Strahov, Eugene
ID - 7423
IS - 1
JF - Annales de l'Institut Henri Poincaré, Probabilités et Statistiques
SN - 0246-0203
TI - Finite rank perturbations in products of coupled random matrices: From one correlated to two Wishart ensembles
VL - 55
ER -
TY - JOUR
AB - For an ordinary K3 surface over an algebraically closed field of positive characteristic we show that every automorphism lifts to characteristic zero. Moreover, we show that the Fourier-Mukai partners of an ordinary K3 surface are in one-to-one correspondence with the Fourier-Mukai partners of the geometric generic fiber of its canonical lift. We also prove that the explicit counting formula for Fourier-Mukai partners of the K3 surfaces with Picard rank two and with discriminant equal to minus of a prime number, in terms of the class number of the prime, holds over a field of positive characteristic as well. We show that the image of the derived autoequivalence group of a K3 surface of finite height in the group of isometries of its crystalline cohomology has index at least two. Moreover, we provide a conditional upper bound on the kernel of this natural cohomological descent map. Further, we give an extended remark in the appendix on the possibility of an F-crystal structure on the crystalline cohomology of a K3 surface over an algebraically closed field of positive characteristic and show that the naive F-crystal structure fails in being compatible with inner product.
AU - Srivastava, Tanya K
ID - 7436
JF - Documenta Mathematica
SN - 14310635
TI - On derived equivalences of k3 surfaces in positive characteristic
VL - 24
ER -
TY - CONF
AB - Most of today's distributed machine learning systems assume reliable networks: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: Can we design machine learning systems that are tolerant to network unreliability during training? With this motivation, we focus on a theoretical problem of independent interest-given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability p of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of parameter servers. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable.
AU - Yu, Chen
AU - Tang, Hanlin
AU - Renggli, Cedric
AU - Kassing, Simon
AU - Singla, Ankit
AU - Alistarh, Dan-Adrian
AU - Zhang, Ce
AU - Liu, Ji
ID - 7437
SN - 9781510886988
T2 - 36th International Conference on Machine Learning, ICML 2019
TI - Distributed learning over unreliable networks
VL - 2019-June
ER -
TY - JOUR
AB - We prove that the observable telegraph signal accompanying the bistability in the photon-blockade-breakdown regime of the driven and lossy Jaynes–Cummings model is the finite-size precursor of what in the thermodynamic limit is a genuine first-order phase transition. We construct a finite-size scaling of the system parameters to a well-defined thermodynamic limit, in which the system remains the same microscopic system, but the telegraph signal becomes macroscopic both in its timescale and intensity. The existence of such a finite-size scaling completes and justifies the classification of the photon-blockade-breakdown effect as a first-order dissipative quantum phase transition.
AU - Vukics, A.
AU - Dombi, A.
AU - Fink, Johannes M
AU - Domokos, P.
ID - 7451
JF - Quantum
SN - 2521-327X
TI - Finite-size scaling of the photon-blockade breakdown dissipative quantum phase transition
VL - 3
ER -
TY - JOUR
AB - We report the fabrication of BaTiO3-Ni magnetoelectric nanocomposites comprising of BaTiO3 nanotubes surrounded by Ni matrix. BaTiO3 nanotubes obtained from the hydrothermal transformation of TiO2 have both inner and outer surfaces, which facilitates greater magnetoelectric coupling with the surrounding Ni matrix. The magnetoelectric coupling was studied by measuring the piezoelectric behavior in the presence of an in-plane direct magnetic field. A higher magnetoelectric voltage coefficient of 110 mV/cm·Oe was obtained, because of better coupling between Ni and BaTiO3 through the walls of the nanotubes. Such nanocomposite developed directly on Ti substrate may lead to efficient fabrication of magnetoelectric devices.
AU - Vadla, Samba Siva
AU - Costanzo, Tommaso
AU - John, Subish
AU - Caruntu, Gabriel
AU - Roy, Somnath C.
ID - 7459
JF - Scripta Materialia
SN - 1359-6462
TI - Local probing of magnetoelectric coupling in BaTiO3-Ni 1–3 composites
VL - 159
ER -
TY - CONF
AB - We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the original energy minimization problem using a multi plane block-coordinate Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean decomposition. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label discrete tomography and graph matching problems.
AU - Swoboda, Paul
AU - Kolmogorov, Vladimir
ID - 7468
SN - 10636919
T2 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
TI - Map inference via block-coordinate Frank-Wolfe algorithm
VL - 2019-June
ER -
TY - JOUR
AB - The sebaceous gland (SG) is an essential component of the skin, and SG dysfunction is debilitating1,2. Yet, the cellular bases for its origin, development and subsequent maintenance remain poorly understood. Here, we apply large-scale quantitative fate mapping to define the patterns of cell fate behaviour during SG development and maintenance. We show that the SG develops from a defined number of lineage-restricted progenitors that undergo a programme of independent and stochastic cell fate decisions. Following an expansion phase, equipotent progenitors transition into a phase of homeostatic turnover, which is correlated with changes in the mechanical properties of the stroma and spatial restrictions on gland size. Expression of the oncogene KrasG12D results in a release from these constraints and unbridled gland expansion. Quantitative clonal fate analysis reveals that, during this phase, the primary effect of the Kras oncogene is to drive a constant fate bias with little effect on cell division rates. These findings provide insight into the developmental programme of the SG, as well as the mechanisms that drive tumour progression and gland dysfunction.
AU - Andersen, Marianne Stemann
AU - Hannezo, Edouard B
AU - Ulyanchenko, Svetlana
AU - Estrach, Soline
AU - Antoku, Yasuko
AU - Pisano, Sabrina
AU - Boonekamp, Kim E.
AU - Sendrup, Sarah
AU - Maimets, Martti
AU - Pedersen, Marianne Terndrup
AU - Johansen, Jens V.
AU - Clement, Ditte L.
AU - Feral, Chloe C.
AU - Simons, Benjamin D.
AU - Jensen, Kim B.
ID - 7476
IS - 8
JF - Nature Cell Biology
SN - 1465-7392
TI - Tracing the cellular dynamics of sebaceous gland development in normal and perturbed states
VL - 21
ER -
TY - CONF
AB - Multi-exit architectures, in which a stack of processing layers is interleaved with early output layers, allow the processing of a test example to stop early and thus save computation time and/or energy. In this work, we propose a new training procedure for multi-exit architectures based on the principle of knowledge distillation. The method encourage searly exits to mimic later, more accurate exits, by matching their output probabilities.
Experiments on CIFAR100 and ImageNet show that distillation-based training significantly improves the accuracy of early exits while maintaining state-of-the-art accuracy for late ones. The method is particularly beneficial when training data is limited and it allows a straightforward extension to semi-supervised learning,i.e. making use of unlabeled data at training time. Moreover, it takes only afew lines to implement and incurs almost no computational overhead at training time, and none at all at test time.
AU - Bui Thi Mai, Phuong
AU - Lampert, Christoph
ID - 7479
SN - 15505499
T2 - IEEE International Conference on Computer Vision
TI - Distillation-based training for multi-exit architectures
VL - 2019-October
ER -
TY - CHAP
AB - Social insects (i.e., ants, termites and the social bees and wasps) protect their colonies from disease using a combination of individual immunity and collectively performed defenses, termed social immunity. The first line of social immune defense is sanitary care, which is performed by colony members to protect their pathogen-exposed nestmates from developing an infection. If sanitary care fails and an infection becomes established, a second line of social immune defense is deployed to stop disease transmission within the colony and to protect the valuable queens, which together with the males are the reproductive individuals of the colony. Insect colonies are separated into these reproductive individuals and the sterile worker force, forming a superorganismal reproductive unit reminiscent of the differentiated germline and soma in a multicellular organism. Ultimately, the social immune response preserves the germline of the superorganism insect colony and increases overall fitness of the colony in case of disease.
AU - Cremer, Sylvia
AU - Kutzer, Megan
ED - Choe, Jae
ID - 7513
SN - 9780128132517
T2 - Encyclopedia of Animal Behavior
TI - Social immunity
ER -
TY - GEN
AB - We prove a lower bound for the free energy (per unit volume) of the two-dimensional Bose gas in the thermodynamic limit. We show that the free energy at density $\rho$ and inverse temperature $\beta$ differs from the one of the non-interacting system by the correction term $4 \pi \rho^2 |\ln a^2 \rho|^{-1} (2 - [1 - \beta_{\mathrm{c}}/\beta]_+^2)$. Here $a$ is the scattering length of the interaction potential, $[\cdot]_+ = \max\{ 0, \cdot \}$ and $\beta_{\mathrm{c}}$ is the inverse Berezinskii--Kosterlitz--Thouless critical temperature for superfluidity. The result is valid in the dilute limit
$a^2\rho \ll 1$ and if $\beta \rho \gtrsim 1$.
AU - Deuchert, Andreas
AU - Mayer, Simon
AU - Seiringer, Robert
ID - 7524
T2 - arXiv:1910.03372
TI - The free energy of the two-dimensional dilute Bose gas. I. Lower bound
ER -
TY - JOUR
AB - The BH3-only family of proteins is key for initiating apoptosis in a variety of contexts, and may also contribute to non-apoptotic cellular processes. Historically, the nematode Caenorhabditis elegans has provided a powerful system for studying and identifying conserved regulators of BH3-only proteins. In C. elegans, the BH3-only protein egl-1 is expressed during development to cell-autonomously trigger most developmental cell deaths. Here we provide evidence that egl-1 is also transcribed after development in the sensory neuron pair URX without inducing apoptosis. We used genetic screening and epistasis analysis to determine that its transcription is regulated in URX by neuronal activity and/or in parallel by orthologs of Protein Kinase G and the Salt-Inducible Kinase family. Because several BH3-only family proteins are also expressed in the adult nervous system of mammals, we suggest that studying egl-1 expression in URX may shed light on mechanisms that regulate conserved family members in higher organisms.
AU - Cohn, Jesse
AU - Dwivedi, Vivek
AU - Valperga, Giulio
AU - Zarate, Nicole
AU - de Bono, Mario
AU - Horvitz, H. Robert
AU - Pierce, Jonathan T.
ID - 7547
IS - 11
JF - G3: Genes, Genomes, Genetics
SN - 2160-1836
TI - Activity-dependent regulation of the proapoptotic BH3-only gene egl-1 in a living neuron pair in Caenorhabditis elegans
VL - 9
ER -
TY - JOUR
AB - Although the aggregation of the amyloid-β peptide (Aβ) into amyloid fibrils is a well-established hallmark of Alzheimer’s disease, the complex mechanisms linking this process to neurodegeneration are still incompletely understood. The nematode worm C. elegans is a valuable model organism through which to study these mechanisms because of its simple nervous system and its relatively short lifespan. Standard Aβ-based C. elegans models of Alzheimer’s disease are designed to study the toxic effects of the overexpression of Aβ in the muscle or nervous systems. However, the wide variety of effects associated with the tissue-level overexpression of Aβ makes it difficult to single out and study specific cellular mechanisms related to the onset of Alzheimer’s disease. Here, to better understand how to investigate the early events affecting neuronal signalling, we created a C. elegans model expressing Aβ42, the 42-residue form of Aβ, from a single-copy gene insertion in just one pair of glutamatergic sensory neurons, the BAG neurons. In behavioural assays, we found that the Aβ42-expressing animals displayed a subtle modulation of the response to CO2, compared to controls. Ca2+ imaging revealed that the BAG neurons in young Aβ42-expressing nematodes were activated more strongly than in control animals, and that neuronal activation remained intact until old age. Taken together, our results suggest that Aβ42-expression in this very subtle model of AD is sufficient to modulate the behavioural response but not strong enough to generate significant neurotoxicity, suggesting that slightly more aggressive perturbations will enable effectively studies of the links between the modulation of a physiological response and its associated neurotoxicity.
AU - Sinnige, Tessa
AU - Ciryam, Prashanth
AU - Casford, Samuel
AU - Dobson, Christopher M.
AU - de Bono, Mario
AU - Vendruscolo, Michele
ID - 7548
IS - 5
JF - PLOS ONE
SN - 1932-6203
TI - Expression of the amyloid-β peptide in a single pair of C. elegans sensory neurons modulates the associated behavioural response
VL - 14
ER -