0 there exists a large subset of a ∈ F×p such that for kl a,1,p : x → e((ax+x) / p) we have M(kla,1,p) ≥ (1−ε/√2π + o(1)) log log p, as p→∞. Finally, we prove a result on the growth of the moments of {M (kla,1,p)}a∈F×p. 2020 Mathematics Subject Classification: 11L03, 11T23 (Primary); 14F20, 60F10 (Secondary).
AU - Bonolis, Dante
ID - 9364
JF - Mathematical Proceedings of the Cambridge Philosophical Society
SN - 03050041
TI - On the size of the maximum of incomplete Kloosterman sums
ER -
TY - JOUR
AB - Shigella are pathogens originating within the Escherichia lineage but frequently classified as a separate genus. Shigella genomes contain numerous insertion sequences (ISs) that lead to pseudogenisation of affected genes and an increase of non-homologous recombination. Here, we study 414 genomes of E. coli and Shigella strains to assess the contribution of genomic rearrangements to Shigella evolution. We found that Shigella experienced exceptionally high rates of intragenomic rearrangements and had a decreased rate of homologous recombination compared to pathogenic and non-pathogenic E. coli. The high rearrangement rate resulted in independent disruption of syntenic regions and parallel rearrangements in different Shigella lineages. Specifically, we identified two types of chromosomally encoded E3 ubiquitin-protein ligases acquired independently by all Shigella strains that also showed a high level of sequence conservation in the promoter and further in the 5′-intergenic region. In the only available enteroinvasive E. coli (EIEC) strain, which is a pathogenic E. coli with a phenotype intermediate between Shigella and non-pathogenic E. coli, we found a rate of genome rearrangements comparable to those in other E. coli and no functional copies of the two Shigella-specific E3 ubiquitin ligases. These data indicate that the accumulation of ISs influenced many aspects of genome evolution and played an important role in the evolution of intracellular pathogens. Our research demonstrates the power of comparative genomics-based on synteny block composition and an important role of non-coding regions in the evolution of genomic islands.
AU - Seferbekova, Zaira
AU - Zabelkin, Alexey
AU - Yakovleva, Yulia
AU - Afasizhev, Robert
AU - Dranenko, Natalia O.
AU - Alexeev, Nikita
AU - Gelfand, Mikhail S.
AU - Bochkareva, Olga
ID - 9380
JF - Frontiers in Microbiology
TI - High rates of genome rearrangements and pathogenicity of Shigella spp.
VL - 12
ER -
TY - JOUR
AB - A game of rock-paper-scissors is an interesting example of an interaction where none of the pure strategies strictly dominates all others, leading to a cyclic pattern. In this work, we consider an unstable version of rock-paper-scissors dynamics and allow individuals to make behavioural mistakes during the strategy execution. We show that such an assumption can break a cyclic relationship leading to a stable equilibrium emerging with only one strategy surviving. We consider two cases: completely random mistakes when individuals have no bias towards any strategy and a general form of mistakes. Then, we determine conditions for a strategy to dominate all other strategies. However, given that individuals who adopt a dominating strategy are still prone to behavioural mistakes in the observed behaviour, we may still observe extinct strategies. That is, behavioural mistakes in strategy execution stabilise evolutionary dynamics leading to an evolutionary stable and, potentially, mixed co-existence equilibrium.
AU - Kleshnina, Maria
AU - Streipert, Sabrina S.
AU - Filar, Jerzy A.
AU - Chatterjee, Krishnendu
ID - 9381
IS - 4
JF - PLoS Computational Biology
SN - 1553734X
TI - Mistakes can stabilise the dynamics of rock-paper-scissors games
VL - 17
ER -
TY - JOUR
AB - A primary roadblock to our understanding of speciation is that it usually occurs over a timeframe that is too long to study from start to finish. The idea of a speciation continuum provides something of a solution to this problem; rather than observing the entire process, we can simply reconstruct it from the multitude of speciation events that surround us. But what do we really mean when we talk about the speciation continuum, and can it really help us understand speciation? We explored these questions using a literature review and online survey of speciation researchers. Although most researchers were familiar with the concept and thought it was useful, our survey revealed extensive disagreement about what the speciation continuum actually tells us. This is due partly to the lack of a clear definition. Here, we provide an explicit definition that is compatible with the Biological Species Concept. That is, the speciation continuum is a continuum of reproductive isolation. After outlining the logic of the definition in light of alternatives, we explain why attempts to reconstruct the speciation process from present‐day populations will ultimately fail. We then outline how we think the speciation continuum concept can continue to act as a foundation for understanding the continuum of reproductive isolation that surrounds us.
AU - Stankowski, Sean
AU - Ravinet, Mark
ID - 9383
JF - Evolution
SN - 00143820
TI - Defining the speciation continuum
ER -
TY - JOUR
AU - Bolger-Munro, Madison
AU - Choi, Kate
AU - Cheung, Faith
AU - Liu, Yi Tian
AU - Dang-Lawson, May
AU - Deretic, Nikola
AU - Keane, Connor
AU - Gold, Michael R.
ID - 9379
JF - Frontiers in Cell and Developmental Biology
KW - B cell
KW - actin
KW - immune synapse
KW - cell spreading
KW - cofilin
KW - WDR1 (AIP1)
KW - LIM domain kinase
KW - B cell receptor (BCR)
TI - The Wdr1-LIMK-Cofilin axis controls B cell antigen receptor-induced actin remodeling and signaling at the immune synapse
VL - 9
ER -
TY - JOUR
AB - We report the complete analysis of a deterministic model of deleterious mutations and negative selection against them at two haploid loci without recombination. As long as mutation is a weaker force than selection, mutant alleles remain rare at the only stable equilibrium, and otherwise, a variety of dynamics are possible. If the mutation-free genotype is absent, generally the only stable equilibrium is the one that corresponds to fixation of the mutant allele at the locus where it is less deleterious. This result suggests that fixation of a deleterious allele that follows a click of the Muller’s ratchet is governed by natural selection, instead of random drift.
AU - Khudiakova, Kseniia
AU - Neretina, Tatiana Yu.
AU - Kondrashov, Alexey S.
ID - 9387
JF - Journal of Theoretical Biology
KW - General Biochemistry
KW - Genetics and Molecular Biology
KW - Modelling and Simulation
KW - Statistics and Probability
KW - General Immunology and Microbiology
KW - Applied Mathematics
KW - General Agricultural and Biological Sciences
KW - General Medicine
SN - 0022-5193
TI - Two linked loci under mutation-selection balance and Muller’s ratchet
VL - 524
ER -
TY - JOUR
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff, the ratio, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with bounded treewidth—a class that contains the control flow graphs of most programs. Let n denote the number of nodes of a graph, m the number of edges (for bounded treewidth 𝑚=𝑂(𝑛)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for the minimum initial credit problem we show that (1) for general graphs the problem can be solved in 𝑂(𝑛2⋅𝑚) time and the associated decision problem in 𝑂(𝑛⋅𝑚) time, improving the previous known 𝑂(𝑛3⋅𝑚⋅log(𝑛⋅𝑊)) and 𝑂(𝑛2⋅𝑚) bounds, respectively; and (2) for bounded treewidth graphs we present an algorithm that requires 𝑂(𝑛⋅log𝑛) time. Second, for bounded treewidth graphs we present an algorithm that approximates the mean-payoff value within a factor of 1+𝜖 in time 𝑂(𝑛⋅log(𝑛/𝜖)) as compared to the classical exact algorithms on general graphs that require quadratic time. Third, for the ratio property we present an algorithm that for bounded treewidth graphs works in time 𝑂(𝑛⋅log(|𝑎⋅𝑏|))=𝑂(𝑛⋅log(𝑛⋅𝑊)), when the output is 𝑎𝑏, as compared to the previously best known algorithm on general graphs with running time 𝑂(𝑛2⋅log(𝑛⋅𝑊)). We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 9393
JF - Formal Methods in System Design
SN - 09259856
TI - Faster algorithms for quantitative verification in bounded treewidth graphs
ER -
TY - JOUR
AB - Chromosomal inversions have long been recognized for their role in local adaptation. By suppressing recombination in heterozygous individuals, they can maintain coadapted gene complexes and protect them from homogenizing effects of gene flow. However, to fully understand their importance for local adaptation we need to know their influence on phenotypes under divergent selection. For this, the marine snail Littorina saxatilis provides an ideal study system. Divergent ecotypes adapted to wave action and crab predation occur in close proximity on intertidal shores with gene flow between them. Here, we used F2 individuals obtained from crosses between the ecotypes to test for associations between genomic regions and traits distinguishing the Crab‐/Wave‐adapted ecotypes including size, shape, shell thickness, and behavior. We show that most of these traits are influenced by two previously detected inversion regions that are divergent between ecotypes. We thus gain a better understanding of one important underlying mechanism responsible for the rapid and repeated formation of ecotypes: divergent selection acting on inversions. We also found that some inversions contributed to more than one trait suggesting that they may contain several loci involved in adaptation, consistent with the hypothesis that suppression of recombination within inversions facilitates differentiation in the presence of gene flow.
AU - Koch, Eva L.
AU - Morales, Hernán E.
AU - Larsson, Jenny
AU - Westram, Anja M
AU - Faria, Rui
AU - Lemmon, Alan R.
AU - Lemmon, E. Moriarty
AU - Johannesson, Kerstin
AU - Butlin, Roger K.
ID - 9394
JF - Evolution Letters
TI - Genetic variation for adaptive traits is associated with polymorphic inversions in Littorina saxatilis
ER -
TY - DATA
AB - This .zip File contains the transport data for "Non-topological zero bias peaks in full-shell nanowires induced by flux tunable Andreev states" by M. Valentini, et. al.
The measurements were done using Labber Software and the data is stored in the hdf5 file format.
Instructions of how to read the data are in "Notebook_Valentini.pdf".
AU - Valentini, Marco
ID - 9389
TI - Research data for "Non-topological zero bias peaks in full-shell nanowires induced by flux tunable Andreev states"
ER -
TY - JOUR
AU - Stankowski, Sean
AU - Ravinet, Mark
ID - 9392
IS - 9
JF - Current Biology
SN - 09609822
TI - Quantifying the use of species concepts
VL - 31
ER -
TY - JOUR
AB - Direct and indirect reciprocity are key mechanisms for the evolution of cooperation. Direct reciprocity means that individuals use their own experience to decide whether to cooperate with another person. Indirect reciprocity means that they also consider the experiences of others. Although these two mechanisms are intertwined, they are typically studied in isolation. Here, we introduce a mathematical framework that allows us to explore both kinds of reciprocity simultaneously. We show that the well-known ‘generous tit-for-tat’ strategy of direct reciprocity has a natural analogue in indirect reciprocity, which we call ‘generous scoring’. Using an equilibrium analysis, we characterize under which conditions either of the two strategies can maintain cooperation. With simulations, we additionally explore which kind of reciprocity evolves when members of a population engage in social learning to adapt to their environment. Our results draw unexpected connections between direct and indirect reciprocity while highlighting important differences regarding their evolvability.
AU - Schmid, Laura
AU - Chatterjee, Krishnendu
AU - Hilbe, Christian
AU - Nowak, Martin A.
ID - 9402
JF - Nature Human Behaviour
TI - A unified framework of direct and indirect reciprocity
ER -
TY - CHAP
AB - Optimal decision making requires individuals to know their available options and to anticipate correctly what consequences these options have. In many social interactions, however, we refrain from gathering all relevant information, even if this information would help us make better decisions and is costless to obtain. This chapter examines several examples of “deliberate ignorance.” Two simple models are proposed to illustrate how ignorance can evolve among self-interested and payoff - maximizing individuals, and open problems are highlighted that lie ahead for future research to explore.
AU - Schmid, Laura
AU - Hilbe, Christian
ED - Hertwig, Ralph
ED - Engel, Christoph
ID - 9403
SN - 978-0-262-04559-9
T2 - Deliberate Ignorance: Choosing Not To Know
TI - The evolution of strategic ignorance in strategic interaction
VL - 29
ER -
TY - JOUR
AB - We extend our recent result [22] on the central limit theorem for the linear eigenvalue statistics of non-Hermitian matrices X with independent, identically distributed complex entries to the real symmetry class. We find that the expectation and variance substantially differ from their complex counterparts, reflecting (i) the special spectral symmetry of real matrices onto the real axis; and (ii) the fact that real i.i.d. matrices have many real eigenvalues. Our result generalizes the previously known special cases where either the test function is analytic [49] or the first four moments of the matrix elements match the real Gaussian [59, 44]. The key element of the proof is the analysis of several weakly dependent Dyson Brownian motions (DBMs). The conceptual novelty of the real case compared with [22] is that the correlation structure of the stochastic differentials in each individual DBM is non-trivial, potentially even jeopardising its well-posedness.
AU - Cipolloni, Giorgio
AU - Erdös, László
AU - Schröder, Dominik J
ID - 9412
JF - Electronic Journal of Probability
TI - Fluctuation around the circular law for random matrices with real entries
VL - 26
ER -
TY - JOUR
AB - The dynamics of a triangular magnetocapillary swimmer is studied using the lattice Boltzmann method. We extend on our previous work, which deals with the self-assembly and a specific type of the swimmer motion characterized by the swimmer’s maximum velocity centred around the particle’s inverse viscous time. Here, we identify additional regimes of motion. First, modifying the ratio of surface tension and magnetic forces allows to study the swimmer propagation in the regime of significantly lower frequencies mainly defined by the strength of the magnetocapillary potential. Second, introducing a constant magnetic contribution in each of the particles in addition to their magnetic moment induced by external fields leads to another regime characterized by strong in-plane swimmer reorientations that resemble experimental observations.
AU - Sukhov, Alexander
AU - Hubert, Maxime
AU - Grosjean, Galien M
AU - Trosman, Oleg
AU - Ziegler, Sebastian
AU - Collard, Ylona
AU - Vandewalle, Nicolas
AU - Smith, Ana Sunčana
AU - Harting, Jens
ID - 9411
IS - 4
JF - European Physical Journal E
SN - 12928941
TI - Regimes of motion of magnetocapillary swimmers
VL - 44
ER -
TY - JOUR
AB - Microtubule plus-end depolymerization rate is a potentially important target of physiological regulation, but it has been challenging to measure, so its role in spatial organization is poorly understood. Here we apply a method for tracking plus ends based on time difference imaging to measure depolymerization rates in large interphase asters growing in Xenopus egg extract. We observed strong spatial regulation of depolymerization rates, which were higher in the aster interior compared with the periphery, and much less regulation of polymerization or catastrophe rates. We interpret these data in terms of a limiting component model, where aster growth results in lower levels of soluble tubulin and microtubule-associated proteins (MAPs) in the interior cytosol compared with that at the periphery. The steady-state polymer fraction of tubulin was ∼30%, so tubulin is not strongly depleted in the aster interior. We propose that the limiting component for microtubule assembly is a MAP that inhibits depolymerization, and that egg asters are tuned to low microtubule density.
AU - Ishihara, Keisuke
AU - Decker, Franziska
AU - Dos Santos Caldas, Paulo R
AU - Pelletier, James F.
AU - Loose, Martin
AU - Brugués, Jan
AU - Mitchison, Timothy J.
ID - 9414
IS - 9
JF - Molecular Biology of the Cell
SN - 10591524
TI - Spatial variation of microtubule depolymerization in large asters
VL - 32
ER -
TY - JOUR
AB - We present a computational design system that assists users to model, optimize, and fabricate quad-robots with soft skins. Our system addresses the challenging task of predicting their physical behavior by fully integrating the multibody dynamics of the mechanical skeleton and the elastic behavior of the soft skin. The developed motion control strategy uses an alternating optimization scheme to avoid expensive full space time-optimization, interleaving space-time optimization for the skeleton, and frame-by-frame optimization for the full dynamics. The output are motor torques to drive the robot to achieve a user prescribed motion trajectory. We also provide a collection of convenient engineering tools and empirical manufacturing guidance to support the fabrication of the designed quad-robot. We validate the feasibility of designs generated with our system through physics simulations and with a physically-fabricated prototype.
AU - Feng, Xudong
AU - Liu, Jiafeng
AU - Wang, Huamin
AU - Yang, Yin
AU - Bao, Hujun
AU - Bickel, Bernd
AU - Xu, Weiwei
ID - 9408
IS - 6
JF - IEEE Transactions on Visualization and Computer Graphics
SN - 19410506
TI - Computational design of skinned Quad-Robots
VL - 27
ER -
TY - JOUR
AB - Antibiotic concentrations vary dramatically in the body and the environment. Hence, understanding the dynamics of resistance evolution along antibiotic concentration gradients is critical for predicting and slowing the emergence and spread of resistance. While it has been shown that increasing the concentration of an antibiotic slows resistance evolution, how adaptation to one antibiotic concentration correlates with fitness at other points along the gradient has not received much attention. Here, we selected populations of Escherichia coli at several points along a concentration gradient for three different antibiotics, asking how rapidly resistance evolved and whether populations became specialized to the antibiotic concentration they were selected on. Populations selected at higher concentrations evolved resistance more slowly but exhibited equal or higher fitness across the whole gradient. Populations selected at lower concentrations evolved resistance rapidly, but overall fitness in the presence of antibiotics was lower. However, these populations readily adapted to higher concentrations upon subsequent selection. Our results indicate that resistance management strategies must account not only for the rates of resistance evolution but also for the fitness of evolved strains.
AU - Lagator, Mato
AU - Uecker, Hildegard
AU - Neve, Paul
ID - 9410
IS - 5
JF - Biology letters
TI - Adaptation at different points along antibiotic concentration gradients
VL - 17
ER -
TY - JOUR
AB - This paper presents a method for designing planar multistable compliant structures. Given a sequence of desired stable states and the corresponding poses of the structure, we identify the topology and geometric realization of a mechanism—consisting of bars and joints—that is able to physically reproduce the desired multistable behavior. In order to solve this problem efficiently, we build on insights from minimally rigid graph theory to identify simple but effective topologies for the mechanism. We then optimize its geometric parameters, such as joint positions and bar lengths, to obtain correct transitions between the given poses. Simultaneously, we ensure adequate stability of each pose based on an effective approximate error metric related to the elastic energy Hessian of the bars in the mechanism. As demonstrated by our results, we obtain functional multistable mechanisms of manageable complexity that can be fabricated using 3D printing. Further, we evaluated the effectiveness of our method on a large number of examples in the simulation and fabricated several physical prototypes.
AU - Zhang, Ran
AU - Auzinger, Thomas
AU - Bickel, Bernd
ID - 9376
JF - ACM Transactions on Graphics
KW - multistability
KW - mechanism
KW - computational design
KW - rigidity
TI - Computational design of planar multistable compliant structures
ER -
TY - JOUR
AB - We derive rigorously the leading order of the correlation energy of a Fermi gas in a scaling regime of high density and weak interaction. The result verifies the prediction of the random-phase approximation. Our proof refines the method of collective bosonization in three dimensions. We approximately diagonalize an effective Hamiltonian describing approximately bosonic collective excitations around the Hartree–Fock state, while showing that gapless and non-collective excitations have only a negligible effect on the ground state energy.
AU - Benedikter, Niels P
AU - Nam, Phan Thành
AU - Porta, Marcello
AU - Schlein, Benjamin
AU - Seiringer, Robert
ID - 7901
JF - Inventiones Mathematicae
SN - 00209910
TI - Correlation energy of a weakly interacting Fermi gas
ER -
TY - JOUR
AB - The ability to adapt to changes in stimulus statistics is a hallmark of sensory systems. Here, we developed a theoretical framework that can account for the dynamics of adaptation from an information processing perspective. We use this framework to optimize and analyze adaptive sensory codes, and we show that codes optimized for stationary environments can suffer from prolonged periods of poor performance when the environment changes. To mitigate the adversarial effects of these environmental changes, sensory systems must navigate tradeoffs between the ability to accurately encode incoming stimuli and the ability to rapidly detect and adapt to changes in the distribution of these stimuli. We derive families of codes that balance these objectives, and we demonstrate their close match to experimentally observed neural dynamics during mean and variance adaptation. Our results provide a unifying perspective on adaptation across a range of sensory systems, environments, and sensory tasks.
AU - Mlynarski, Wiktor F
AU - Hermundstad, Ann M.
ID - 9439
JF - Nature Neuroscience
SN - 10976256
TI - Efficient and adaptive sensory codes
ER -
TY - GEN
AB - For any given positive integer l, we prove that every plane deformation of a circlewhich preserves the 1/2and 1/ (2l + 1) -rational caustics is trivial i.e. the deformationconsists only of similarities (rescalings and isometries).
AU - Kaloshin, Vadim
AU - Koudjinan, Edmond
ID - 9435
TI - Non co-preservation of the 1/2 and 1/(2l+1)-rational caustics along deformations of circles
ER -
TY - JOUR
AB - Embryo morphogenesis is impacted by dynamic changes in tissue material properties, which have been proposed to occur via processes akin to phase transitions (PTs). Here, we show that rigidity percolation provides a simple and robust theoretical framework to predict material/structural PTs of embryonic tissues from local cell connectivity. By using percolation theory, combined with directly monitoring dynamic changes in tissue rheology and cell contact mechanics, we demonstrate that the zebrafish blastoderm undergoes a genuine rigidity PT, brought about by a small reduction in adhesion-dependent cell connectivity below a critical value. We quantitatively predict and experimentally verify hallmarks of PTs, including power-law exponents and associated discontinuities of macroscopic observables. Finally, we show that this uniform PT depends on blastoderm cells undergoing meta-synchronous divisions causing random and, consequently, uniform changes in cell connectivity. Collectively, our theoretical and experimental findings reveal the structural basis of material PTs in an organismal context.
AU - Petridou, Nicoletta
AU - Corominas-Murtra, Bernat
AU - Heisenberg, Carl-Philipp J
AU - Hannezo, Edouard B
ID - 9316
IS - 7
JF - Cell
SN - 00928674
TI - Rigidity percolation uncovers a structural basis for embryonic tissue phase transitions
VL - 184
ER -
TY - JOUR
AB - The inverse problem of designing component interactions to target emergent structure is fundamental to numerous applications in biotechnology, materials science, and statistical physics. Equally important is the inverse problem of designing emergent kinetics, but this has received considerably less attention. Using recent advances in automatic differentiation, we show how kinetic pathways can be precisely designed by directly differentiating through statistical physics models, namely free energy calculations and molecular dynamics simulations. We consider two systems that are crucial to our understanding of structural self-assembly: bulk crystallization and small nanoclusters. In each case, we are able to assemble precise dynamical features. Using gradient information, we manipulate interactions among constituent particles to tune the rate at which these systems yield specific structures of interest. Moreover, we use this approach to learn nontrivial features about the high-dimensional design space, allowing us to accurately predict when multiple kinetic features can be simultaneously and independently controlled. These results provide a concrete and generalizable foundation for studying nonstructural self-assembly, including kinetic properties as well as other complex emergent properties, in a vast array of systems.
AU - Goodrich, Carl Peter
AU - King, Ella M.
AU - Schoenholz, Samuel S.
AU - Cubuk, Ekin D.
AU - Brenner, Michael P.
ID - 9257
IS - 10
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - Designing self-assembling kinetics with differentiable statistical physics models
VL - 118
ER -
TY - JOUR
AB - Electrodepositing insulating lithium peroxide (Li2O2) is the key process during discharge of aprotic Li–O2 batteries and determines rate, capacity, and reversibility. Current understanding states that the partition between surface adsorbed and dissolved lithium superoxide governs whether Li2O2 grows as a conformal surface film or larger particles, leading to low or high capacities, respectively. However, better understanding governing factors for Li2O2 packing density and capacity requires structural sensitive in situ metrologies. Here, we establish in situ small- and wide-angle X-ray scattering (SAXS/WAXS) as a suitable method to record the Li2O2 phase evolution with atomic to submicrometer resolution during cycling a custom-built in situ Li–O2 cell. Combined with sophisticated data analysis, SAXS allows retrieving rich quantitative structural information from complex multiphase systems. Surprisingly, we find that features are absent that would point at a Li2O2 surface film formed via two consecutive electron transfers, even in poorly solvating electrolytes thought to be prototypical for surface growth. All scattering data can be modeled by stacks of thin Li2O2 platelets potentially forming large toroidal particles. Li2O2 solution growth is further justified by rotating ring-disk electrode measurements and electron microscopy. Higher discharge overpotentials lead to smaller Li2O2 particles, but there is no transition to an electronically passivating, conformal Li2O2 coating. Hence, mass transport of reactive species rather than electronic transport through a Li2O2 film limits the discharge capacity. Provided that species mobilities and carbon surface areas are high, this allows for high discharge capacities even in weakly solvating electrolytes. The currently accepted Li–O2 reaction mechanism ought to be reconsidered.
AU - Prehal, Christian
AU - Samojlov, Aleksej
AU - Nachtnebel, Manfred
AU - Lovicar, Ludek
AU - Kriechbaum, Manfred
AU - Amenitsch, Heinz
AU - Freunberger, Stefan Alexander
ID - 9301
IS - 14
JF - Proceedings of the National Academy of Sciences
KW - small-angle X-ray scattering
KW - oxygen reduction
KW - disproportionation
KW - Li-air battery
SN - 0027-8424
TI - In situ small-angle X-ray scattering reveals solution phase discharge of Li–O2 batteries with weakly solvating electrolytes
VL - 118
ER -
TY - JOUR
AB - Endoplasmic reticulum–plasma membrane contact sites (ER–PM CS) play fundamental roles in all eukaryotic cells. Arabidopsis thaliana mutants lacking the ER–PM protein tether synaptotagmin1 (SYT1) exhibit decreased PM integrity under multiple abiotic stresses, such as freezing, high salt, osmotic stress, and mechanical damage. Here, we show that, together with SYT1, the stress-induced SYT3 is an ER–PM tether that also functions in maintaining PM integrity. The ER–PM CS localization of SYT1 and SYT3 is dependent on PM phosphatidylinositol-4-phosphate and is regulated by abiotic stress. Lipidomic analysis revealed that cold stress increased the accumulation of diacylglycerol at the PM in a syt1/3 double mutant relative to wild-type while the levels of most glycerolipid species remain unchanged. In addition, the SYT1-green fluorescent protein fusion preferentially binds diacylglycerol in vivo with little affinity for polar glycerolipids. Our work uncovers a SYT-dependent mechanism of stress adaptation counteracting the detrimental accumulation of diacylglycerol at the PM produced during episodes of abiotic stress.
AU - Ruiz-Lopez, N
AU - Pérez-Sancho, J
AU - Esteban Del Valle, A
AU - Haslam, RP
AU - Vanneste, S
AU - Catalá, R
AU - Perea-Resa, C
AU - Van Damme, D
AU - García-Hernández, S
AU - Albert, A
AU - Vallarino, J
AU - Lin, J
AU - Friml, Jiří
AU - Macho, AP
AU - Salinas, J
AU - Rosado, A
AU - Napier, JA
AU - Amorim-Silva, V
AU - Botella, MA
ID - 9443
JF - Plant Cell
SN - 1040-4651
TI - Synaptotagmins at the endoplasmic reticulum-plasma membrane contact sites maintain diacylglycerol homeostasis during abiotic stress
ER -
TY - JOUR
AB - Lithium bis(trifluoromethylsulfonyl)imide (LiTFSI) based water-in-salt electrolytes (WiSEs) has recently emerged as a new promising class of electrolytes, primarily owing to their wide electrochemical stability windows (~3–4 V), that by far exceed the thermodynamic stability window of water (1.23 V). Upon increasing the salt concentration towards superconcentration the onset of the oxygen evolution reaction (OER) shifts more significantly than the hydrogen evolution reaction (HER) does. The OER shift has been explained by the accumulation of hydrophobic anions blocking water access to the electrode surface, hence by double layer theory. Here we demonstrate that the processes during oxidation are much more complex, involving OER, carbon and salt decomposition by OER intermediates, and salt precipitation upon local oversaturation. The positive shift in the onset potential of oxidation currents was elucidated by combining several advanced analysis techniques: rotating ring-disk electrode voltammetry, online electrochemical mass spectrometry, and X-ray photoelectron spectroscopy, using both dilute and superconcentrated electrolytes. The results demonstrate the importance of reactive OER intermediates and surface films for electrolyte and electrode stability and motivate further studies of the nature of the electrode.
AU - Maffre, Marion
AU - Bouchal, Roza
AU - Freunberger, Stefan Alexander
AU - Lindahl, Niklas
AU - Johansson, Patrik
AU - Favier, Frédéric
AU - Fontaine, Olivier
AU - Bélanger, Daniel
ID - 9447
IS - 5
JF - Journal of The Electrochemical Society
KW - Renewable Energy
KW - Sustainability and the Environment
KW - Electrochemistry
KW - Materials Chemistry
KW - Electronic
KW - Optical and Magnetic Materials
KW - Surfaces
KW - Coatings and Films
KW - Condensed Matter Physics
SN - 0013-4651
TI - Investigation of electrochemical and chemical processes occurring at positive potentials in “Water-in-Salt” electrolytes
VL - 168
ER -
TY - JOUR
AB - Given a locally finite set 𝑋⊆ℝ𝑑 and an integer 𝑘≥0, we consider the function 𝐰𝑘:Del𝑘(𝑋)→ℝ on the dual of the order-k Voronoi tessellation, whose sublevel sets generalize the notion of alpha shapes from order-1 to order-k (Edelsbrunner et al. in IEEE Trans Inf Theory IT-29:551–559, 1983; Krasnoshchekov and Polishchuk in Inf Process Lett 114:76–83, 2014). While this function is not necessarily generalized discrete Morse, in the sense of Forman (Adv Math 134:90–145, 1998) and Freij (Discrete Math 309:3821–3829, 2009), we prove that it satisfies similar properties so that its increments can be meaningfully classified into critical and non-critical steps. This result extends to the case of weighted points and sheds light on k-fold covers with balls in Euclidean space.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
AU - Osang, Georg F
ID - 9465
IS - 1
JF - Journal of Geometry
SN - 00472468
TI - A step in the Delaunay mosaic of order k
VL - 112
ER -
TY - CONF
AB - We firstly introduce the self-assembled growth of highly uniform Ge quantum wires with controllable position, distance and length on patterned Si (001) substrates. We then present the electrically tunable strong spin-orbit coupling, the first Ge hole spin qubit and ultrafast operation of hole spin qubit in the Ge/Si quantum wires.
AU - Gao, Fei
AU - Zhang, Jie Yin
AU - Wang, Jian Huan
AU - Ming, Ming
AU - Wang, Tina
AU - Zhang, Jian Jun
AU - Watzinger, Hannes
AU - Kukucka, Josip
AU - Vukušić, Lada
AU - Katsaros, Georgios
AU - Wang, Ke
AU - Xu, Gang
AU - Li, Hai Ou
AU - Guo, Guo Ping
ID - 9464
SN - 9781728181769
T2 - 2021 5th IEEE Electron Devices Technology and Manufacturing Conference, EDTM 2021
TI - Ge/Si quantum wires for quantum computing
ER -
TY - JOUR
AB - In this paper, we consider reflected three-operator splitting methods for monotone inclusion problems in real Hilbert spaces. To do this, we first obtain weak convergence analysis and nonasymptotic O(1/n) convergence rate of the reflected Krasnosel'skiĭ-Mann iteration for finding a fixed point of nonexpansive mapping in real Hilbert spaces under some seemingly easy to implement conditions on the iterative parameters. We then apply our results to three-operator splitting for the monotone inclusion problem and consequently obtain the corresponding convergence analysis. Furthermore, we derive reflected primal-dual algorithms for highly structured monotone inclusion problems. Some numerical implementations are drawn from splitting methods to support the theoretical analysis.
AU - Iyiola, Olaniyi S.
AU - Enyi, Cyril D.
AU - Shehu, Yekini
ID - 9469
JF - Optimization Methods and Software
SN - 10556788
TI - Reflected three-operator splitting method for monotone inclusion problem
ER -
TY - JOUR
AB - A key step in understanding the genetic basis of different evolutionary outcomes (e.g., adaptation) is to determine the roles played by different mutation types (e.g., SNPs, translocations and inversions). To do this we must simultaneously consider different mutation types in an evolutionary framework. Here, we propose a research framework that directly utilizes the most important characteristics of mutations, their population genetic effects, to determine their relative evolutionary significance in a given scenario. We review known population genetic effects of different mutation types and show how these may be connected to different evolutionary outcomes. We provide examples of how to implement this framework and pinpoint areas where more data, theory and synthesis are needed. Linking experimental and theoretical approaches to examine different mutation types simultaneously is a critical step towards understanding their evolutionary significance.
AU - Berdan, Emma L.
AU - Blanckaert, Alexandre
AU - Slotte, Tanja
AU - Suh, Alexander
AU - Westram, Anja M
AU - Fragata, Inês
ID - 9470
IS - 12
JF - Molecular Ecology
SN - 09621083
TI - Unboxing mutations: Connecting mutation types with evolutionary consequences
VL - 30
ER -
TY - JOUR
AB - Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical” drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no three on a great circle---and the edges of $G$ are shortest-arcs in $\mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $\gamma_e$ such that the only vertices in $\gamma_e$ are the ends of $e$; (2) if $e\ne f$, then $\gamma_e\cap\gamma_f$ has precisely two crossings; and (3) if $e\ne f$, then $e$ intersects $\gamma_f$ at most once, in either a crossing or an end of $e$. We use properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with “precisely two crossings” in (2) replaced by “at most two crossings.” The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.
AU - Arroyo Guevara, Alan M
AU - Richter, R. Bruce
AU - Sunohara, Matthew
ID - 9468
IS - 2
JF - SIAM Journal on Discrete Mathematics
SN - 08954801
TI - Extending drawings of complete graphs into arrangements of pseudocircles
VL - 35
ER -
TY - JOUR
AB - Brain neurons arise from relatively few progenitors generating an enormous diversity of neuronal types. Nonetheless, a cardinal feature of mammalian brain neurogenesis is thought to be that excitatory and inhibitory neurons derive from separate, spatially segregated progenitors. Whether bi-potential progenitors with an intrinsic capacity to generate both lineages exist and how such a fate decision may be regulated are unknown. Using cerebellar development as a model, we discover that individual progenitors can give rise to both inhibitory and excitatory lineages. Gradations of Notch activity determine the fates of the progenitors and their daughters. Daughters with the highest levels of Notch activity retain the progenitor fate, while intermediate levels of Notch activity generate inhibitory neurons, and daughters with very low levels of Notch signaling adopt the excitatory fate. Therefore, Notch-mediated binary cell fate choice is a mechanism for regulating the ratio of excitatory to inhibitory neurons from common progenitors.
AU - Zhang, Tingting
AU - Liu, Tengyuan
AU - Mora, Natalia
AU - Guegan, Justine
AU - Bertrand, Mathilde
AU - Contreras, Ximena
AU - Hansen, Andi H
AU - Streicher, Carmen
AU - Anderle, Marica
AU - Danda, Natasha
AU - Tiberi, Luca
AU - Hippenmeyer, Simon
AU - Hassan, Bassem A.
ID - 8546
IS - 10
JF - Cell Reports
TI - Generation of excitatory and inhibitory neurons from common progenitors via Notch signaling in the cerebellum
VL - 35
ER -
TY - JOUR
AB - We prove that the energy of any eigenvector of a sum of several independent large Wigner matrices is equally distributed among these matrices with very high precision. This shows a particularly strong microcanonical form of the equipartition principle for quantum systems whose components are modelled by Wigner matrices.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 9550
JF - Forum of Mathematics, Sigma
TI - Equipartition principle for Wigner matrices
VL - 9
ER -
TY - JOUR
AB - We extend the notion of the minimal volume ellipsoid containing a convex body in Rd to the setting of logarithmically concave functions. We consider a vast class of logarithmically concave functions whose superlevel sets are concentric ellipsoids. For a fixed function from this class, we consider the set of all its “affine” positions. For any log-concave function f on Rd, we consider functions belonging to this set of “affine” positions, and find the one with the minimal integral under the condition that it is pointwise greater than or equal to f. We study the properties of existence and uniqueness of the solution to this problem. For any s∈[0,+∞), we consider the construction dual to the recently defined John s-function (Ivanov and Naszódi in Functional John ellipsoids. arXiv preprint: arXiv:2006.09934, 2020). We prove that such a construction determines a unique function and call it the Löwner s-function of f. We study the Löwner s-functions as s tends to zero and to infinity. Finally, extending the notion of the outer volume ratio, we define the outer integral ratio of a log-concave function and give an asymptotically tight bound on it.
AU - Ivanov, Grigory
AU - Tsiutsiurupa, Igor
ID - 9548
JF - Journal of Geometric Analysis
SN - 10506926
TI - Functional Löwner ellipsoids
ER -
TY - JOUR
AB - De novo loss of function mutations in the ubiquitin ligase-encoding gene Cullin3 lead to autism spectrum disorder (ASD). In mouse, constitutive haploinsufficiency leads to motor coordination deficits as well as ASD-relevant social and cognitive impairments. However, induction of Cul3 haploinsufficiency later in life does not lead to ASD-relevant behaviors, pointing to an important role of Cul3 during a critical developmental window. Here we show that Cul3 is essential to regulate neuronal migration and, therefore, constitutive Cul3 heterozygous mutant mice display cortical lamination abnormalities. At the molecular level, we found that Cul3 controls neuronal migration by tightly regulating the amount of Plastin3 (Pls3), a previously unrecognized player of neural migration. Furthermore, we found that Pls3 cell-autonomously regulates cell migration by regulating actin cytoskeleton organization, and its levels are inversely proportional to neural migration speed. Finally, we provide evidence that cellular phenotypes associated with autism-linked gene haploinsufficiency can be rescued by transcriptional activation of the intact allele in vitro, offering a proof of concept for a potential therapeutic approach for ASDs.
AU - Morandell, Jasmin
AU - Schwarz, Lena A
AU - Basilico, Bernadette
AU - Tasciyan, Saren
AU - Dimchev, Georgi A
AU - Nicolas, Armel
AU - Sommer, Christoph M
AU - Kreuzinger, Caroline
AU - Dotter, Christoph
AU - Knaus, Lisa
AU - Dobler, Zoe
AU - Cacci, Emanuele
AU - Schur, Florian KM
AU - Danzl, Johann G
AU - Novarino, Gaia
ID - 9429
IS - 1
JF - Nature Communications
KW - General Biochemistry
KW - Genetics and Molecular Biology
TI - Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development
VL - 12
ER -
TY - JOUR
AB - Inositol hexakisphosphate (IP6) is an assembly cofactor for HIV-1. We report here that IP6 is also used for assembly of Rous sarcoma virus (RSV), a retrovirus from a different genus. IP6 is ~100-fold more potent at promoting RSV mature capsid protein (CA) assembly than observed for HIV-1 and removal of IP6 in cells reduces infectivity by 100-fold. Here, visualized by cryo-electron tomography and subtomogram averaging, mature capsid-like particles show an IP6-like density in the CA hexamer, coordinated by rings of six lysines and six arginines. Phosphate and IP6 have opposing effects on CA in vitro assembly, inducing formation of T = 1 icosahedrons and tubes, respectively, implying that phosphate promotes pentamer and IP6 hexamer formation. Subtomogram averaging and classification optimized for analysis of pleomorphic retrovirus particles reveal that the heterogeneity of mature RSV CA polyhedrons results from an unexpected, intrinsic CA hexamer flexibility. In contrast, the CA pentamer forms rigid units organizing the local architecture. These different features of hexamers and pentamers determine the structural mechanism to form CA polyhedrons of variable shape in mature RSV particles.
AU - Obr, Martin
AU - Ricana, Clifton L.
AU - Nikulin, Nadia
AU - Feathers, Jon-Philip R.
AU - Klanschnig, Marco
AU - Thader, Andreas
AU - Johnson, Marc C.
AU - Vogt, Volker M.
AU - Schur, Florian KM
AU - Dick, Robert A.
ID - 9431
IS - 1
JF - Nature Communications
KW - General Biochemistry
KW - Genetics and Molecular Biology
KW - General Physics and Astronomy
KW - General Chemistry
TI - Structure of the mature Rous sarcoma virus lattice reveals a role for IP6 in the formation of the capsid hexamer
VL - 12
ER -
TY - JOUR
AB - The hexameric AAA-ATPase Drg1 is a key factor in eukaryotic ribosome biogenesis and initiates cytoplasmic maturation of the large ribosomal subunit by releasing the shuttling maturation factor Rlp24. Drg1 monomers contain two AAA-domains (D1 and D2) that act in a concerted manner. Rlp24 release is inhibited by the drug diazaborine which blocks ATP hydrolysis in D2. The mode of inhibition was unknown. Here we show the first cryo-EM structure of Drg1 revealing the inhibitory mechanism. Diazaborine forms a covalent bond to the 2′-OH of the nucleotide in D2, explaining its specificity for this site. As a consequence, the D2 domain is locked in a rigid, inactive state, stalling the whole Drg1 hexamer. Resistance mechanisms identified include abolished drug binding and altered positioning of the nucleotide. Our results suggest nucleotide-modifying compounds as potential novel inhibitors for AAA-ATPases.
AU - Prattes, Michael
AU - Grishkovskaya, Irina
AU - Hodirnau, Victor-Valentin
AU - Rössler, Ingrid
AU - Klein, Isabella
AU - Hetzmannseder, Christina
AU - Zisser, Gertrude
AU - Gruber, Christian C.
AU - Gruber, Karl
AU - Haselbach, David
AU - Bergler, Helmut
ID - 9540
IS - 1
JF - Nature Communications
KW - General Biochemistry
KW - Genetics and Molecular Biology
KW - General Physics and Astronomy
KW - General Chemistry
TI - Structural basis for inhibition of the AAA-ATPase Drg1 by diazaborine
VL - 12
ER -
TY - JOUR
AB - High impact epidemics constitute one of the largest threats humanity is facing in the 21st century. In the absence of pharmaceutical interventions, physical distancing together with testing, contact tracing and quarantining are crucial in slowing down epidemic dynamics. Yet, here we show that if testing capacities are limited, containment may fail dramatically because such combined countermeasures drastically change the rules of the epidemic transition: Instead of continuous, the response to countermeasures becomes discontinuous. Rather than following the conventional exponential growth, the outbreak that is initially strongly suppressed eventually accelerates and scales faster than exponential during an explosive growth period. As a consequence, containment measures either suffice to stop the outbreak at low total case numbers or fail catastrophically if marginally too weak, thus implying large uncertainties in reliably estimating overall epidemic dynamics, both during initial phases and during second wave scenarios.
AU - Scarselli, Davide
AU - Budanur, Nazmi B
AU - Timme, Marc
AU - Hof, Björn
ID - 9407
IS - 1
JF - Nature Communications
TI - Discontinuous epidemic transition due to limited testing
VL - 12
ER -
TY - JOUR
AB - AMPA receptors (AMPARs) mediate the majority of excitatory transmission in the brain and enable the synaptic plasticity that underlies learning1. A diverse array of AMPAR signalling complexes are established by receptor auxiliary subunits, which associate with the AMPAR in various combinations to modulate trafficking, gating and synaptic strength2. However, their mechanisms of action are poorly understood. Here we determine cryo-electron microscopy structures of the heteromeric GluA1–GluA2 receptor assembled with both TARP-γ8 and CNIH2, the predominant AMPAR complex in the forebrain, in both resting and active states. Two TARP-γ8 and two CNIH2 subunits insert at distinct sites beneath the ligand-binding domains of the receptor, with site-specific lipids shaping each interaction and affecting the gating regulation of the AMPARs. Activation of the receptor leads to asymmetry between GluA1 and GluA2 along the ion conduction path and an outward expansion of the channel triggers counter-rotations of both auxiliary subunit pairs, promoting the active-state conformation. In addition, both TARP-γ8 and CNIH2 pivot towards the pore exit upon activation, extending their reach for cytoplasmic receptor elements. CNIH2 achieves this through its uniquely extended M2 helix, which has transformed this endoplasmic reticulum-export factor into a powerful AMPAR modulator that is capable of providing hippocampal pyramidal neurons with their integrative synaptic properties.
AU - Zhang, Danyang
AU - Watson, Jake
AU - Matthews, Peter M.
AU - Cais, Ondrej
AU - Greger, Ingo H.
ID - 9549
JF - Nature
SN - 00280836
TI - Gating and modulation of a hetero-octameric AMPA glutamate receptor
ER -
TY - JOUR
AB - Thermalization is the inevitable fate of many complex quantum systems, whose dynamics allow them to fully explore the vast configuration space regardless of the initial state---the behaviour known as quantum ergodicity. In a quest for experimental realizations of coherent long-time dynamics, efforts have focused on ergodicity-breaking mechanisms, such as integrability and localization. The recent discovery of persistent revivals in quantum simulators based on Rydberg atoms have pointed to the existence of a new type of behaviour where the system rapidly relaxes for most initial conditions, while certain initial states give rise to non-ergodic dynamics. This collective effect has been named ”quantum many-body scarring’by analogy with a related form of weak ergodicity breaking that occurs for a single particle inside a stadium billiard potential. In this Review, we provide a pedagogical introduction to quantum many-body scars and highlight the emerging connections with the semiclassical quantization of many-body systems. We discuss the relation between scars and more general routes towards weak violations of ergodicity due to embedded algebras and non-thermal eigenstates, and highlight possible applications of scars in quantum technology.
AU - Serbyn, Maksym
AU - Abanin, Dmitry A.
AU - Papić, Zlatko
ID - 9428
IS - 6
JF - Nature Physics
TI - Quantum many-body scars and weak breaking of ergodicity
VL - 17
ER -
TY - JOUR
AB - We consider a system of N trapped bosons with repulsive interactions in a combined semiclassical mean-field limit at positive temperature. We show that the free energy is well approximated by the minimum of the Hartree free energy functional – a natural extension of the Hartree energy functional to positive temperatures. The Hartree free energy functional converges in the same limit to a semiclassical free energy functional, and we show that the system displays Bose–Einstein condensation if and only if it occurs in the semiclassical free energy functional. This allows us to show that for weak coupling the critical temperature decreases due to the repulsive interactions.
AU - Deuchert, Andreas
AU - Seiringer, Robert
ID - 9462
IS - 6
JF - Journal of Functional Analysis
SN - 00221236
TI - Semiclassical approximation and critical temperature shift for weakly interacting trapped bosons
VL - 281
ER -
TY - JOUR
AB - With the wider availability of full-color 3D printers, color-accurate 3D-print preparation has received increased attention. A key challenge lies in the inherent translucency of commonly used print materials that blurs out details of the color texture. Previous work tries to compensate for these scattering effects through strategic assignment of colored primary materials to printer voxels. To date, the highest-quality approach uses iterative optimization that relies on computationally expensive Monte Carlo light transport simulation to predict the surface appearance from subsurface scattering within a given print material distribution; that optimization, however, takes in the order of days on a single machine. In our work, we dramatically speed up the process by replacing the light transport simulation with a data-driven approach. Leveraging a deep neural network to predict the scattering within a highly heterogeneous medium, our method performs around two orders of magnitude faster than Monte Carlo rendering while yielding optimization results of similar quality level. The network is based on an established method from atmospheric cloud rendering, adapted to our domain and extended by a physically motivated weight sharing scheme that substantially reduces the network size. We analyze its performance in an end-to-end print preparation pipeline and compare quality and runtime to alternative approaches, and demonstrate its generalization to unseen geometry and material values. This for the first time enables full heterogenous material optimization for 3D-print preparation within time frames in the order of the actual printing time.
AU - Rittig, Tobias
AU - Sumin, Denis
AU - Babaei, Vahid
AU - Didyk, Piotr
AU - Voloboy, Alexey
AU - Wilkie, Alexander
AU - Bickel, Bernd
AU - Myszkowski, Karol
AU - Weyrich, Tim
AU - Křivánek, Jaroslav
ID - 9547
IS - 2
JF - Computer Graphics Forum
SN - 01677055
TI - Neural acceleration of scattering-aware color 3D printing
VL - 40
ER -
TY - JOUR
AB - The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17].
AU - Czumaj, Artur
AU - Davies, Peter
AU - Parter, Merav
ID - 9541
IS - 2
JF - ACM Transactions on Algorithms
SN - 1549-6325
TI - Graph sparsification for derandomizing massively parallel computation with low space
VL - 17
ER -
TY - JOUR
AB - We show that turbulent dynamics that arise in simulations of the three-dimensional Navier--Stokes equations in a triply-periodic domain under sinusoidal forcing can be described as transient visits to the neighborhoods of unstable time-periodic solutions. Based on this description, we reduce the original system with more than 10^5 degrees of freedom to a 17-node Markov chain where each node corresponds to the neighborhood of a periodic orbit. The model accurately reproduces long-term averages of the system's observables as weighted sums over the periodic orbits.
AU - Yalniz, Gökhan
AU - Hof, Björn
AU - Budanur, Nazmi B
ID - 9558
IS - 24
JF - Physical Review Letters
SN - 0031-9007
TI - Coarse graining the state space of a turbulent flow using periodic orbits
VL - 126
ER -
TY - JOUR
AB - We present conductance-matrix measurements in long, three-terminal hybrid superconductor-semiconductor nanowires, and compare with theoretical predictions of a magnetic-field-driven, topological quantum phase transition. By examining the nonlocal conductance, we identify the closure of the excitation gap in the bulk of the semiconductor before the emergence of zero-bias peaks, ruling out spurious gap-closure signatures from localized states. We observe that after the gap closes, nonlocal signals and zero-bias peaks fluctuate strongly at both ends, inconsistent with a simple picture of clean topological superconductivity.
AU - Puglia, Denise
AU - Martinez, E. A.
AU - Ménard, G. C.
AU - Pöschl, A.
AU - Gronin, S.
AU - Gardner, G. C.
AU - Kallaher, R.
AU - Manfra, M. J.
AU - Marcus, C. M.
AU - Higginbotham, Andrew P
AU - Casparis, L.
ID - 9570
IS - 23
JF - Physical Review B
SN - 24699950
TI - Closing of the induced gap in a hybrid superconductor-semiconductor nanowire
VL - 103
ER -
TY - JOUR
AB - While high risk of failure is an inherent part of developing innovative therapies, it can be reduced by adherence to evidence-based rigorous research practices. Numerous analyses conducted to date have clearly identified measures that need to be taken to improve research rigor. Supported through the European Union's Innovative Medicines Initiative, the EQIPD consortium has developed a novel preclinical research quality system that can be applied in both public and private sectors and is free for anyone to use. The EQIPD Quality System was designed to be suited to boost innovation by ensuring the generation of robust and reliable preclinical data while being lean, effective and not becoming a burden that could negatively impact the freedom to explore scientific questions. EQIPD defines research quality as the extent to which research data are fit for their intended use. Fitness, in this context, is defined by the stakeholders, who are the scientists directly involved in the research, but also their funders, sponsors, publishers, research tool manufacturers and collaboration partners such as peers in a multi-site research project. The essence of the EQIPD Quality System is the set of 18 core requirements that can be addressed flexibly, according to user-specific needs and following a user-defined trajectory. The EQIPD Quality System proposes guidance on expectations for quality-related measures, defines criteria for adequate processes (i.e., performance standards) and provides examples of how such measures can be developed and implemented. However, it does not prescribe any pre-determined solutions. EQIPD has also developed tools (for optional use) to support users in implementing the system and assessment services for those research units that successfully implement the quality system and seek formal accreditation. Building upon the feedback from users and continuous improvement, a sustainable EQIPD Quality System will ultimately serve the entire community of scientists conducting non-regulated preclinical research, by helping them generate reliable data that are fit for their intended use.
AU - Bespalov, Anton
AU - Bernard, René
AU - Gilis, Anja
AU - Gerlach, Björn
AU - Guillén, Javier
AU - Castagné, Vincent
AU - Lefevre, Isabel A.
AU - Ducrey, Fiona
AU - Monk, Lee
AU - Bongiovanni, Sandrine
AU - Altevogt, Bruce
AU - Arroyo-Araujo, María
AU - Bikovski, Lior
AU - De Bruin, Natasja
AU - Castaños-Vélez, Esmeralda
AU - Dityatev, Alexander
AU - Emmerich, Christoph H.
AU - Fares, Raafat
AU - Ferland-Beckham, Chantelle
AU - Froger-Colléaux, Christelle
AU - Gailus-Durner, Valerie
AU - Hölter, Sabine M.
AU - Hofmann, Martine Cj
AU - Kabitzke, Patricia
AU - Kas, Martien Jh
AU - Kurreck, Claudia
AU - Moser, Paul
AU - Pietraszek, Malgorzata
AU - Popik, Piotr
AU - Potschka, Heidrun
AU - Prado Montes De Oca, Ernesto
AU - Restivo, Leonardo
AU - Riedel, Gernot
AU - Ritskes-Hoitinga, Merel
AU - Samardzic, Janko
AU - Schunn, Michael
AU - Stöger, Claudia
AU - Voikar, Vootele
AU - Vollert, Jan
AU - Wever, Kimberley E.
AU - Wuyts, Kathleen
AU - Macleod, Malcolm R.
AU - Dirnagl, Ulrich
AU - Steckler, Thomas
ID - 9607
JF - eLife
TI - Introduction to the EQIPD quality system
VL - 10
ER -
TY - JOUR
AB - We report the synthesis and characterization of graphene functionalized with iron (Fe3+) oxide (G-Fe3O4) nanohybrids for radio-frequency magnetic hyperthermia application. We adopted the wet chemical procedure, using various contents of Fe3O4 (magnetite) from 0–100% for making two-dimensional graphene–Fe3O4 nanohybrids. The homogeneous dispersal of Fe3O4 nanoparticles decorated on the graphene surface combined with their biocompatibility and high thermal conductivity make them an excellent material for magnetic hyperthermia. The morphological and magnetic properties of the nanohybrids were studied using scanning electron microscopy (SEM) and a vibrating sample magnetometer (VSM), respectively. The smart magnetic platforms were exposed to an alternating current (AC) magnetic field of 633 kHz and of strength 9.1 mT for studying their hyperthermic performance. The localized antitumor effects were investigated with artificial neural network modeling. A neural net time-series model was developed for the assessment of the best nanohybrid composition to serve the purpose with an accuracy close to 100%. Six Nonlinear Autoregressive with External Input (NARX) models were obtained, one for each of the components. The assessment of the accuracy of the predicted results has been done on the basis of Mean Squared Error (MSE). The highest Mean Squared Error value was obtained for the nanohybrid containing 45% magnetite and 55% graphene (F45G55) in the training phase i.e., 0.44703, which is where the model achieved optimal results after 71 epochs. The F45G55 nanohybrid was found to be the best for hyperthermia applications in low dosage with the highest specific absorption rate (SAR) and mean squared error values.
AU - Dar, M. S.
AU - Akram, Khush Bakhat
AU - Sohail, Ayesha
AU - Arif, Fatima
AU - Zabihi, Fatemeh
AU - Yang, Shengyuan
AU - Munir, Shamsa
AU - Zhu, Meifang
AU - Abid, M.
AU - Nauman, Muhammad
ID - 9569
IS - 35
JF - RSC Advances
TI - Heat induction in two-dimensional graphene–Fe3O4 nanohybrids for magnetic hyperthermia applications with artificial neural network modeling
VL - 11
ER -
TY - JOUR
AB - Sound propagation is a macroscopic manifestation of the interplay between the equilibrium thermodynamics and the dynamical transport properties of fluids. Here, for a two-dimensional system of ultracold fermions, we calculate the first and second sound velocities across the whole BCS-BEC crossover, and we analyze the system response to an external perturbation. In the low-temperature regime we reproduce the recent measurements [Phys. Rev. Lett. 124, 240403 (2020)] of the first sound velocity, which, due to the decoupling of density and entropy fluctuations, is the sole mode excited by a density probe. Conversely, a heat perturbation excites only the second sound, which, being sensitive to the superfluid depletion, vanishes in the deep BCS regime and jumps discontinuously to zero at the Berezinskii-Kosterlitz-Thouless superfluid transition. A mixing between the modes occurs only in the finite-temperature BEC regime, where our theory converges to the purely bosonic results.
AU - Tononi, A.
AU - Cappellaro, Alberto
AU - Bighin, Giacomo
AU - Salasnich, L.
ID - 9606
IS - 6
JF - Physical Review A
SN - 24699926
TI - Propagation of first and second sound in a two-dimensional Fermi superfluid
VL - 103
ER -
TY - JOUR
AB - Mosaic analysis with double markers (MADM) offers one approach to visualize and concomitantly manipulate genetically defined cells in mice with single-cell resolution. MADM applications include the analysis of lineage, single-cell morphology and physiology, genomic imprinting phenotypes, and dissection of cell-autonomous gene functions in vivo in health and disease. Yet, MADM can only be applied to <25% of all mouse genes on select chromosomes to date. To overcome this limitation, we generate transgenic mice with knocked-in MADM cassettes near the centromeres of all 19 autosomes and validate their use across organs. With this resource, >96% of the entire mouse genome can now be subjected to single-cell genetic mosaic analysis. Beyond a proof of principle, we apply our MADM library to systematically trace sister chromatid segregation in distinct mitotic cell lineages. We find striking chromosome-specific biases in segregation patterns, reflecting a putative mechanism for the asymmetric segregation of genetic determinants in somatic stem cell division.
AU - Contreras, Ximena
AU - Amberg, Nicole
AU - Davaatseren, Amarbayasgalan
AU - Hansen, Andi H
AU - Sonntag, Johanna
AU - Andersen, Lill
AU - Bernthaler, Tina
AU - Streicher, Carmen
AU - Heger, Anna-Magdalena
AU - Johnson, Randy L.
AU - Schwarz, Lindsay A.
AU - Luo, Liqun
AU - Rülicke, Thomas
AU - Hippenmeyer, Simon
ID - 9603
IS - 12
JF - Cell Reports
TI - A genome-wide library of MADM mice for single-cell genetic mosaic analysis
VL - 35
ER -
TY - JOUR
AB - In mammalian genomes, differentially methylated regions (DMRs) and histone marks including trimethylation of histone 3 lysine 27 (H3K27me3) at imprinted genes are asymmetrically inherited to control parentally-biased gene expression. However, neither parent-of-origin-specific transcription nor imprints have been comprehensively mapped at the blastocyst stage of preimplantation development. Here, we address this by integrating transcriptomic and epigenomic approaches in mouse preimplantation embryos. We find that seventy-one genes exhibit previously unreported parent-of-origin-specific expression in blastocysts (nBiX: novel blastocyst-imprinted expressed). Uniparental expression of nBiX genes disappears soon after implantation. Micro-whole-genome bisulfite sequencing (µWGBS) of individual uniparental blastocysts detects 859 DMRs. We further find that 16% of nBiX genes are associated with a DMR, whereas most are associated with parentally-biased H3K27me3, suggesting a role for Polycomb-mediated imprinting in blastocysts. nBiX genes are clustered: five clusters contained at least one published imprinted gene, and five clusters exclusively contained nBiX genes. These data suggest that early development undergoes a complex program of stage-specific imprinting involving different tiers of regulation.
AU - Santini, Laura
AU - Halbritter, Florian
AU - Titz-Teixeira, Fabian
AU - Suzuki, Toru
AU - Asami, Maki
AU - Ma, Xiaoyan
AU - Ramesmayer, Julia
AU - Lackner, Andreas
AU - Warr, Nick
AU - Pauler, Florian
AU - Hippenmeyer, Simon
AU - Laue, Ernest
AU - Farlik, Matthias
AU - Bock, Christoph
AU - Beyer, Andreas
AU - Perry, Anthony C.F.
AU - Leeb, Martin
ID - 9601
IS - 1
JF - Nature Communications
TI - Genomic imprinting in mouse blastocysts is predominantly associated with H3K27me3
VL - 12
ER -
TY - JOUR
AB - An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer k, there exists a constant ck > 0 such that any ordered graph G on n vertices with the property that neither G nor its complement contains an induced monotone path of size k, has either a clique or an independent set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs.
A key idea of the above paper was to show that any unordered graph on n vertices that does not contain an induced path of size k, and whose maximum degree is at most c(k)n for some small c(k) > 0, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for k ≥ 3, by a construction of Fox. We provide some further examples showing that this statement also fails for ordered graphs avoiding other ordered trees.
AU - Pach, János
AU - Tomon, István
ID - 9602
JF - Journal of Combinatorial Theory. Series B
SN - 00958956
TI - Erdős-Hajnal-type results for monotone paths
VL - 151
ER -
TY - CONF
AB - Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation.
AU - Biswas, Ranita
AU - Cultrera di Montesano, Sebastiano
AU - Edelsbrunner, Herbert
AU - Saghafian, Morteza
ID - 9604
SN - 18688969
T2 - Leibniz International Proceedings in Informatics
TI - Counting cells of order-k voronoi tessellations in ℝ^{3} with morse theory
VL - 189
ER -
TY - JOUR
AB - Spin qubits are considered to be among the most promising candidates for building a quantum processor. Group IV hole spin qubits have moved into the focus of interest due to the ease of operation and compatibility with Si technology. In addition, Ge offers the option for monolithic superconductor-semiconductor integration. Here we demonstrate a hole spin qubit operating at fields below 10 mT, the critical field of Al, by exploiting the large out-of-plane hole g-factors in planar Ge and by encoding the qubit into the singlet-triplet states of a double quantum dot. We observe electrically controlled X and Z-rotations with tunable frequencies exceeding 100 MHz and dephasing times of 1μs which we extend beyond 15μs with echo techniques. These results show that Ge hole singlet triplet qubits outperform their electronic Si and GaAs based counterparts in speed and coherence, respectively. In addition, they are on par with Ge single spin qubits, but can be operated at much lower fields underlining their potential for on chip integration with superconducting technologies.
AU - Jirovec, Daniel
AU - Hofmann, Andrea C
AU - Ballabio, Andrea
AU - Mutter, Philipp M.
AU - Tavani, Giulio
AU - Botifoll, Marc
AU - Crippa, Alessandro
AU - Kukucka, Josip
AU - Sagi, Oliver
AU - Martins, Frederico
AU - Saez Mollejo, Jaime
AU - Prieto Gonzalez, Ivan
AU - Borovkov, Maksim
AU - Arbiol, Jordi
AU - Chrastina, Daniel
AU - Isella, Giovanni
AU - Katsaros, Georgios
ID - 8909
JF - Nature Materials
SN - 1476-1122
TI - A singlet triplet hole spin qubit in planar Ge
ER -
TY - DATA
AB - This .zip File contains the data for figures presented in the main text and supplementary material of "A singlet triplet hole spin qubit in planar Ge" by D. Jirovec, et. al. The measurements were done using Labber Software and the data is stored in the hdf5 file format. The files can be opened using either the Labber Log Browser (https://labber.org/overview/) or Labber Python API (http://labber.org/online-doc/api/LogFile.html). A single file is acquired with QCodes and features the corresponding data type. XRD data are in .dat format and a code to open the data is provided. The code for simulations is as well provided in Python.
AU - Jirovec, Daniel
ID - 9323
TI - Research data for "A singlet-triplet hole spin qubit planar Ge"
ER -
TY - CONF
AB - In runtime verification, a monitor watches a trace of a system and, if possible, decides after observing each finite prefix whether or not the unknown infinite trace satisfies a given specification. We generalize the theory of runtime verification to monitors that attempt to estimate numerical values of quantitative trace properties (instead of attempting to conclude boolean values of trace specifications), such as maximal or average response time along a trace. Quantitative monitors are approximate: with every finite prefix, they can improve their estimate of the infinite trace's unknown property value. Consequently, quantitative monitors can be compared with regard to a precision-cost trade-off: better approximations of the property value require more monitor resources, such as states (in the case of finite-state monitors) or registers, and additional resources yield better approximations. We introduce a formal framework for quantitative and approximate monitoring, show how it conservatively generalizes the classical boolean setting for monitoring, and give several precision-cost trade-offs for monitors. For example, we prove that there are quantitative properties for which every additional register improves monitoring precision.
AU - Henzinger, Thomas A
AU - Sarac, Naci E
ID - 9356
T2 - Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Quantitative and approximate monitoring
ER -
TY - CONF
AB - The convex grabbing game is a game where two players, Alice and Bob, alternate taking extremal points from the convex hull of a point set on the plane. Rational weights are given to the points. The goal of each player is to maximize the total weight over all points that they obtain. We restrict the setting to the case of binary weights. We show a construction of an arbitrarily large odd-sized point set that allows Bob to obtain almost 3/4 of the total weight. This construction answers a question asked by Matsumoto, Nakamigawa, and Sakuma in [Graphs and Combinatorics, 36/1 (2020)]. We also present an arbitrarily large even-sized point set where Bob can obtain the entirety of the total weight. Finally, we discuss conjectures about optimum moves in the convex grabbing game for both players in general.
AU - Dvorak, Martin
AU - Nicholson, Sara
ID - 9592
KW - convex grabbing game
KW - graph grabbing game
KW - combinatorial game
KW - convex geometry
T2 - Proceedings of the 33rd Canadian Conference on Computational Geometry
TI - Massively winning configurations in the convex grabbing game on the plane
ER -
TY - JOUR
AB - We investigate how the critical driving amplitude at the Floquet many-body localized (MBL) to ergodic phase transition differs between smooth and nonsmooth drives. To this end, we numerically study a disordered spin-1/2 chain which is periodically driven by a sine or square-wave drive over a wide range of driving frequencies. In both cases the critical driving amplitude increases monotonically with the frequency, and at large frequencies it is identical for the two drives. However, at low and intermediate frequencies the critical amplitude of the square-wave drive depends strongly on the frequency, while that of the sinusoidal drive is almost constant over a wide frequency range. By analyzing the density of drive-induced resonances we conclude that this difference is due to resonances induced by the higher harmonics which are present (absent) in the Fourier spectrum of the square-wave (sine) drive. Furthermore, we suggest a numerically efficient method for estimating the frequency dependence of the critical driving amplitudes for different drives which is based on calculating the density of drive-induced resonances. We conclude that delocalization occurs once the density of drive-induced resonances reaches a critical value determined only by the static system.
AU - Diringer, Asaf A.
AU - Gulden, Tobias
ID - 8198
IS - 21
JF - Physical Review B
SN - 24699950
TI - Impact of drive harmonics on the stability of Floquet many-body localization
VL - 103
ER -
TY - JOUR
AB - When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.
AU - Aichholzer, Oswin
AU - Akitaya, Hugo A.
AU - Cheung, Kenneth C.
AU - Demaine, Erik D.
AU - Demaine, Martin L.
AU - Fekete, Sándor P.
AU - Kleist, Linda
AU - Kostitsyna, Irina
AU - Löffler, Maarten
AU - Masárová, Zuzana
AU - Mundilova, Klara
AU - Schmidt, Christiane
ID - 8317
JF - Computational Geometry: Theory and Applications
SN - 09257721
TI - Folding polyominoes with holes into a cube
VL - 93
ER -
TY - JOUR
AB - Resting-state brain activity is characterized by the presence of neuronal avalanches showing absence of characteristic size. Such evidence has been interpreted in the context of criticality and associated with the normal functioning of the brain. A distinctive attribute of systems at criticality is the presence of long-range correlations. Thus, to verify the hypothesis that the brain operates close to a critical point and consequently assess deviations from criticality for diagnostic purposes, it is of primary importance to robustly and reliably characterize correlations in resting-state brain activity. Recent works focused on the analysis of narrow-band electroencephalography (EEG) and magnetoencephalography (MEG) signal amplitude envelope, showing evidence of long-range temporal correlations (LRTC) in neural oscillations. However, brain activity is a broadband phenomenon, and a significant piece of information useful to precisely discriminate between normal (critical) and pathological behavior (non-critical), may be encoded in the broadband spatio-temporal cortical dynamics. Here we propose to characterize the temporal correlations in the broadband brain activity through the lens of neuronal avalanches. To this end, we consider resting-state EEG and long-term MEG recordings, extract the corresponding neuronal avalanche sequences, and study their temporal correlations. We demonstrate that the broadband resting-state brain activity consistently exhibits long-range power-law correlations in both EEG and MEG recordings, with similar values of the scaling exponents. Importantly, although we observe that the avalanche size distribution depends on scale parameters, scaling exponents characterizing long-range correlations are quite robust. In particular, they are independent of the temporal binning (scale of analysis), indicating that our analysis captures intrinsic characteristics of the underlying dynamics. Because neuronal avalanches constitute a fundamental feature of neural systems with universal characteristics, the proposed approach may serve as a general, systems- and experiment-independent procedure to infer the existence of underlying long-range correlations in extended neural systems, and identify pathological behaviors in the complex spatio-temporal interplay of cortical rhythms.
AU - Lombardi, Fabrizio
AU - Shriki, Oren
AU - Herrmann, Hans J
AU - de Arcangelis, Lucilla
ID - 7463
JF - Neurocomputing
SN - 09252312
TI - Long-range temporal correlations in the broadband resting state activity of the human brain revealed by neuronal avalanches
ER -
TY - JOUR
AB - SnSe, a wide-bandgap semiconductor, has attracted significant attention from the thermoelectric (TE) community due to its outstanding TE performance deriving from the ultralow thermal conductivity and advantageous electronic structures. Here, we promoted the TE performance of n-type SnSe polycrystals through bandgap engineering and vacancy compensation. We found that PbTe can significantly reduce the wide bandgap of SnSe to reduce the impurity transition energy, largely enhancing the carrier concentration. Also, PbTe-induced crystal symmetry promotion increases the carrier mobility, preserving large Seebeck coefficient. Consequently, a maximum ZT of ∼1.4 at 793 K is obtained in Br doped SnSe–13%PbTe. Furthermore, we found that extra Sn in n-type SnSe can compensate for the intrinsic Sn vacancies and form electron donor-like metallic Sn nanophases. The Sn nanophases near the grain boundary could also reduce the intergrain energy barrier which largely enhances the carrier mobility. As a result, a maximum ZT value of ∼1.7 at 793 K and an average ZT (ZTave) of ∼0.58 in 300–793 K are achieved in Br doped Sn1.08Se–13%PbTe. Our findings provide a novel strategy to promote the TE performance in wide-bandgap semiconductors.
AU - Su, Lizhong
AU - Hong, Tao
AU - Wang, Dongyang
AU - Wang, Sining
AU - Qin, Bingchao
AU - Zhang, Mengmeng
AU - Gao, Xiang
AU - Chang, Cheng
AU - Zhao, Li Dong
ID - 9626
JF - Materials Today Physics
TI - Realizing high doping efficiency and thermoelectric performance in n-type SnSe polycrystals via bandgap engineering and vacancy compensation
VL - 20
ER -
TY - JOUR
AB - Rigorous investigation of synaptic transmission requires analysis of unitary synaptic events by simultaneous recording from presynaptic terminals and postsynaptic target neurons. However, this has been achieved at only a limited number of model synapses, including the squid giant synapse and the mammalian calyx of Held. Cortical presynaptic terminals have been largely inaccessible to direct presynaptic recording, due to their small size. Here, we describe a protocol for improved subcellular patch-clamp recording in rat and mouse brain slices, with the synapse in a largely intact environment. Slice preparation takes ~2 h, recording ~3 h and post hoc morphological analysis 2 d. Single presynaptic hippocampal mossy fiber terminals are stimulated minimally invasively in the bouton-attached configuration, in which the cytoplasmic content remains unperturbed, or in the whole-bouton configuration, in which the cytoplasmic composition can be precisely controlled. Paired pre–postsynaptic recordings can be integrated with biocytin labeling and morphological analysis, allowing correlative investigation of synapse structure and function. Paired recordings can be obtained from mossy fiber terminals in slices from both rats and mice, implying applicability to genetically modified synapses. Paired recordings can also be performed together with axon tract stimulation or optogenetic activation, allowing comparison of unitary and compound synaptic events in the same target cell. Finally, paired recordings can be combined with spontaneous event analysis, permitting collection of miniature events generated at a single identified synapse. In conclusion, the subcellular patch-clamp techniques detailed here should facilitate analysis of biophysics, plasticity and circuit function of cortical synapses in the mammalian central nervous system.
AU - Vandael, David H
AU - Okamoto, Yuji
AU - Borges Merjane, Carolina
AU - Vargas Barroso, Victor M
AU - Suter, Benjamin
AU - Jonas, Peter M
ID - 9438
IS - 6
JF - Nature Protocols
SN - 17542189
TI - Subcellular patch-clamp techniques for single-bouton stimulation and simultaneous pre- and postsynaptic recording at cortical synapses
VL - 16
ER -
TY - CONF
AB - Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.
AU - Corbet, René
AU - Kerber, Michael
AU - Lesnick, Michael
AU - Osang, Georg F
ID - 9605
SN - 18688969
T2 - Leibniz International Proceedings in Informatics
TI - Computing the multicover bifiltration
VL - 189
ER -
TY - JOUR
AB - The control of nonequilibrium quantum dynamics in many-body systems is challenging because interactions typically lead to thermalization and a chaotic spreading throughout Hilbert space. We investigate nonequilibrium dynamics after rapid quenches in a many-body system composed of 3 to 200 strongly interacting qubits in one and two spatial dimensions. Using a programmable quantum simulator based on Rydberg atom arrays, we show that coherent revivals associated with so-called quantum many-body scars can be stabilized by periodic driving, which generates a robust subharmonic response akin to discrete time-crystalline order. We map Hilbert space dynamics, geometry dependence, phase diagrams, and system-size dependence of this emergent phenomenon, demonstrating new ways to steer complex dynamics in many-body systems and enabling potential applications in quantum information science.
AU - Bluvstein, D.
AU - Omran, A.
AU - Levine, H.
AU - Keesling, A.
AU - Semeghini, G.
AU - Ebadi, S.
AU - Wang, T. T.
AU - Michailidis, Alexios
AU - Maskara, N.
AU - Ho, W. W.
AU - Choi, S.
AU - Serbyn, Maksym
AU - Greiner, M.
AU - Vuletić, V.
AU - Lukin, M. D.
ID - 9618
IS - 6536
JF - Science
KW - Multidisciplinary
SN - 0036-8075
TI - Controlling quantum many-body dynamics in driven Rydberg atom arrays
VL - 371
ER -
TY - JOUR
AB - As the size and complexity of models and datasets grow, so does the need for communication-efficient variants of stochastic gradient descent that can be deployed to perform parallel model training. One popular communication-compression method for data-parallel SGD is QSGD (Alistarh et al., 2017), which quantizes and encodes gradients to reduce communication costs. The baseline variant of QSGD provides strong theoretical guarantees, however, for practical purposes, the authors proposed a heuristic variant which we call QSGDinf, which demonstrated impressive empirical gains for distributed training of large neural networks. In this paper, we build on this work to propose a new gradient quantization scheme, and show that it has both stronger theoretical guarantees than QSGD, and matches and exceeds the empirical performance of the QSGDinf heuristic and of other compression methods.
AU - Ramezani-Kebrya, Ali
AU - Faghri, Fartash
AU - Markov, Ilya
AU - Aksenov, Vitalii
AU - Alistarh, Dan-Adrian
AU - Roy, Daniel M.
ID - 9571
IS - 114
JF - Journal of Machine Learning Research
SN - 15324435
TI - NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization
VL - 22
ER -
TY - JOUR
AB - Intestinal organoids derived from single cells undergo complex crypt–villus patterning and morphogenesis. However, the nature and coordination of the underlying forces remains poorly characterized. Here, using light-sheet microscopy and large-scale imaging quantification, we demonstrate that crypt formation coincides with a stark reduction in lumen volume. We develop a 3D biophysical model to computationally screen different mechanical scenarios of crypt morphogenesis. Combining this with live-imaging data and multiple mechanical perturbations, we show that actomyosin-driven crypt apical contraction and villus basal tension work synergistically with lumen volume reduction to drive crypt morphogenesis, and demonstrate the existence of a critical point in differential tensions above which crypt morphology becomes robust to volume changes. Finally, we identified a sodium/glucose cotransporter that is specific to differentiated enterocytes that modulates lumen volume reduction through cell swelling in the villus region. Together, our study uncovers the cellular basis of how cell fate modulates osmotic and actomyosin forces to coordinate robust morphogenesis.
AU - Yang, Qiutan
AU - Xue, Shi-lei
AU - Chan, Chii Jou
AU - Rempfler, Markus
AU - Vischi, Dario
AU - Maurer-Gutierrez, Francisca
AU - Hiiragi, Takashi
AU - Hannezo, Edouard B
AU - Liberali, Prisca
ID - 9629
JF - Nature Cell Biology
SN - 14657392
TI - Cell fate coordinates mechano-osmotic forces in intestinal crypt formation
ER -
TY - JOUR
AB - Perineuronal nets (PNNs), components of the extracellular matrix, preferentially coat parvalbumin-positive interneurons and constrain critical-period plasticity in the adult cerebral cortex. Current strategies to remove PNN are long-lasting, invasive, and trigger neuropsychiatric symptoms. Here, we apply repeated anesthetic ketamine as a method with minimal behavioral effect. We find that this paradigm strongly reduces PNN coating in the healthy adult brain and promotes juvenile-like plasticity. Microglia are critically involved in PNN loss because they engage with parvalbumin-positive neurons in their defined cortical layer. We identify external 60-Hz light-flickering entrainment to recapitulate microglia-mediated PNN removal. Importantly, 40-Hz frequency, which is known to remove amyloid plaques, does not induce PNN loss, suggesting microglia might functionally tune to distinct brain frequencies. Thus, our 60-Hz light-entrainment strategy provides an alternative form of PNN intervention in the healthy adult brain.
AU - Venturino, Alessandro
AU - Schulz, Rouven
AU - De Jesús-Cortés, Héctor
AU - Maes, Margaret E
AU - Nagy, Balint
AU - Reilly-Andújar, Francis
AU - Colombo, Gloria
AU - Cubero, Ryan J
AU - Schoot Uiterkamp, Florianne E
AU - Bear, Mark F.
AU - Siegert, Sandra
ID - 9642
IS - 1
JF - Cell Reports
TI - Microglia enable mature perineuronal nets disassembly upon anesthetic ketamine exposure or 60-Hz light entrainment in the healthy brain
VL - 36
ER -
TY - JOUR
AB - At the encounter with a novel environment, contextual memory formation is greatly enhanced, accompanied with increased arousal and active exploration. Although this phenomenon has been widely observed in animal and human daily life, how the novelty in the environment is detected and contributes to contextual memory formation has lately started to be unveiled. The hippocampus has been studied for many decades for its largely known roles in encoding spatial memory, and a growing body of evidence indicates a differential involvement of dorsal and ventral hippocampal divisions in novelty detection. In this brief review article, we discuss the recent findings of the role of mossy cells in the ventral hippocampal moiety in novelty detection and put them in perspective with other novelty-related pathways in the hippocampus. We propose a mechanism for novelty-driven memory acquisition in the dentate gyrus by the direct projection of ventral mossy cells to dorsal dentate granule cells. By this projection, the ventral hippocampus sends novelty signals to the dorsal hippocampus, opening a gate for memory encoding in dentate granule cells based on information coming from the entorhinal cortex. We conclude that, contrary to the presently accepted functional independence, the dorsal and ventral hippocampi cooperate to link the novelty and contextual information, and this dorso-ventral interaction is crucial for the novelty-dependent memory formation.
AU - Fredes, Felipe
AU - Shigemoto, Ryuichi
ID - 9641
JF - Neurobiology of Learning and Memory
SN - 10747427
TI - The role of hippocampal mossy cells in novelty detection
VL - 183
ER -
TY - JOUR
AB - The relative motion of three impenetrable particles on a ring, in our case two identical fermions and one impurity, is isomorphic to a triangular quantum billiard. Depending on the ratio κ of the impurity and fermion masses, the billiards can be integrable or non-integrable (also referred to in the main text as chaotic). To set the stage, we first investigate the energy level distributions of the billiards as a function of 1/κ ∈ [0, 1] and find no evidence of integrable cases beyond the limiting values 1/κ = 1 and 1/κ = 0. Then, we use machine learning tools to analyze properties of probability distributions of individual quantum states. We find that convolutional neural networks can correctly classify integrable and non-integrable states. The decisive features of the wave functions are the normalization and a large number of zero elements, corresponding to the existence of a nodal line. The network achieves typical accuracies of 97%, suggesting that machine learning tools can be used to analyze and classify the morphology of probability densities obtained in theory or experiment.
AU - Huber, David
AU - Marchukov, Oleksandr V.
AU - Hammer, Hans Werner
AU - Volosniev, Artem
ID - 9679
IS - 6
JF - New Journal of Physics
TI - Morphology of three-body quantum states from machine learning
VL - 23
ER -
TY - JOUR
AB - To overcome nitrogen deficiency, legume roots establish symbiotic interactions with nitrogen-fixing rhizobia that is fostered in specialized organs (nodules). Similar to other organs, nodule formation is determined by a local maximum of the phytohormone auxin at the primordium site. However, how auxin regulates nodule development remains poorly understood. Here, we found that in soybean, (Glycine max), dynamic auxin transport driven by PIN-FORMED (PIN) transporter GmPIN1 is involved in nodule primordium formation. GmPIN1 was specifically expressed in nodule primordium cells and GmPIN1 was polarly localized in these cells. Two nodulation regulators, (iso)flavonoids trigger expanded distribution of GmPIN1b to root cortical cells, and cytokinin rearranges GmPIN1b polarity. Gmpin1abc triple mutants generated with CRISPR-Cas9 showed impaired establishment of auxin maxima in nodule meristems and aberrant divisions in the nodule primordium cells. Moreover, overexpression of GmPIN1 suppressed nodule primordium initiation. GmPIN9d, an ortholog of Arabidopsis thaliana PIN2, acts together with GmPIN1 later in nodule development to acropetally transport auxin in vascular bundles, fine-tuning the auxin supply for nodule enlargement. Our findings reveal how PIN-dependent auxin transport modulates different aspects of soybean nodule development and suggest that establishment of auxin gradient is a prerequisite for the proper interaction between legumes and rhizobia.
AU - Gao, Z
AU - Chen, Z
AU - Cui, Y
AU - Ke, M
AU - Xu, H
AU - Xu, Q
AU - Chen, J
AU - Li, Y
AU - Huang, L
AU - Zhao, H
AU - Huang, D
AU - Mai, S
AU - Xu, T
AU - Liu, X
AU - Li, S
AU - Guan, Y
AU - Yang, W
AU - Friml, Jiří
AU - Petrášek, J
AU - Zhang, J
AU - Chen, X
ID - 9657
JF - Plant Cell
SN - 1040-4651
TI - GmPIN-dependent polar auxin transport is involved in soybean nodule development
ER -
TY - JOUR
AB - Tropisms, growth responses to environmental stimuli such as light or gravity, are spectacular examples of adaptive plant development. The plant hormone auxin serves as a major coordinative signal. The PIN auxin exporters, through their dynamic polar subcellular localizations, redirect auxin fluxes in response to environmental stimuli and the resulting auxin gradients across organs underly differential cell elongation and bending. In this review, we discuss recent advances concerning regulations of PIN polarity during tropisms, focusing on PIN phosphorylation and trafficking. We also cover how environmental cues regulate PIN actions during tropisms, and a crucial role of auxin feedback on PIN polarity during bending termination. Finally, the interactions between different tropisms are reviewed to understand plant adaptive growth in the natural environment.
AU - Han, Huibin
AU - Adamowski, Maciek
AU - Qi, Linlin
AU - Alotaibi, SS
AU - Friml, Jiří
ID - 9656
JF - New Phytologist
SN - 0028-646x
TI - PIN-mediated polar auxin transport regulations in plant tropic responses
ER -
TY - JOUR
AB - A semiconducting nanowire fully wrapped by a superconducting shell has been proposed as a platform for obtaining Majorana modes at small magnetic fields. In this study, we demonstrate that the appearance of subgap states in such structures is actually governed by the junction region in tunneling spectroscopy measurements and not the full-shell nanowire itself. Short tunneling regions never show subgap states, whereas longer junctions always do. This can be understood in terms of quantum dots forming in the junction and hosting Andreev levels in the Yu-Shiba-Rusinov regime. The intricate magnetic field dependence of the Andreev levels, through both the Zeeman and Little-Parks effects, may result in robust zero-bias peaks—features that could be easily misinterpreted as originating from Majorana zero modes but are unrelated to topological superconductivity.
AU - Valentini, Marco
AU - Peñaranda, Fernando
AU - Hofmann, Andrea C
AU - Brauns, Matthias
AU - Hauschild, Robert
AU - Krogstrup, Peter
AU - San-Jose, Pablo
AU - Prada, Elsa
AU - Aguado, Ramón
AU - Katsaros, Georgios
ID - 8910
IS - 6550
JF - Science
SN - 00368075
TI - Nontopological zero-bias peaks in full-shell nanowires induced by flux-tunable Andreev states
VL - 373
ER -
TY - JOUR
AB - We compute the deficiency spaces of operators of the form 𝐻𝐴⊗̂ 𝐼+𝐼⊗̂ 𝐻𝐵, for symmetric 𝐻𝐴 and self-adjoint 𝐻𝐵. This enables us to construct self-adjoint extensions (if they exist) by means of von Neumann's theory. The structure of the deficiency spaces for this case was asserted already in Ibort et al. [Boundary dynamics driven entanglement, J. Phys. A: Math. Theor. 47(38) (2014) 385301], but only proven under the restriction of 𝐻𝐵 having discrete, non-degenerate spectrum.
AU - Lenz, Daniel
AU - Weinmann, Timon
AU - Wirth, Melchior
ID - 9627
JF - Proceedings of the Edinburgh Mathematical Society
SN - 00130915
TI - Self-adjoint extensions of bipartite Hamiltonians
ER -
TY - GEN
AB - We introduce a hierachy of equivalence relations on the set of separated nets of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞). Two separated nets are called ϕ-displacement equivalent if, roughly speaking, there is a bijection between them which, for large radii R, displaces points of norm at most R by something of order at most ϕ(R). We show that the spectrum of ϕ-displacement equivalence spans from the established notion of bounded displacement equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation, coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞. We further undertake a comparison of our notion of ϕ-displacement equivalence with previously studied relations on separated nets. Particular attention is given to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz equivalence.
AU - Dymond, Michael
AU - Kaluza, Vojtech
ID - 9651
T2 - arXiv
TI - Divergence of separated nets with respect to displacement equivalence
ER -
TY - JOUR
AB - Gene expression is regulated by the set of transcription factors (TFs) that bind to the promoter. The ensuing regulating function is often represented as a combinational logic circuit, where output (gene expression) is determined by current input values (promoter bound TFs) only. However, the simultaneous arrival of TFs is a strong assumption, since transcription and translation of genes introduce intrinsic time delays and there is no global synchronisation among the arrival times of different molecular species at their targets. We present an experimentally implementable genetic circuit with two inputs and one output, which in the presence of small delays in input arrival, exhibits qualitatively distinct population-level phenotypes, over timescales that are longer than typical cell doubling times. From a dynamical systems point of view, these phenotypes represent long-lived transients: although they converge to the same value eventually, they do so after a very long time span. The key feature of this toy model genetic circuit is that, despite having only two inputs and one output, it is regulated by twenty-three distinct DNA-TF configurations, two of which are more stable than others (DNA looped states), one promoting and another blocking the expression of the output gene. Small delays in input arrival time result in a majority of cells in the population quickly reaching the stable state associated with the first input, while exiting of this stable state occurs at a slow timescale. In order to mechanistically model the behaviour of this genetic circuit, we used a rule-based modelling language, and implemented a grid-search to find parameter combinations giving rise to long-lived transients. Our analysis shows that in the absence of feedback, there exist path-dependent gene regulatory mechanisms based on the long timescale of transients. The behaviour of this toy model circuit suggests that gene regulatory networks can exploit event timing to create phenotypes, and it opens the possibility that they could use event timing to memorise events, without regulatory feedback. The model reveals the importance of (i) mechanistically modelling the transitions between the different DNA-TF states, and (ii) employing transient analysis thereof.
AU - Petrov, Tatjana
AU - Igler, Claudia
AU - Sezgin, Ali
AU - Henzinger, Thomas A
AU - Guet, Calin C
ID - 9647
JF - Theoretical Computer Science
SN - 03043975
TI - Long lived transients in gene regulation
ER -
TY - CONF
AB - We consider the fundamental problem of deriving quantitative bounds on the probability that a given assertion is violated in a probabilistic program. We provide automated algorithms that obtain both lower and upper bounds on the assertion violation probability. The main novelty of our approach is that we prove new and dedicated fixed-point theorems which serve as the theoretical basis of our algorithms and enable us to reason about assertion violation bounds in terms of pre and post fixed-point functions. To synthesize such fixed-points, we devise algorithms that utilize a wide range of mathematical tools, including repulsing ranking supermartingales, Hoeffding's lemma, Minkowski decompositions, Jensen's inequality, and convex optimization. On the theoretical side, we provide (i) the first automated algorithm for lower-bounds on assertion violation probabilities, (ii) the first complete algorithm for upper-bounds of exponential form in affine programs, and (iii) provably and significantly tighter upper-bounds than the previous approaches. On the practical side, we show our algorithms can handle a wide variety of programs from the literature and synthesize bounds that are remarkably tighter than previous results, in some cases by thousands of orders of magnitude.
AU - Wang, Jinyi
AU - Sun, Yican
AU - Fu, Hongfei
AU - Chatterjee, Krishnendu
AU - Goharshady, Amir Kafshdar
ID - 9646
SN - 9781450383912
T2 - Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
TI - Quantitative analysis of assertion violations in probabilistic programs
ER -
TY - CONF
AB - We consider the fundamental problem of reachability analysis over imperative programs with real variables. Previous works that tackle reachability are either unable to handle programs consisting of general loops (e.g. symbolic execution), or lack completeness guarantees (e.g. abstract interpretation), or are not automated (e.g. incorrectness logic). In contrast, we propose a novel approach for reachability analysis that can handle general and complex loops, is complete, and can be entirely automated for a wide family of programs. Through the notion of Inductive Reachability Witnesses (IRWs), our approach extends ideas from both invariant generation and termination to reachability analysis.
We first show that our IRW-based approach is sound and complete for reachability analysis of imperative programs. Then, we focus on linear and polynomial programs and develop automated methods for synthesizing linear and polynomial IRWs. In the linear case, we follow the well-known approaches using Farkas' Lemma. Our main contribution is in the polynomial case, where we present a push-button semi-complete algorithm. We achieve this using a novel combination of classical theorems in real algebraic geometry, such as Putinar's Positivstellensatz and Hilbert's Strong Nullstellensatz. Finally, our experimental results show we can prove complex reachability objectives over various benchmarks that were beyond the reach of previous methods.
AU - Asadi, Ali
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Goharshady, Amir Kafshdar
AU - Mahdavi, Mohammad
ID - 9645
SN - 9781450383912
T2 - Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
TI - Polynomial reachability witnesses via Stellensätze
ER -
TY - CONF
AB - We present a new approach to proving non-termination of non-deterministic integer programs. Our technique is rather simple but efficient. It relies on a purely syntactic reversal of the program's transition system followed by a constraint-based invariant synthesis with constraints coming from both the original and the reversed transition system. The latter task is performed by a simple call to an off-the-shelf SMT-solver, which allows us to leverage the latest advances in SMT-solving. Moreover, our method offers a combination of features not present (as a whole) in previous approaches: it handles programs with non-determinism, provides relative completeness guarantees and supports programs with polynomial arithmetic. The experiments performed with our prototype tool RevTerm show that our approach, despite its simplicity and stronger theoretical guarantees, is at least on par with the state-of-the-art tools, often achieving a non-trivial improvement under a proper configuration of its parameters.
AU - Chatterjee, Krishnendu
AU - Goharshady, Ehsan Kafshdar
AU - Novotný, Petr
AU - Zikelic, Dorde
ID - 9644
SN - 9781450383912
T2 - Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
TI - Proving non-termination by program reversal
ER -
TY - JOUR
AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f : Rd → Rd−n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation T of the ambient space Rd. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently
fine triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.
AU - Boissonnat, Jean-Daniel
AU - Wintraecken, Mathijs
ID - 9649
JF - Foundations of Computational Mathematics
TI - The topological correctness of PL approximations of isomanifolds
ER -
TY - CONF
AB - We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
AU - Brandt, Sebastian
AU - Keller, Barbara
AU - Rybicki, Joel
AU - Suomela, Jukka
AU - Uitto, Jara
ID - 9678
SN - 9781450380706
T2 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
TI - Efficient load-balancing through distributed token dropping
ER -
TY - CONF
AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.
AU - Boissonnat, Jean-Daniel
AU - Kachanovich, Siargey
AU - Wintraecken, Mathijs
ID - 9441
SN - 1868-8969
T2 - 37th International Symposium on Computational Geometry (SoCG 2021)
TI - Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations
VL - 189
ER -
TY - CONF
AB - In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).
We provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.
AU - Alistarh, Dan-Adrian
AU - Davies, Peter
ID - 9620
SN - 0302-9743
T2 - Structural Information and Communication Complexity
TI - Collecting coupons is faster with friends
VL - 12810
ER -
TY - CONF
AB - Formal design of embedded and cyber-physical systems relies on mathematical modeling. In this paper, we consider the model class of hybrid automata whose dynamics are defined by affine differential equations. Given a set of time-series data, we present an algorithmic approach to synthesize a hybrid automaton exhibiting behavior that is close to the data, up to a specified precision, and changes in synchrony with the data. A fundamental problem in our synthesis algorithm is to check membership of a time series in a hybrid automaton. Our solution integrates reachability and optimization techniques for affine dynamical systems to obtain both a sufficient and a necessary condition for membership, combined in a refinement framework. The algorithm processes one time series at a time and hence can be interrupted, provide an intermediate result, and be resumed. We report experimental results demonstrating the applicability of our synthesis approach.
AU - Garcia Soto, Miriam
AU - Henzinger, Thomas A
AU - Schilling, Christian
ID - 9200
KW - hybrid automaton
KW - membership
KW - system identification
SN - 9781450383394
T2 - HSCC '21: Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control
TI - Synthesis of hybrid automata with affine dynamics from time-series data
ER -
TY - CONF
AB - Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction.
AU - Edelsbrunner, Herbert
AU - Heiss, Teresa
AU - Kurlin , Vitaliy
AU - Smith, Philip
AU - Wintraecken, Mathijs
ID - 9345
SN - 1868-8969
T2 - 37th International Symposium on Computational Geometry (SoCG 2021)
TI - The density fingerprint of a periodic point set
VL - 189
ER -
TY - CONF
AB - matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.
AU - Aichholzer, Oswin
AU - Arroyo Guevara, Alan M
AU - Masárová, Zuzana
AU - Parada, Irene
AU - Perz, Daniel
AU - Pilz, Alexander
AU - Tkadlec, Josef
AU - Vogtenhuber, Birgit
ID - 9296
SN - 03029743
T2 - 15th International Conference on Algorithms and Computation
TI - On compatible matchings
VL - 12635
ER -