TY - JOUR
AB - Plants are continuously exposed to a myriad of external signals such as fluctuating nutrients availability, drought, heat, cold, high salinity, or pathogen/pest attacks that can severely affect their development, growth, and fertility. As sessile organisms, plants must therefore be able to sense and rapidly react to these external inputs, activate efficient responses, and adjust development to changing conditions. In recent years, significant progress has been made towards understanding the molecular mechanisms underlying the intricate and complex communication between plants and the environment. It is now becoming increasingly evident that hormones have an important regulatory role in plant adaptation and defense mechanisms.
AU - Benková, Eva
ID - 1269
IS - 6
JF - Plant Molecular Biology
TI - Plant hormones in interactions with the environment
VL - 91
ER -
TY - JOUR
AB - A crucial step in the early development of multicellular organisms involves the establishment of spatial patterns of gene expression which later direct proliferating cells to take on different cell fates. These patterns enable the cells to infer their global position within a tissue or an organism by reading out local gene expression levels. The patterning system is thus said to encode positional information, a concept that was formalized recently in the framework of information theory. Here we introduce a toy model of patterning in one spatial dimension, which can be seen as an extension of Wolpert's paradigmatic "French Flag" model, to patterning by several interacting, spatially coupled genes subject to intrinsic and extrinsic noise. Our model, a variant of an Ising spin system, allows us to systematically explore expression patterns that optimally encode positional information. We find that optimal patterning systems use positional cues, as in the French Flag model, together with gene-gene interactions to generate combinatorial codes for position which we call "Counter" patterns. Counter patterns can also be stabilized against noise and variations in system size or morphogen dosage by longer-range spatial interactions of the type invoked in the Turing model. The simple setup proposed here qualitatively captures many of the experimentally observed properties of biological patterning systems and allows them to be studied in a single, theoretically consistent framework.
AU - Hillenbrand, Patrick
AU - Gerland, Ulrich
AU - Tkacik, Gasper
ID - 1270
IS - 9
JF - PLoS One
TI - Beyond the French flag model: Exploiting spatial and gene regulatory interactions for positional information
VL - 11
ER -
TY - JOUR
AB - Background: High directional persistence is often assumed to enhance the efficiency of chemotactic migration. Yet, cells in vivo usually display meandering trajectories with relatively low directional persistence, and the control and function of directional persistence during cell migration in three-dimensional environments are poorly understood. Results: Here, we use mesendoderm progenitors migrating during zebrafish gastrulation as a model system to investigate the control of directional persistence during migration in vivo. We show that progenitor cells alternate persistent run phases with tumble phases that result in cell reorientation. Runs are characterized by the formation of directed actin-rich protrusions and tumbles by enhanced blebbing. Increasing the proportion of actin-rich protrusions or blebs leads to longer or shorter run phases, respectively. Importantly, both reducing and increasing run phases result in larger spatial dispersion of the cells, indicative of reduced migration precision. A physical model quantitatively recapitulating the migratory behavior of mesendoderm progenitors indicates that the ratio of tumbling to run times, and thus the specific degree of directional persistence of migration, are critical for optimizing migration precision. Conclusions: Together, our experiments and model provide mechanistic insight into the control of migration directionality for cells moving in three-dimensional environments that combine different protrusion types, whereby the proportion of blebs to actin-rich protrusions determines the directional persistence and precision of movement by regulating the ratio of tumbling to run times.
AU - Diz Muñoz, Alba
AU - Romanczuk, Pawel
AU - Yu, Weimiao
AU - Bergert, Martin
AU - Ivanovitch, Kenzo
AU - Salbreux, Guillame
AU - Heisenberg, Carl-Philipp J
AU - Paluch, Ewa
ID - 1271
IS - 1
JF - BMC Biology
TI - Steering cell migration by alternating blebs and actin-rich protrusions
VL - 14
ER -
TY - JOUR
AB - We study different means to extend offsetting based on skeletal structures beyond the well-known constant-radius and mitered offsets supported by Voronoi diagrams and straight skeletons, for which the orthogonal distance of offset elements to their respective input elements is constant and uniform over all input elements. Our main contribution is a new geometric structure, called variable-radius Voronoi diagram, which supports the computation of variable-radius offsets, i.e., offsets whose distance to the input is allowed to vary along the input. We discuss properties of this structure and sketch a prototype implementation that supports the computation of variable-radius offsets based on this new variant of Voronoi diagrams.
AU - Held, Martin
AU - Huber, Stefan
AU - Palfrader, Peter
ID - 1272
IS - 5
JF - Computer-Aided Design and Applications
TI - Generalized offsetting of planar structures using skeletons
VL - 13
ER -
TY - JOUR
AB - Lateral root primordia (LRP) originate from pericycle stem cells located deep within parental root tissues. LRP emerge through overlying root tissues by inducing auxin-dependent cell separation and hydraulic changes in adjacent cells. The auxin-inducible auxin influx carrier LAX3 plays a key role concentrating this signal in cells overlying LRP. Delimiting LAX3 expression to two adjacent cell files overlying new LRP is crucial to ensure that auxin-regulated cell separation occurs solely along their shared walls. Multiscale modeling has predicted that this highly focused pattern of expression requires auxin to sequentially induce auxin efflux and influx carriers PIN3 and LAX3, respectively. Consistent with model predictions, we report that auxin-inducible LAX3 expression is regulated indirectly by AUXIN RESPONSE FACTOR 7 (ARF7). Yeast one-hybrid screens revealed that the LAX3 promoter is bound by the transcription factor LBD29, which is a direct target for regulation by ARF7. Disrupting auxin-inducible LBD29 expression or expressing an LBD29-SRDX transcriptional repressor phenocopied the lax3 mutant, resulting in delayed lateral root emergence. We conclude that sequential LBD29 and LAX3 induction by auxin is required to coordinate cell separation and organ emergence.
AU - Porco, Silvana
AU - Larrieu, Antoine
AU - Du, Yujuan
AU - Gaudinier, Allison
AU - Goh, Tatsuaki
AU - Swarup, Kamal
AU - Swarup, Ranjan
AU - Kuempers, Britta
AU - Bishopp, Anthony
AU - Lavenus, Julien
AU - Casimiro, Ilda
AU - Hill, Kristine
AU - Benková, Eva
AU - Fukaki, Hidehiro
AU - Brady, Siobhan
AU - Scheres, Ben
AU - Peéet, Benjamin
AU - Bennett, Malcolm
ID - 1273
IS - 18
JF - Development
TI - Lateral root emergence in Arabidopsis is dependent on transcription factor LBD29 regulation of auxin influx carrier LAX3
VL - 143
ER -
TY - JOUR
AB - Synchronized tissue polarization during regeneration or de novo vascular tissue formation is a plant-specific example of intercellular communication and coordinated development. According to the canalization hypothesis, the plant hormone auxin serves as polarizing signal that mediates directional channel formation underlying the spatio-temporal vasculature patterning. A necessary part of canalization is a positive feedback between auxin signaling and polarity of the intercellular auxin flow. The cellular and molecular mechanisms of this process are still poorly understood, not the least, because of a lack of a suitable model system. We show that the main genetic model plant, Arabidopsis (Arabidopsis thaliana) can be used to study the canalization during vascular cambium regeneration and new vasculature formation. We monitored localized auxin responses, directional auxin-transport channels formation, and establishment of new vascular cambium polarity during regenerative processes after stem wounding. The increased auxin response above and around the wound preceded the formation of PIN1 auxin transporter-marked channels from the primarily homogenous tissue and the transient, gradual changes in PIN1 localization preceded the polarity of newly formed vascular tissue. Thus, Arabidopsis is a useful model for studies of coordinated tissue polarization and vasculature formation after wounding allowing for genetic and mechanistic dissection of the canalization hypothesis.
AU - Mazur, Ewa
AU - Benková, Eva
AU - Friml, Jirí
ID - 1274
JF - Scientific Reports
TI - Vascular cambium regeneration and vessel formation in wounded inflorescence stems of Arabidopsis
VL - 6
ER -
TY - JOUR
AB - The cytochrome (cyt) bc 1 complex is an integral component of the respiratory electron transfer chain sustaining the energy needs of organisms ranging from humans to bacteria. Due to its ubiquitous role in the energy metabolism, both the oxidation and reduction of the enzyme's substrate co-enzyme Q has been studied vigorously. Here, this vast amount of data is reassessed after probing the substrate reduction steps at the Q i-site of the cyt bc 1 complex of Rhodobacter capsulatus using atomistic molecular dynamics simulations. The simulations suggest that the Lys251 side chain could rotate into the Q i-site to facilitate binding of half-protonated semiquinone-a reaction intermediate that is potentially formed during substrate reduction. At this bent pose, the Lys251 forms a salt bridge with the Asp252, thus making direct proton transfer possible. In the neutral state, the lysine side chain stays close to the conserved binding location of cardiolipin (CL). This back-and-forth motion between the CL and Asp252 indicates that Lys251 functions as a proton shuttle controlled by pH-dependent negative feedback. The CL/K/D switching, which represents a refinement to the previously described CL/K pathway, fine-tunes the proton transfer process. Lastly, the simulation data was used to formulate a mechanism for reducing the substrate at the Q i-site.
AU - Postila, Pekka
AU - Kaszuba, Karol
AU - Kuleta, Patryk
AU - Vattulainen, Ilpo
AU - Sarewicz, Marcin
AU - Osyczka, Artur
AU - Róg, Tomasz
ID - 1276
JF - Scientific Reports
TI - Atomistic determinants of co-enzyme Q reduction at the Qi-site of the cytochrome bc1 complex
VL - 6
ER -
TY - JOUR
AB - The Arabidopsis thaliana endogenous elicitor peptides (AtPeps) are released into the apoplast after cellular damage caused by pathogens or wounding to induce innate immunity by direct binding to the membrane-localized leucine-rich repeat receptor kinases, PEP RECEPTOR1 (PEPR1) and PEPR2. Although the PEPR-mediated signaling components and responses have been studied extensively, the contributions of the subcellular localization and dynamics of the active PEPRs remain largely unknown. We used live-cell imaging of the fluorescently labeled and bioactive pep1 to visualize the intracellular behavior of the PEPRs in the Arabidopsis root meristem. We found that AtPep1 decorated the plasma membrane (PM) in a receptor-dependent manner and cointernalized with PEPRs. Trafficking of the AtPep1-PEPR1 complexes to the vacuole required neither the trans-Golgi network/early endosome (TGN/EE)-localized vacuolar H+ -ATPase activity nor the function of the brefeldin A-sensitive ADP-ribosylation factor-guanine exchange factors (ARF-GEFs). In addition, AtPep1 and different TGN/EE markers colocalized only rarely, implying that the intracellular route of this receptor-ligand pair is largely independent of the TGN/EE. Inducible overexpression of the Arabidopsis clathrin coat disassembly factor, Auxilin2, which inhibits clathrin-mediated endocytosis (CME), impaired the AtPep1-PEPR1 internalization and compromised AtPep1-mediated responses. Our results show that clathrin function at the PM is required to induce plant defense responses, likely through CME of cell surface-located signaling components.
AU - Ortiz Morea, Fausto
AU - Savatin, Daniel
AU - Dejonghe, Wim
AU - Kumar, Rahul
AU - Luo, Yu
AU - Adamowski, Maciek
AU - Van Begin, Jos
AU - Dressano, Keini
AU - De Oliveira, Guilherme
AU - Zhao, Xiuyang
AU - Lu, Qing
AU - Madder, Annemieke
AU - Friml, Jirí
AU - De Moura, Daniel
AU - Russinova, Eugenia
ID - 1277
IS - 39
JF - PNAS
TI - Danger-associated peptide signaling in Arabidopsis requires clathrin
VL - 113
ER -
TY - JOUR
AB - Adaptations of vestibulo-ocular and optokinetic response eye movements have been studied as an experimental model of cerebellum-dependent motor learning. Several previous physiological and pharmacological studies have consistently suggested that the cerebellar flocculus (FL) Purkinje cells (P-cells) and the medial vestibular nucleus (MVN) neurons targeted by FL (FL-targeted MVN neurons) may respectively maintain the memory traces of short- and long-term adaptation. To study the basic structures of the FL-MVN synapses by light microscopy (LM) and electron microscopy (EM), we injected green florescence protein (GFP)-expressing lentivirus into FL to anterogradely label the FL P-cell axons in C57BL/6J mice. The FL P-cell axonal boutons were distributed in the magnocellular MVN and in the border region of parvocellular MVN and prepositus hypoglossi (PrH). In the magnocellular MVN, the FL-P cell axons mainly terminated on somata and proximal dendrites. On the other hand, in the parvocellular MVN/PrH, the FL P-cell axonal synaptic boutons mainly terminated on the relatively small-diameter (< 1 μm) distal dendrites of MVN neurons, forming symmetrical synapses. The majority of such parvocellular MVN/PrH neurons were determined to be glutamatergic by immunocytochemistry and in-situ hybridization of GFP expressing transgenic mice. To further examine the spatial relationship between the synapses of FL P-cells and those of vestibular nerve on the neurons of the parvocellular MVN/ PrH, we added injections of biotinylated dextran amine into the semicircular canal and anterogradely labeled vestibular nerve axons in some mice. The MVN dendrites receiving the FL P-cell axonal synaptic boutons often closely apposed vestibular nerve synaptic boutons in both LM and EM studies. Such a partial overlap of synaptic boutons of FL P-cell axons with those of vestibular nerve axons in the distal dendrites of MVN neurons suggests that inhibitory synapses of FL P-cells may influence the function of neighboring excitatory synapses of vestibular nerve in the parvocellular MVN/PrH neurons.
AU - Matsuno, Hitomi
AU - Kudoh, Moeko
AU - Watakabe, Akiya
AU - Yamamori, Tetsuo
AU - Shigemoto, Ryuichi
AU - Nagao, Soichi
ID - 1278
IS - 10
JF - PLoS One
TI - Distribution and structure of synapses on medial vestibular nuclear neurons targeted by cerebellar flocculus purkinje cells and vestibular nerve in mice: Light and electron microscopy studies
VL - 11
ER -
TY - JOUR
AB - During hippocampal sharp wave/ripple (SWR) events, previously occurring, sensory inputdriven neuronal firing patterns are replayed. Such replay is thought to be important for plasticity- related processes and consolidation of memory traces. It has previously been shown that the electrical stimulation-induced disruption of SWR events interferes with learning in rodents in different experimental paradigms. On the other hand, the cognitive map theory posits that the plastic changes of the firing of hippocampal place cells constitute the electrophysiological counterpart of the spatial learning, observable at the behavioral level. Therefore, we tested whether intact SWR events occurring during the sleep/rest session after the first exploration of a novel environment are needed for the stabilization of the CA1 code, which process requires plasticity. We found that the newly-formed representation in the CA1 has the same level of stability with optogenetic SWR blockade as with a control manipulation that delivered the same amount of light into the brain. Therefore our results suggest that at least in the case of passive exploratory behavior, SWR-related plasticity is dispensable for the stability of CA1 ensembles.
AU - Kovács, Krisztián
AU - O'Neill, Joseph
AU - Schönenberger, Philipp
AU - Penttonen, Markku
AU - Rangel Guerrero, Dámaris K
AU - Csicsvari, Jozsef L
ID - 1279
IS - 10
JF - PLoS One
TI - Optogenetically blocking sharp wave ripple events in sleep does not interfere with the formation of stable spatial representation in the CA1 area of the hippocampus
VL - 11
ER -
TY - JOUR
AB - We prove the Wigner-Dyson-Mehta conjecture at fixed energy in the bulk of the spectrum for generalized symmetric and Hermitian Wigner matrices. Previous results concerning the universality of random matrices either require an averaging in the energy parameter or they hold only for Hermitian matrices if the energy parameter is fixed. We develop a homogenization theory of the Dyson Brownian motion and show that microscopic universality follows from mesoscopic statistics.
AU - Bourgade, Paul
AU - Erdös, László
AU - Yau, Horngtzer
AU - Yin, Jun
ID - 1280
IS - 10
JF - Communications on Pure and Applied Mathematics
TI - Fixed energy universality for generalized wigner matrices
VL - 69
ER -
TY - JOUR
AB - Plants are able to modulate root growth and development to optimize their nitrogen nutrition. In Arabidopsis (Arabidopsis thaliana), the adaptive root response to nitrate (NO3 -) depends on the NRT1.1/NPF6.3 transporter/sensor. NRT1.1 represses emergence of lateral root primordia (LRPs) at low concentration or absence of NO3 - through its auxin transport activity that lowers auxin accumulation in LR. However, these functional data strongly contrast with the known transcriptional regulation of NRT1.1, which is markedly repressed in LRPs in the absence of NO3 -. To explain this discrepancy, we investigated in detail the spatiotemporal expression pattern of the NRT1.1 protein during LRP development and combined local transcript analysis with the use of transgenic lines expressing tagged NRT1.1 proteins. Our results show that although NO3 - stimulates NRT1.1 transcription and probably mRNA stability both in primary root tissues and in LRPs, it acts differentially on protein accumulation, depending on the tissues considered with stimulation in cortex and epidermis of the primary root and a strong repression in LRPs and to a lower extent at the primary root tip. This demonstrates that NRT1.1 is strongly regulated at the posttranscriptional level by tissue-specific mechanisms. These mechanisms are crucial for controlling the large palette of adaptive responses to NO3 - mediated by NRT1.1 as they ensure that the protein is present in the proper tissue under the specific conditions where it plays a signaling role in this particular tissue.
AU - Bouguyon, Eléonore
AU - Perrine Walker, Francine
AU - Pervent, Marjorie
AU - Rochette, Juliette
AU - Cuesta, Candela
AU - Benková, Eva
AU - Martinière, Alexandre
AU - Bach, Lien
AU - Krouk, Gabriel
AU - Gojon, Alain
AU - Nacry, Philippe
ID - 1281
IS - 2
JF - Plant Physiology
TI - Nitrate controls root development through posttranscriptional regulation of the NRT1.1/NPF6.3 transporter sensor
VL - 172
ER -
TY - JOUR
AB - We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial–Meshulam model Xk(n, p) of random k-dimensional simplicial complexes on n vertices. We show that for p = Ω(logn/n), the eigenvalues of each of the matrices are a.a.s. concentrated around two values. The main tool, which goes back to the work of Garland, are arguments that relate the eigenvalues of these matrices to those of graphs that arise as links of (k - 2)-dimensional faces. Garland’s result concerns the Laplacian; we develop an analogous result for the adjacency matrix. The same arguments apply to other models of random complexes which allow for dependencies between the choices of k-dimensional simplices. In the second part of the paper, we apply this to the question of possible higher-dimensional analogues of the discrete Cheeger inequality, which in the classical case of graphs relates the eigenvalues of a graph and its edge expansion. It is very natural to ask whether this generalizes to higher dimensions and, in particular, whether the eigenvalues of the higher-dimensional Laplacian capture the notion of coboundary expansion—a higher-dimensional generalization of edge expansion that arose in recent work of Linial and Meshulam and of Gromov; this question was raised, for instance, by Dotterrer and Kahle. We show that this most straightforward version of a higher-dimensional discrete Cheeger inequality fails, in quite a strong way: For every k ≥ 2 and n ∈ N, there is a k-dimensional complex Yn k on n vertices that has strong spectral expansion properties (all nontrivial eigenvalues of the normalised k-dimensional Laplacian lie in the interval [1−O(1/√1), 1+0(1/√1]) but whose coboundary expansion is bounded from above by O(log n/n) and so tends to zero as n → ∞; moreover, Yn k can be taken to have vanishing integer homology in dimension less than k.
AU - Gundert, Anna
AU - Wagner, Uli
ID - 1282
IS - 2
JF - Israel Journal of Mathematics
TI - On eigenvalues of random complexes
VL - 216
ER -
TY - JOUR
AB - We use recently developed angulon theory [R. Schmidt and M. Lemeshko, Phys. Rev. Lett. 114, 203001 (2015)PRLTAO0031-900710.1103/PhysRevLett.114.203001] to study the rotational spectrum of a cyanide molecular anion immersed into Bose-Einstein condensates of rubidium and strontium. Based on ab initio potential energy surfaces, we provide a detailed study of the rotational Lamb shift and many-body-induced fine structure which arise due to dressing of molecular rotation by a field of phonon excitations. We demonstrate that the magnitude of these effects is large enough in order to be observed in modern experiments on cold molecular ions. Furthermore, we introduce a novel method to construct pseudopotentials starting from the ab initio potential energy surfaces, which provides a means to obtain effective coupling constants for low-energy polaron models.
AU - Midya, Bikashkali
AU - Tomza, Michał
AU - Schmidt, Richard
AU - Lemeshko, Mikhail
ID - 1286
IS - 4
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Rotation of cold molecular ions inside a Bose-Einstein condensate
VL - 94
ER -
TY - JOUR
AB - A planar waveguide with an impedance boundary, composed of nonperfect metallic plates, and with passive or active dielectric filling, is considered. We show the possibility of selective mode guiding and amplification when a homogeneous pump is added to the dielectric and analyze differences in TE and TM mode propagation. Such a non-conservative system is also shown to feature exceptional points for specific and experimentally tunable parameters, which are described for a particular case of transparent dielectric.
AU - Midya, Bikashkali
AU - Konotop, Vladimir
ID - 1287
IS - 20
JF - Optics Letters
TI - Modes and exceptional points in waveguides with impedance boundary conditions
VL - 41
ER -
TY - JOUR
AB - Aiming at the automatic diagnosis of tumors using narrow band imaging (NBI) magnifying endoscopic (ME) images of the stomach, we combine methods from image processing, topology, geometry, and machine learning to classify patterns into three classes: oval, tubular and irregular. Training the algorithm on a small number of images of each type, we achieve a high rate of correct classifications. The analysis of the learning algorithm reveals that a handful of geometric and topological features are responsible for the overwhelming majority of decisions.
AU - Dunaeva, Olga
AU - Edelsbrunner, Herbert
AU - Lukyanov, Anton
AU - Machin, Michael
AU - Malkova, Daria
AU - Kuvaev, Roman
AU - Kashin, Sergey
ID - 1289
IS - 1
JF - Pattern Recognition Letters
TI - The classification of endoscopy images with persistent homology
VL - 83
ER -
TY - JOUR
AB - We developed a competition-based screening strategy to identify compounds that invert the selective advantage of antibiotic resistance. Using our assay, we screened over 19,000 compounds for the ability to select against the TetA tetracycline-resistance efflux pump in Escherichia coli and identified two hits, β-thujaplicin and disulfiram. Treating a tetracycline-resistant population with β-thujaplicin selects for loss of the resistance gene, enabling an effective second-phase treatment with doxycycline.
AU - Stone, Laura
AU - Baym, Michael
AU - Lieberman, Tami
AU - Chait, Remy P
AU - Clardy, Jon
AU - Kishony, Roy
ID - 1290
IS - 11
JF - Nature Chemical Biology
TI - Compounds that select against the tetracycline-resistance efflux pump
VL - 12
ER -
TY - JOUR
AB - We consider Ising models in two and three dimensions, with short range ferromagnetic and long range, power-law decaying, antiferromagnetic interactions. We let J be the ratio between the strength of the ferromagnetic to antiferromagnetic interactions. The competition between these two kinds of interactions induces the system to form domains of minus spins in a background of plus spins, or vice versa. If the decay exponent p of the long range interaction is larger than dÂ +Â 1, with d the space dimension, this happens for all values of J smaller than a critical value Jc(p), beyond which the ground state is homogeneous. In this paper, we give a characterization of the infinite volume ground states of the system, for pÂ >Â 2d and J in a left neighborhood of Jc(p). In particular, we prove that the quasi-one-dimensional states consisting of infinite stripes (dÂ =Â 2) or slabs (dÂ =Â 3), all of the same optimal width and orientation, and alternating magnetization, are infinite volume ground states. Our proof is based on localization bounds combined with reflection positivity.
AU - Giuliani, Alessandro
AU - Seiringer, Robert
ID - 1291
IS - 3
JF - Communications in Mathematical Physics
TI - Periodic striped ground states in Ising models with competing interactions
VL - 347
ER -
TY - JOUR
AB - We give explicit formulas and algorithms for the computation of the Thurston–Bennequin invariant of a nullhomologous Legendrian knot on a page of a contact open book and on Heegaard surfaces in convex position. Furthermore, we extend the results to rationally nullhomologous knots in arbitrary 3-manifolds.
AU - Durst, Sebastian
AU - Kegel, Marc
AU - Klukas, Mirko D
ID - 1292
IS - 2
JF - Acta Mathematica Hungarica
TI - Computing the Thurston–Bennequin invariant in open books
VL - 150
ER -
TY - JOUR
AB - For a graph G with p vertices the closed convex cone S⪰0(G) consists of all real positive semidefinite p×p matrices whose sparsity pattern is given by G, that is, those matrices with zeros in the off-diagonal entries corresponding to nonedges of G. The extremal rays of this cone and their associated ranks have applications to matrix completion problems, maximum likelihood estimation in Gaussian graphical models in statistics, and Gauss elimination for sparse matrices. While the maximum rank of an extremal ray in S⪰0(G), known as the sparsity order of G, has been characterized for different classes of graphs, we here study all possible extremal ranks of S⪰0(G). We investigate when the geometry of the (±1)-cut polytope of G yields a polyhedral characterization of the set of extremal ranks of S⪰0(G). For a graph G without K5 minors, we show that appropriately chosen normal vectors to the facets of the (±1)-cut polytope of G specify the off-diagonal entries of extremal matrices in S⪰0(G). We also prove that for appropriately chosen scalars the constant term of the linear equation of each facet-supporting hyperplane is the rank of its corresponding extremal matrix in S⪰0(G). Furthermore, we show that if G is series-parallel then this gives a complete characterization of all possible extremal ranks of S⪰0(G). Consequently, the sparsity order problem for series-parallel graphs can be solved in terms of polyhedral geometry.
AU - Solus, Liam T
AU - Uhler, Caroline
AU - Yoshida, Ruriko
ID - 1293
JF - Linear Algebra and Its Applications
TI - Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without K5 minors
VL - 509
ER -
TY - JOUR
AB - Direct reciprocity is a major mechanism for the evolution of cooperation. Several classical studies have suggested that humans should quickly learn to adopt reciprocal strategies to establish mutual cooperation in repeated interactions. On the other hand, the recently discovered theory of ZD strategies has found that subjects who use extortionate strategies are able to exploit and subdue cooperators. Although such extortioners have been predicted to succeed in any population of adaptive opponents, theoretical follow-up studies questioned whether extortion can evolve in reality. However, most of these studies presumed that individuals have similar strategic possibilities and comparable outside options, whereas asymmetries are ubiquitous in real world applications. Here we show with a model and an economic experiment that extortionate strategies readily emerge once subjects differ in their strategic power. Our experiment combines a repeated social dilemma with asymmetric partner choice. In our main treatment there is one randomly chosen group member who is unilaterally allowed to exchange one of the other group members after every ten rounds of the social dilemma. We find that this asymmetric replacement opportunity generally promotes cooperation, but often the resulting payoff distribution reflects the underlying power structure. Almost half of the subjects in a better strategic position turn into extortioners, who quickly proceed to exploit their peers. By adapting their cooperation probabilities consistent with ZD theory, extortioners force their co-players to cooperate without being similarly cooperative themselves. Comparison to non-extortionate players under the same conditions indicates a substantial net gain to extortion. Our results thus highlight how power asymmetries can endanger mutually beneficial interactions, and transform them into exploitative relationships. In particular, our results indicate that the extortionate strategies predicted from ZD theory could play a more prominent role in our daily interactions than previously thought.
AU - Hilbe, Christian
AU - Hagel, Kristin
AU - Milinski, Manfred
ID - 1322
IS - 10
JF - PLoS One
TI - Asymmetric power boosts extortion in an economic experiment
VL - 11
ER -
TY - JOUR
AB - Mossy fiber synapses on CA3 pyramidal cells are 'conditional detonators' that reliably discharge postsynaptic targets. The 'conditional' nature implies that burst activity in dentate gyrus granule cells is required for detonation. Whether single unitary excitatory postsynaptic potentials (EPSPs) trigger spikes in CA3 neurons remains unknown. Mossy fiber synapses exhibit both pronounced short-term facilitation and uniquely large post-tetanic potentiation (PTP). We tested whether PTP could convert mossy fiber synapses from subdetonator into detonator mode, using a recently developed method to selectively and noninvasively stimulate individual presynaptic terminals in rat brain slices. Unitary EPSPs failed to initiate a spike in CA3 neurons under control conditions, but reliably discharged them after induction of presynaptic short-term plasticity. Remarkably, PTP switched mossy fiber synapses into full detonators for tens of seconds. Plasticity-dependent detonation may be critical for efficient coding, storage, and recall of information in the granule cell–CA3 cell network.
AU - Vyleta, Nicholas
AU - Borges Merjane, Carolina
AU - Jonas, Peter M
ID - 1323
JF - eLife
TI - Plasticity-dependent, full detonation at hippocampal mossy fiber–CA3 pyramidal neuron synapses
VL - 5
ER -
TY - CONF
AB - We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.
AU - Brázdil, Tomáš
AU - Forejt, Vojtěch
AU - Kučera, Antonín
AU - Novotny, Petr
ID - 1325
TI - Stability in graphs and games
VL - 59
ER -
TY - CONF
AB - Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff.
AU - Brázdil, Tomáš
AU - Kučera, Antonín
AU - Novotny, Petr
ID - 1326
TI - Optimizing the expected mean payoff in Energy Markov Decision Processes
VL - 9938
ER -
TY - CONF
AB - We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Anchit
AU - Novotny, Petr
ID - 1327
T2 - Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems
TI - Stochastic shortest path with energy constraints in POMDPs
ER -
TY - JOUR
AB - Hole spins have gained considerable interest in the past few years due to their potential for fast electrically controlled qubits. Here, we study holes confined in Ge hut wires, a so-far unexplored type of nanostructure. Low-temperature magnetotransport measurements reveal a large anisotropy between the in-plane and out-of-plane g-factors of up to 18. Numerical simulations verify that this large anisotropy originates from a confined wave function of heavy-hole character. A light-hole admixture of less than 1% is estimated for the states of lowest energy, leading to a surprisingly large reduction of the out-of-plane g-factors compared with those for pure heavy holes. Given this tiny light-hole contribution, the spin lifetimes are expected to be very long, even in isotopically nonpurified samples.
AU - Watzinger, Hannes
AU - Kloeffel, Christoph
AU - Vukusic, Lada
AU - Rossell, Marta
AU - Sessi, Violetta
AU - Kukucka, Josip
AU - Kirchschlager, Raimund
AU - Lausecker, Elisabeth
AU - Truhlar, Alisha
AU - Glaser, Martin
AU - Rastelli, Armando
AU - Fuhrer, Andreas
AU - Loss, Daniel
AU - Katsaros, Georgios
ID - 1328
IS - 11
JF - Nano Letters
TI - Heavy-hole states in germanium hut wires
VL - 16
ER -
TY - JOUR
AB - Daphnia species have become models for ecological genomics and exhibit interesting features, such as high phenotypic plasticity and a densely packed genome with many lineage-specific genes. They are also cyclic parthenogenetic, with alternating asexual and sexual cycles and environmental sex determination. Here, we present a de novo transcriptome assembly of over 32,000 D. galeata genes and use it to investigate gene expression in females and spontaneously produced males of two clonal lines derived from lakes in Germany and the Czech Republic. We find that only a low percentage (18%) of genes shows sex-biased expression and that there are many more female-biased gene (FBG) than male-biased gene (MBG). Furthermore, FBGs tend to be more conserved between species than MBGs in both sequence and expression. These patterns may be a consequence of cyclic parthenogenesis leading to a relaxation of purifying selection on MBGs. The two clonal lines show considerable differences in both number and identity of sex-biased genes, suggesting that they may have reproductive strategies differing in their investment in sexual reproduction. Orthologs of key genes in the sex determination and juvenile hormone pathways, which are thought to be important for the transition from asexual to sexual reproduction, are present in D. galeata and highly conserved among Daphnia species.
AU - Huylmans, Ann K
AU - López Ezquerra, Alberto
AU - Parsch, John
AU - Cordellier, Mathilde
ID - 1329
IS - 10
JF - Genome Biology and Evolution
TI - De novo transcriptome assembly and sex-biased gene expression in the cyclical parthenogenetic Daphnia galeata
VL - 8
ER -
TY - JOUR
AB - In this paper we investigate the existence of closed billiard trajectories in not necessarily smooth convex bodies. In particular, we show that if a body K ⊂ Rd has the property that the tangent cone of every non-smooth point q ∉ ∂K is acute (in a certain sense), then there is a closed billiard trajectory in K.
AU - Akopyan, Arseniy
AU - Balitskiy, Alexey
ID - 1330
IS - 2
JF - Israel Journal of Mathematics
TI - Billiards in convex bodies with acute angles
VL - 216
ER -
TY - JOUR
AB - Antibiotic-sensitive and -resistant bacteria coexist in natural environments with low, if detectable, antibiotic concentrations. Except possibly around localized antibiotic sources, where resistance can provide a strong advantage, bacterial fitness is dominated by stresses unaffected by resistance to the antibiotic. How do such mixed and heterogeneous conditions influence the selective advantage or disadvantage of antibiotic resistance? Here we find that sub-inhibitory levels of tetracyclines potentiate selection for or against tetracycline resistance around localized sources of almost any toxin or stress. Furthermore, certain stresses generate alternating rings of selection for and against resistance around a localized source of the antibiotic. In these conditions, localized antibiotic sources, even at high strengths, can actually produce a net selection against resistance to the antibiotic. Our results show that interactions between the effects of an antibiotic and other stresses in inhomogeneous environments can generate pervasive, complex patterns of selection both for and against antibiotic resistance.
AU - Chait, Remy P
AU - Palmer, Adam
AU - Yelin, Idan
AU - Kishony, Roy
ID - 1332
JF - Nature Communications
TI - Pervasive selection for and against antibiotic resistance in inhomogeneous multistress environments
VL - 7
ER -
TY - JOUR
AB - Social dilemmas force players to balance between personal and collective gain. In many dilemmas, such as elected governments negotiating climate-change mitigation measures, the decisions are made not by individual players but by their representatives. However, the behaviour of representatives in social dilemmas has not been investigated experimentally. Here inspired by the negotiations for greenhouse-gas emissions reductions, we experimentally study a collective-risk social dilemma that involves representatives deciding on behalf of their fellow group members. Representatives can be re-elected or voted out after each consecutive collective-risk game. Selfish players are preferentially elected and are hence found most frequently in the "representatives" treatment. Across all treatments, we identify the selfish players as extortioners. As predicted by our mathematical model, their steadfast strategies enforce cooperation from fair players who finally compensate almost completely the deficit caused by the extortionate co-players. Everybody gains, but the extortionate representatives and their groups gain the most.
AU - Milinski, Manfred
AU - Hilbe, Christian
AU - Semmann, Dirk
AU - Sommerfeld, Ralf
AU - Marotzke, Jochem
ID - 1333
JF - Nature Communications
TI - Humans choose representatives who enforce cooperation in social dilemmas through extortion
VL - 7
ER -
TY - JOUR
AB - Hippocampal neurons encode a cognitive map of space. These maps are thought to be updated during learning and in response to changes in the environment through activity-dependent synaptic plasticity. Here we examine how changes in activity influence spatial coding in rats using halorhodopsin-mediated, spatially selective optogenetic silencing. Halorhoposin stimulation leads to light-induced suppression in many place cells and interneurons; some place cells increase their firing through disinhibition, whereas some show no effect. We find that place fields of the unaffected subpopulation remain stable. On the other hand, place fields of suppressed place cells were unstable, showing remapping across sessions before and after optogenetic inhibition. Disinhibited place cells had stable maps but sustained an elevated firing rate. These findings suggest that place representation in the hippocampus is constantly governed by activity-dependent processes, and that disinhibition may provide a mechanism for rate remapping.
AU - Schönenberger, Philipp
AU - O'Neill, Joseph
AU - Csicsvari, Jozsef L
ID - 1334
JF - Nature Communications
TI - Activity dependent plasticity of hippocampal place maps
VL - 7
ER -
TY - CONF
AB - In this paper we review various automata-theoretic formalisms for expressing quantitative properties. We start with finite-state Boolean automata that express the traditional regular properties. We then consider weighted ω-automata that can measure the average density of events, which finite-state Boolean automata cannot. However, even weighted ω-automata cannot express basic performance properties like average response time. We finally consider two formalisms of weighted ω-automata with monitors, where the monitors are either (a) counters or (b) weighted automata themselves. We present a translation result to establish that these two formalisms are equivalent. Weighted ω-automata with monitors generalize weighted ω-automata, and can express average response time property. They present a natural, robust, and expressive framework for quantitative specifications, with important decidable properties.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 1335
TI - Quantitative monitor automata
VL - 9837
ER -
TY - JOUR
AB - We present a microelectromechanical system, in which a silicon beam is attached to a comb-drive
actuator, which is used to tune the tension in the silicon beam and thus its resonance frequency. By
measuring the resonance frequencies of the system, we show that the comb-drive actuator and the
silicon beam behave as two strongly coupled resonators. Interestingly, the effective coupling rate
(1.5 MHz) is tunable with the comb-drive actuator (10%) as well as with a side-gate (10%)
placed close to the silicon beam. In contrast, the effective spring constant of the system is insensitive
to either of them and changes only by 60.5%. Finally, we show that the comb-drive actuator
can be used to switch between different coupling rates with a frequency of at least 10 kHz.
AU - Verbiest, Gerard
AU - Xu, Duo
AU - Goldsche, Matthias
AU - Khodkov, Timofiy
AU - Barzanjeh, Shabir
AU - Von Den Driesch, Nils
AU - Buca, Dan
AU - Stampfer, Christoph
ID - 1339
JF - Applied Physics Letter
TI - Tunable mechanical coupling between driven microelectromechanical resonators
VL - 109
ER -
TY - CONF
AB - We study repeated games with absorbing states, a type of two-player, zero-sum concurrent mean-payoff games with the prototypical example being the Big Match of Gillete (1957). These games may not allow optimal strategies but they always have ε-optimal strategies. In this paper we design ε-optimal strategies for Player 1 in these games that use only O(log log T) space. Furthermore, we construct strategies for Player 1 that use space s(T), for an arbitrary small unbounded non-decreasing function s, and which guarantee an ε-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Ω(log T) and it was known that no strategy can use constant space if it is ε-optimal even in the limit superior sense. We also give a complementary lower bound. Furthermore, we also show that no Markov strategy, even extended with finite memory, can ensure value greater than 0 in the Big Match, answering a question posed by Neyman [11].
AU - Hansen, Kristoffer
AU - Ibsen-Jensen, Rasmus
AU - Koucký, Michal
ID - 1340
TI - The big match in small space
VL - 9928
ER -
TY - CONF
AB - In resource allocation games, selfish players share resources that are needed in order to fulfill their objectives. The cost of using a resource depends on the load on it. In the traditional setting, the players make their choices concurrently and in one-shot. That is, a strategy for a player is a subset of the resources. We introduce and study dynamic resource allocation games. In this setting, the game proceeds in phases. In each phase each player chooses one resource. A scheduler dictates the order in which the players proceed in a phase, possibly scheduling several players to proceed concurrently. The game ends when each player has collected a set of resources that fulfills his objective. The cost for each player then depends on this set as well as on the load on the resources in it – we consider both congestion and cost-sharing games. We argue that the dynamic setting is the suitable setting for many applications in practice. We study the stability of dynamic resource allocation games, where the appropriate notion of stability is that of subgame perfect equilibrium, study the inefficiency incurred due to selfish behavior, and also study problems that are particular to the dynamic setting, like constraints on the order in which resources can be chosen or the problem of finding a scheduler that achieves stability.
AU - Avni, Guy
AU - Henzinger, Thomas A
AU - Kupferman, Orna
ID - 1341
TI - Dynamic resource allocation games
VL - 9928
ER -
TY - JOUR
AB - A key aspect of bacterial survival is the ability to evolve while migrating across spatially varying environmental challenges. Laboratory experiments, however, often study evolution in well-mixed systems. Here, we introduce an experimental device, the microbial evolution and growth arena (MEGA)-plate, in which bacteria spread and evolved on a large antibiotic landscape (120 × 60 centimeters) that allowed visual observation of mutation and selection in a migrating bacterial front.While resistance increased consistently, multiple coexisting lineages diversified both phenotypically and genotypically. Analyzing mutants at and behind the propagating front,we found that evolution is not always led by the most resistant mutants; highly resistant mutants may be trapped behindmore sensitive lineages.TheMEGA-plate provides a versatile platformfor studying microbial adaption and directly visualizing evolutionary dynamics.
AU - Baym, Michael
AU - Lieberman, Tami
AU - Kelsic, Eric
AU - Chait, Remy P
AU - Gross, Rotem
AU - Yelin, Idan
AU - Kishony, Roy
ID - 1342
IS - 6304
JF - Science
TI - Spatiotemporal microbial evolution on antibiotic landscapes
VL - 353
ER -
TY - JOUR
AB - The Fermi-Hubbard model is one of the key models of condensed matter physics, which holds a
potential for explaining the mystery of high-temperature superconductivity. Recent progress in
ultracold atoms in optical lattices has paved the way to studying the model’s phase diagram using
the tools of quantum simulation, which emerged as a promising alternative to the numerical
calculations plagued by the infamous sign problem. However, the temperatures achieved using
elaborate laser cooling protocols so far have been too high to show the appearance of
antiferromagnetic (AF) and superconducting quantum phases directly. In this work, we demonstrate
that using the machinery of dissipative quantum state engineering, one can observe the emergence of
the AF order in the Fermi-Hubbard model with fermions in optical lattices. The core of the approach
is to add incoherent laser scattering in such a way that the AF state emerges as the dark state of
the driven-dissipative dynamics. The proposed controlled dissipation channels described in this work
are straightforward to add to already existing experimental setups.
AU - Kaczmarczyk, Jan
AU - Weimer, Hendrik
AU - Lemeshko, Mikhail
ID - 1343
IS - 9
JF - New Journal of Physics
TI - Dissipative preparation of antiferromagnetic order in the Fermi-Hubbard model
VL - 18
ER -
TY - JOUR
AB - Despite being composed of immobile cells, plants reorient along directional stimuli. The hormone auxin is redistributed in stimulated organs leading to differential growth and bending. Auxin application triggers rapid cell wall acidification and elongation of aerial organs of plants, but the molecular players mediating these effects are still controversial. Here we use genetically-encoded pH and auxin signaling sensors, pharmacological and genetic manipulations available for Arabidopsis etiolated hypocotyls to clarify how auxin is perceived and the downstream growth executed. We show that auxin-induced acidification occurs by local activation of H+-ATPases, which in the context of gravity response is restricted to the lower organ side. This auxin-stimulated acidification and growth require TIR1/AFB-Aux/IAA nuclear auxin perception. In addition, auxin-induced gene transcription and specifically SAUR proteins are crucial downstream mediators of this growth. Our study provides strong experimental support for the acid growth theory and clarified the contribution of the upstream auxin perception mechanisms.
AU - Fendrych, Matyas
AU - Leung, Jeffrey
AU - Friml, Jirí
ID - 1344
JF - eLife
TI - TIR1 AFB Aux IAA auxin perception mediates rapid cell wall acidification and growth of Arabidopsis hypocotyls
VL - 5
ER -
TY - JOUR
AB - The electrostatic charge at the inner surface of the plasma membrane is strongly negative in higher organisms. A new study shows that phosphatidylinositol-4-phosphate plays a critical role in establishing plasma membrane surface charge in Arabidopsis, which regulates the correct localization of signalling components.
AU - Molnar, Gergely
AU - Fendrych, Matyas
AU - Friml, Jirí
ID - 1345
JF - Nature Plants
TI - Plasma membrane: Negative attraction
VL - 2
ER -
TY - JOUR
AB - ATP production requires the establishment of an electrochemical proton gradient across the inner mitochondrial membrane. Mitochondrial uncouplers dissipate this proton gradient and disrupt numerous cellular processes, including vesicular trafficking, mainly through energy depletion. Here we show that Endosidin9 (ES9), a novel mitochondrial uncoupler, is a potent inhibitor of clathrin-mediated endocytosis (CME) in different systems and that ES9 induces inhibition of CME not because of its effect on cellular ATP, but rather due to its protonophore activity that leads to cytoplasm acidification. We show that the known tyrosine kinase inhibitor tyrphostinA23, which is routinely used to block CME, displays similar properties, thus questioning its use as a specific inhibitor of cargo recognition by the AP-2 adaptor complex via tyrosine motif-based endocytosis signals. Furthermore, we show that cytoplasm acidification dramatically affects the dynamics and recruitment of clathrin and associated adaptors, and leads to reduction of phosphatidylinositol 4,5-biphosphate from the plasma membrane.
AU - Dejonghe, Wim
AU - Kuenen, Sabine
AU - Mylle, Evelien
AU - Vasileva, Mina K
AU - Keech, Olivier
AU - Viotti, Corrado
AU - Swerts, Jef
AU - Fendrych, Matyas
AU - Ortiz Morea, Fausto
AU - Mishev, Kiril
AU - Delang, Simon
AU - Scholl, Stefan
AU - Zarza, Xavier
AU - Heilmann, Mareike
AU - Kourelis, Jiorgos
AU - Kasprowicz, Jaroslaw
AU - Nguyen, Le
AU - Drozdzecki, Andrzej
AU - Van Houtte, Isabelle
AU - Szatmári, Anna
AU - Majda, Mateusz
AU - Baisa, Gary
AU - Bednarek, Sebastian
AU - Robert, Stéphanie
AU - Audenaert, Dominique
AU - Testerink, Christa
AU - Munnik, Teun
AU - Van Damme, Daniël
AU - Heilmann, Ingo
AU - Schumacher, Karin
AU - Winne, Johan
AU - Friml, Jirí
AU - Verstreken, Patrik
AU - Russinova, Eugenia
ID - 1346
JF - Nature Communications
TI - Mitochondrial uncouplers inhibit clathrin-mediated endocytosis largely through cytoplasmic acidification
VL - 7
ER -
TY - JOUR
AB - During the past 70 years, the quantum theory of angular momentum has been successfully applied to describing the properties of nuclei, atoms, and molecules, and their interactions with each other as well as with external fields. Because of the properties of quantum rotations, the angular-momentum algebra can be of tremendous complexity even for a few interacting particles, such as valence electrons of an atom, not to mention larger many-particle systems. In this work, we study an example of the latter: A rotating quantum impurity coupled to a many-body bosonic bath. In the regime of strong impurity-bath couplings, the problem involves the addition of an infinite number of angular momenta, which renders it intractable using currently available techniques. Here, we introduce a novel canonical transformation that allows us to eliminate the complex angular-momentum algebra from such a class of many-body problems. In addition, the transformation exposes the problem's constants of motion, and renders it solvable exactly in the limit of a slowly rotating impurity. We exemplify the technique by showing that there exists a critical rotational speed at which the impurity suddenly acquires one quantum of angular momentum from the many-particle bath. Such an instability is accompanied by the deformation of the phonon density in the frame rotating along with the impurity.
AU - Schmidt, Richard
AU - Lemeshko, Mikhail
ID - 1347
IS - 1
JF - Physical Review X
TI - Deformation of a quantum many-particle system by a rotating impurity
VL - 6
ER -
TY - CONF
AB - A drawing in the plane (ℝ2) of a graph G = (V,E) equipped with a function γ : V → ℕ is x-bounded if (i) x(u) < x(v) whenever γ(u) < γ(v) and (ii) γ(u) ≤ γ(w) ≤ γ(v), where uv ∈ E and γ(u) ≤ γ(v), whenever x(w) ∈ x(uv), where x(.) denotes the projection to the xaxis.We prove a characterization of isotopy classes of embeddings of connected graphs equipped with γ in the plane containing an x-bounded embedding.Then we present an efficient algorithm, which relies on our result, for testing the existence of an x-bounded embedding if the given graph is a forest.This partially answers a question raised recently by Angelini et al.and Chang et al., and proves that c-planarity testing of flat clustered graphs with three clusters is tractable when the underlying abstract graph is a forest.
AU - Fulek, Radoslav
ID - 1348
TI - Bounded embeddings of graphs in the plane
VL - 9843
ER -
TY - CONF
AB - Crossing fitness valleys is one of the major obstacles to function optimization. In this paper we investigate how the structure of the fitness valley, namely its depth d and length ℓ, influence the runtime of different strategies for crossing these valleys. We present a runtime comparison between the (1+1) EA and two non-elitist nature-inspired algorithms, Strong Selection Weak Mutation (SSWM) and the Metropolis algorithm. While the (1+1) EA has to jump across the valley to a point of higher fitness because it does not accept decreasing moves, the non-elitist algorithms may cross the valley by accepting worsening moves. We show that while the runtime of the (1+1) EA algorithm depends critically on the length of the valley, the runtimes of the non-elitist algorithms depend crucially only on the depth of the valley. In particular, the expected runtime of both SSWM and Metropolis is polynomial in ℓ and exponential in d while the (1+1) EA is efficient only for valleys of small length. Moreover, we show that both SSWM and Metropolis can also efficiently optimize a rugged function consisting of consecutive valleys.
AU - Oliveto, Pietro
AU - Paixao, Tiago
AU - Heredia, Jorge
AU - Sudholt, Dirk
AU - Trubenova, Barbora
ID - 1349
T2 - Proceedings of the Genetic and Evolutionary Computation Conference 2016
TI - When non-elitism outperforms elitism for crossing fitness valleys
ER -
TY - JOUR
AB - The hippocampal CA3 region plays a key role in learning and memory. Recurrent CA3–CA3
synapses are thought to be the subcellular substrate of pattern completion. However, the
synaptic mechanisms of this network computation remain enigmatic. To investigate these mechanisms, we combined functional connectivity analysis with network modeling.
Simultaneous recording fromup to eight CA3 pyramidal neurons revealed that connectivity was sparse, spatially uniform, and highly enriched in disynaptic motifs (reciprocal, convergence,divergence, and chain motifs). Unitary connections were composed of one or two synaptic contacts, suggesting efficient use of postsynaptic space. Real-size modeling indicated that CA3 networks with sparse connectivity, disynaptic motifs, and single-contact connections robustly generated pattern completion.Thus, macro- and microconnectivity contribute to efficient
memory storage and retrieval in hippocampal networks.
AU - Guzmán, José
AU - Schlögl, Alois
AU - Frotscher, Michael
AU - Jonas, Peter M
ID - 1350
IS - 6304
JF - Science
TI - Synaptic mechanisms of pattern completion in the hippocampal CA3 network
VL - 353
ER -
TY - JOUR
AB - We study the interplay of nematic and superconducting order in the two-dimensional Hubbard model and show that they can coexist, especially when superconductivity is not the energetically dominant phase. Due to a breaking of the C4 symmetry, the coexisting phase inherently contains admixture of the s-wave pairing components. As a result, the superconducting gap exhibits nonstandard features including changed nodal directions. Our results also show that in the optimally doped regime the pure superconducting phase is typically unstable towards developing nematicity (breaking of the C4 symmetry). This has implications for the cuprate high-Tc superconductors, for which in this regime the so-called intertwined orders have recently been observed. Namely, the coexisting phase may be viewed as a precursor to such more involved patterns of symmetry breaking.
AU - Kaczmarczyk, Jan
AU - Schickling, Tobias
AU - Bünemann, Jörg
ID - 1352
IS - 8
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Coexistence of nematic order and superconductivity in the Hubbard model
VL - 94
ER -
TY - JOUR
AB - We characterize absorption in finite idempotent algebras by means of Jónsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations.
AU - Barto, Libor
AU - Kazda, Alexandr
ID - 1353
IS - 5
JF - International Journal of Algebra and Computation
TI - Deciding absorption
VL - 26
ER -
TY - JOUR
AB - Fabrication processes involving anhydrous hydrofluoric vapor etching are developed to create high-Q aluminum superconducting microwave resonators on free-standing silicon membranes formed from a silicon-on-insulator wafer. Using this fabrication process, a high-impedance 8.9-GHz coil resonator is coupled capacitively with a large participation ratio to a 9.7-MHz micromechanical resonator. Two-tone microwave spectroscopy and radiation pressure backaction are used to characterize the coupled system in a dilution refrigerator down to temperatures of Tf=11 mK, yielding a measured electromechanical vacuum coupling rate of g0/2π=24.6 Hz and a mechanical resonator Q factor of Qm=1.7×107. Microwave backaction cooling of the mechanical resonator is also studied, with a minimum phonon occupancy of nm≈16 phonons being realized at an elevated fridge temperature of Tf=211 mK.
AU - Dieterle, Paul
AU - Kalaee, Mahmoud
AU - Fink, Johannes M
AU - Painter, Oskar
ID - 1354
IS - 1
JF - Physical Review Applied
TI - Superconducting cavity electromechanics on a silicon-on-insulator platform
VL - 6
ER -
TY - JOUR
AB - Radiation pressure has recently been used to effectively couple the quantum motion of mechanical elements to the fields of optical or microwave light. Integration of all three degrees of freedom—mechanical, optical and microwave—would enable a quantum interconnect between microwave and optical quantum systems. We present a platform based on silicon nitride nanomembranes for integrating superconducting microwave circuits with planar acoustic and optical devices such as phononic and photonic crystals. Using planar capacitors with vacuum gaps of 60 nm and spiral inductor coils of micron pitch we realize microwave resonant circuits with large electromechanical coupling to planar acoustic structures of nanoscale dimensions and femtoFarad motional capacitance. Using this enhanced coupling, we demonstrate microwave backaction cooling of the 4.48 MHz mechanical resonance of a nanobeam to an occupancy as low as 0.32. These results indicate the viability of silicon nitride nanomembranes as an all-in-one substrate for quantum electro-opto-mechanical experiments.
AU - Fink, Johannes M
AU - Kalaee, Mahmoud
AU - Pitanti, Alessandro
AU - Norte, Richard
AU - Heinzle, Lukas
AU - Davanço, Marcelo
AU - Srinivasan, Kartik
AU - Painter, Oskar
ID - 1355
JF - Nature Communications
TI - Quantum electromechanics on silicon nitride nanomembranes
VL - 7
ER -
TY - JOUR
AU - Barton, Nicholas H
ID - 1356
IS - 1
JF - Genetics
TI - Sewall Wright on evolution in Mendelian populations and the “Shifting Balance”
VL - 202
ER -
TY - JOUR
AU - Barton, Nicholas H
ID - 1357
IS - 3
JF - Genetics
TI - Richard Hudson and Norman Kaplan on the coalescent process
VL - 202
ER -
TY - JOUR
AB - Gene regulation relies on the specificity of transcription factor (TF)–DNA interactions. Limited specificity may lead to crosstalk: a regulatory state in which a gene is either incorrectly activated due to noncognate TF–DNA interactions or remains erroneously inactive. As each TF can have numerous interactions with noncognate cis-regulatory elements, crosstalk is inherently a global problem, yet has previously not been studied as such. We construct a theoretical framework to analyse the effects of global crosstalk on gene regulation. We find that crosstalk presents a significant challenge for organisms with low-specificity TFs, such as metazoans. Crosstalk is not easily mitigated by known regulatory schemes acting at equilibrium, including variants of cooperativity and combinatorial regulation. Our results suggest that crosstalk imposes a previously unexplored global constraint on the functioning and evolution of regulatory networks, which is qualitatively distinct from the known constraints that act at the level of individual gene regulatory elements.
AU - Friedlander, Tamar
AU - Prizak, Roshan
AU - Guet, Calin C
AU - Barton, Nicholas H
AU - Tkacik, Gasper
ID - 1358
JF - Nature Communications
TI - Intrinsic limits to gene regulation by global crosstalk
VL - 7
ER -
TY - JOUR
AB - The role of gene interactions in the evolutionary process has long
been controversial. Although some argue that they are not of
importance, because most variation is additive, others claim that
their effect in the long term can be substantial. Here, we focus on
the long-term effects of genetic interactions under directional
selection assuming no mutation or dominance, and that epistasis is
symmetrical overall. We ask by how much the mean of a complex
trait can be increased by selection and analyze two extreme
regimes, in which either drift or selection dominate the dynamics
of allele frequencies. In both scenarios, epistatic interactions affect
the long-term response to selection by modulating the additive
genetic variance. When drift dominates, we extend Robertson
’
s
[Robertson A (1960)
Proc R Soc Lond B Biol Sci
153(951):234
−
249]
argument to show that, for any form of epistasis, the total response
of a haploid population is proportional to the initial total genotypic
variance. In contrast, the total response of a diploid population is
increased by epistasis, for a given initial genotypic variance. When
selection dominates, we show that the total selection response can
only be increased by epistasis when s
ome initially deleterious alleles
become favored as the genetic background changes. We find a sim-
ple approximation for this effect and show that, in this regime, it is
the structure of the genotype - phenotype map that matters and not
the variance components of the population.
AU - Paixao, Tiago
AU - Barton, Nicholas H
ID - 1359
IS - 16
JF - PNAS
TI - The effect of gene interactions on the long-term response to selection
VL - 113
ER -
TY - JOUR
AB - We apply the technique of Károly Bezdek and Daniel Bezdek to study billiard trajectories in convex bodies, when the length is measured with a (possibly asymmetric) norm. We prove a lower bound for the length of the shortest closed billiard trajectory, related to the non-symmetric Mahler problem. With this technique we are able to give short and elementary proofs to some known results.
AU - Akopyan, Arseniy
AU - Balitskiy, Alexey
AU - Karasev, Roman
AU - Sharipova, Anastasia
ID - 1360
IS - 10
JF - Proceedings of the American Mathematical Society
TI - Elementary approach to closed billiard trajectories in asymmetric normed spaces
VL - 144
ER -
TY - CONF
AB - We propose a novel surface-only technique for simulating incompressible, inviscid and uniform-density liquids with surface tension in three dimensions. The liquid surface is captured by a triangle mesh on which a Lagrangian velocity field is stored. Because advection of the velocity field may violate the incompressibility condition, we devise an orthogonal projection technique to remove the divergence while requiring the evaluation of only two boundary integrals. The forces of surface tension, gravity, and solid contact are all treated by a boundary element solve, allowing us to perform detailed simulations of a wide range of liquid phenomena, including waterbells, droplet and jet collisions, fluid chains, and crown splashes.
AU - Da, Fang
AU - Hahn, David
AU - Batty, Christopher
AU - Wojtan, Christopher J
AU - Grinspun, Eitan
ID - 1361
IS - 4
TI - Surface only liquids
VL - 35
ER -
TY - CONF
AB - We present a boundary element based method for fast simulation of brittle fracture. By introducing simplifying assumptions that allow us to quickly estimate stress intensities and opening displacements during crack propagation, we build a fracture algorithm where the cost of each time step scales linearly with the length of the crackfront. The transition from a full boundary element method to our faster variant is possible at the beginning of any time step. This allows us to build a hybrid method, which uses the expensive but more accurate BEM while the number of degrees of freedom is low, and uses the fast method once that number exceeds a given threshold as the crack geometry becomes more complicated. Furthermore, we integrate this fracture simulation with a standard rigid-body solver. Our rigid-body coupling solves a Neumann boundary value problem by carefully separating translational, rotational and deformational components of the collision forces and then applying a Tikhonov regularizer to the resulting linear system. We show that our method produces physically reasonable results in standard test cases and is capable of dealing with complex scenes faster than previous finite- or boundary element approaches.
AU - Hahn, David
AU - Wojtan, Christopher J
ID - 1362
IS - 4
TI - Fast approximations for boundary element based brittle fracture simulation
VL - 35
ER -
TY - CONF
AB - When aiming to seamlessly integrate a fluid simulation into a larger scenario (like an open ocean), careful attention must be paid to boundary conditions. In particular, one must implement special "non-reflecting" boundary conditions, which dissipate out-going waves as they exit the simulation. Unfortunately, the state of the art in non-reflecting boundary conditions (perfectly-matched layers, or PMLs) only permits trivially simple inflow/outflow conditions, so there is no reliable way to integrate a fluid simulation into a more complicated environment like a stormy ocean or a turbulent river. This paper introduces the first method for combining nonreflecting boundary conditions based on PMLs with inflow/outflow boundary conditions that vary arbitrarily throughout space and time. Our algorithm is a generalization of stateof- the-art mean-flow boundary conditions in the computational fluid dynamics literature, and it allows for seamless integration of a fluid simulation into much more complicated environments. Our method also opens the door for previously-unseen postprocess effects like retroactively changing the location of solid obstacles, and locally increasing the visual detail of a pre-existing simulation.
AU - Bojsen-Hansen, Morten
AU - Wojtan, Christopher J
ID - 1363
IS - 4
TI - Generalized non-reflecting boundaries for fluid re-simulation
VL - 35
ER -
TY - CONF
AB - We present a computational method for designing wire sculptures consisting of interlocking wires. Our method allows the computation of aesthetically pleasing structures that are structurally stable, efficiently fabricatable with a 2D wire bending machine, and assemblable without the need of additional connectors. Starting from a set of planar contours provided by the user, our method automatically tests for the feasibility of a design, determines a discrete ordering of wires at intersection points, and optimizes for the rest shape of the individual wires to maximize structural stability under frictional contact. In addition to their application to art, wire sculptures present an extremely efficient and fast alternative for low-fidelity rapid prototyping because manufacturing time and required material linearly scales with the physical size of objects. We demonstrate the effectiveness of our approach on a varied set of examples, all of which we fabricated.
AU - Miguel Villalba, Eder
AU - Lepoutre, Mathias
AU - Bickel, Bernd
ID - 1364
IS - 4
TI - Computational design of stable planar-rod structures
VL - 35
ER -
TY - CONF
AB - A memory-hard function (MHF) f is equipped with a space cost σ and time cost τ parameter such that repeatedly computing fσ,τ on an application specific integrated circuit (ASIC) is not economically advantageous relative to a general purpose computer. Technically we would like that any (generalized) circuit for evaluating an iMHF fσ,τ has area × time (AT) complexity at Θ(σ2 ∗ τ). A data-independent MHF (iMHF) has the added property that it can be computed with almost optimal memory and time complexity by an algorithm which accesses memory in a pattern independent of the input value. Such functions can be specified by fixing a directed acyclic graph (DAG) G on n = Θ(σ ∗ τ) nodes representing its computation graph. In this work we develop new tools for analyzing iMHFs. First we define and motivate a new complexity measure capturing the amount of energy (i.e. electricity) required to compute a function. We argue that, in practice, this measure is at least as important as the more traditional AT-complexity. Next we describe an algorithm A for repeatedly evaluating an iMHF based on an arbitrary DAG G. We upperbound both its energy and AT complexities per instance evaluated in terms of a certain combinatorial property of G. Next we instantiate our attack for several general classes of DAGs which include those underlying many of the most important iMHF candidates in the literature. In particular, we obtain the following results which hold for all choices of parameters σ and τ (and thread-count) such that n = σ ∗ τ. -The Catena-Dragonfly function of [FLW13] has AT and energy complexities O(n1.67). -The Catena-Butterfly function of [FLW13] has complexities is O(n1.67). -The Double-Buffer and the Linear functions of [CGBS16] both have complexities in O(n1.67). -The Argon2i function of [BDK15] (winner of the Password Hashing Competition [PHC]) has complexities O(n7/4 log(n)). -The Single-Buffer function of [CGBS16] has complexities O(n7/4 log(n)). -Any iMHF can be computed by an algorithm with complexities O(n2/ log1 −ε(n)) for all ε > 0. In particular when τ = 1 this shows that the goal of constructing an iMHF with AT-complexity Θ(σ2 ∗ τ ) is unachievable. Along the way we prove a lemma upper-bounding the depth-robustness of any DAG which may prove to be of independent interest.
AU - Alwen, Joel F
AU - Blocki, Jeremiah
ID - 1365
TI - Efficiently computing data-independent memory-hard functions
VL - 9815
ER -
TY - CONF
AB - We study the problem of devising provably secure PRNGs with input based on the sponge paradigm. Such constructions are very appealing, as efficient software/hardware implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES 2010), fails to achieve the security notion of robustness recently considered by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic, and thus there are high-entropy input distributions on which the construction fails to extract random bits, and (2) The construction is not forward secure, and presented solutions aiming at restoring forward security have not been rigorously analyzed. We propose a seeded variant of Bertoni et al.’s PRNG with input which we prove secure in the sense of robustness, delivering in particular concrete security bounds. On the way, we make what we believe to be an important conceptual contribution, developing a variant of the security framework of Dodis et al. tailored at the ideal permutation model that captures PRNG security in settings where the weakly random inputs are provided from a large class of possible adversarial samplers which are also allowed to query the random permutation. As a further application of our techniques, we also present an efficient sponge-based key-derivation function (which can be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions.
AU - Gazi, Peter
AU - Tessaro, Stefano
ID - 1366
TI - Provably robust sponge-based PRNGs and KDFs
VL - 9665
ER -
TY - JOUR
AB - Superconductivity in heavy-fermion systems has an unconventional nature and is considered to originate from the universal features of the electronic structure. Here, the Anderson lattice model is studied by means of the full variational Gutzwiller wave function incorporating nonlocal effects of the on-site interaction. We show that the d-wave superconducting ground state can be driven solely by interelectronic correlations. The proposed microscopic mechanism leads to a multigap superconductivity with the dominant contribution due to f electrons and in the dx2−y2-wave channel. Our results rationalize several important observations for CeCoIn5.
AU - Wysokiński, Marcin
AU - Kaczmarczyk, Jan
AU - Spałek, Jozef
ID - 1368
IS - 2
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Correlation driven d wave superconductivity in Anderson lattice model: Two gaps
VL - 94
ER -
TY - CONF
AB - We introduce a new loss function for the weakly-supervised training of semantic image segmentation models based on three guiding principles: to seed with weak localization cues, to expand objects based on the information about which classes can occur in an image, and to constrain the segmentations to coincide with object boundaries. We show experimentally that training a deep convolutional neural network using the proposed loss function leads to substantially better segmentations than previous state-of-the-art methods on the challenging PASCAL VOC 2012 dataset. We furthermore give insight into the working mechanism of our method by a detailed experimental study that illustrates how the segmentation quality is affected by each term of the proposed loss function as well as their combinations.
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 1369
TI - Seed, expand and constrain: Three principles for weakly-supervised image segmentation
VL - 9908
ER -
TY - JOUR
AB - We study coherent phonon oscillations and tunneling between two coupled nonlinear nanomechanical resonators. We show that the coupling between two nanomechanical resonators creates an effective phonon Josephson junction, which exhibits two different dynamical behaviors: Josephson oscillation (phonon-Rabi oscillation) and macroscopic self-trapping (phonon blockade). Self-trapping originates from mechanical nonlinearities, meaning that when the nonlinearity exceeds its critical value, the energy exchange between the two resonators is suppressed, and phonon Josephson oscillations between them are completely blocked. An effective classical Hamiltonian for the phonon Josephson junction is derived and its mean-field dynamics is studied in phase space. Finally, we study the phonon-phonon coherence quantified by the mean fringe visibility, and show that the interaction between the two resonators may lead to the loss of coherence in the phononic junction.
AU - Barzanjeh, Shabir
AU - Vitali, David
ID - 1370
IS - 3
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Phonon Josephson junction with nanomechanical resonators
VL - 93
ER -
TY - JOUR
AB - Redirection of intercellular auxin fluxes via relocalization of the PIN-FORMED 3 (PIN3) and PIN7 auxin efflux carriers has been suggested to be necessary for the root gravitropic response. Cytokinins have also been proposed to play a role in controlling root gravitropism, but conclusive evidence is lacking. We present a detailed study of the dynamics of root bending early after gravistimulation, which revealed a delayed gravitropic response in transgenic lines with depleted endogenous cytokinins (Pro35S:AtCKX) and cytokinin signaling mutants. Pro35S:AtCKX lines, as well as a cytokinin receptor mutant ahk3, showed aberrations in the auxin response distribution in columella cells consistent with defects in the auxin transport machinery. Using in vivo real-time imaging of PIN3-GFP and PIN7-GFP in AtCKX3 overexpression and ahk3 backgrounds, we observed wild-type-like relocalization of PIN proteins in the columella early after gravistimulation, with gravity-induced relocalization of PIN7 faster than that of PIN3. Nonetheless, the cellular distribution of PIN3 and PIN7 and expression of PIN7 and the auxin influx carrier AUX1 was affected in AtCKX overexpression lines. Based on the retained cytokinin sensitivity in pin3 pin4 pin7 mutant, we propose the AUX1-mediated auxin transport rather than columella-located PIN proteins as a target of endogenous cytokinins in the control of root gravitropism.
AU - Pernisová, Markéta
AU - Prat, Tomas
AU - Grones, Peter
AU - Haruštiaková, Danka
AU - Matonohova, Martina
AU - Spíchal, Lukáš
AU - Nodzyński, Tomasz
AU - Friml, Jirí
AU - Hejátko, Jan
ID - 1372
IS - 2
JF - New Phytologist
TI - Cytokinins influence root gravitropism via differential regulation of auxin transporter expression and localization in Arabidopsis
VL - 212
ER -
TY - JOUR
AB - We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the nonconvex case and derive worst-case complexities that are equal to or better than existing methods. We show applications to total variation based two dimensional image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very effcient, offer a high degree of parallelism, and come along with memory requirements which are only in the order of the number of image pixels.
AU - Kolmogorov, Vladimir
AU - Pock, Thomas
AU - Rolinek, Michal
ID - 1377
IS - 2
JF - SIAM Journal on Imaging Sciences
TI - Total variation on a tree
VL - 9
ER -
TY - CONF
AB - We give a detailed and easily accessible proof of Gromov's Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map X → ℝd there exists a point p ∈ ℝd whose preimage intersects a positive fraction μ > 0 of the d-cells of X. More generally, the conclusion holds if ℝd is replaced by any d-dimensional piecewise-linear (PL) manifold M, with a constant μ that depends only on d and on the expansion properties of X, but not on M.
AU - Dotterrer, Dominic
AU - Kaufman, Tali
AU - Wagner, Uli
ID - 1378
TI - On expansion and topological overlap
VL - 51
ER -
TY - CONF
AB - We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.
AU - Burton, Benjamin
AU - De Mesmay, Arnaud N
AU - Wagner, Uli
ID - 1379
TI - Finding non-orientable surfaces in 3-manifolds
VL - 51
ER -
TY - JOUR
AB - We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem - determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NPRP.
AU - Chonev, Ventsislav K
AU - Ouaknine, Joël
AU - Worrell, James
ID - 1380
IS - 3
JF - Journal of the ACM
TI - On the complexity of the orbit problem
VL - 63
ER -
TY - CONF
AB - Motivated by Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into double-struck Rd without higher-multiplicity intersections. We focus on conditions for the existence of almost r-embeddings, i.e., maps f : K → double-struck Rd such that f(σ1) ∩ ⋯ ∩ f(σr) = ∅ whenever σ1, ..., σr are pairwise disjoint simplices of K. Generalizing the classical Haefliger-Weber embeddability criterion, we show that a well-known necessary deleted product condition for the existence of almost r-embeddings is sufficient in a suitable r-metastable range of dimensions: If rd ≥ (r + 1) dim K + 3, then there exists an almost r-embedding K → double-struck Rd if and only if there exists an equivariant map (K)Δ r → Sr Sd(r-1)-1, where (K)Δ r is the deleted r-fold product of K, the target Sd(r-1)-1 is the sphere of dimension d(r - 1) - 1, and Sr is the symmetric group. This significantly extends one of the main results of our previous paper (which treated the special case where d = rk and dim K = (r - 1)k for some k ≥ 3), and settles an open question raised there.
AU - Mabillard, Isaac
AU - Wagner, Uli
ID - 1381
TI - Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range
VL - 51
ER -
TY - CONF
AB - The continuous evolution of a wide variety of systems, including continous-time Markov chains and linear hybrid automata, can be
described in terms of linear differential equations. In this paper we study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target halfspace infinitely often. This recurrent reachability problem can
equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function f:R≥0 --> R satisfying a given linear
differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most 7, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.
AU - Chonev, Ventsislav K
AU - Ouaknine, Joël
AU - Worrell, James
ID - 1389
T2 - LICS '16
TI - On recurrent reachability for continuous linear dynamical systems
ER -
TY - CONF
AB - We present an extension to the quantifier-free theory of integer arrays which allows us to express counting. The properties expressible in Array Folds Logic (AFL) include statements such as "the first array cell contains the array length," and "the array contains equally many minimal and maximal elements." These properties cannot be expressed in quantified fragments of the theory of arrays, nor in the theory of concatenation. Using reduction to counter machines, we show that the satisfiability problem of AFL is PSPACE-complete, and with a natural restriction the complexity decreases to NP. We also show that adding either universal quantifiers or concatenation leads to undecidability.
AFL contains terms that fold a function over an array. We demonstrate that folding, a well-known concept from functional languages, allows us to concisely summarize loops that count over arrays, which occurs frequently in real-life programs. We provide a tool that can discharge proof obligations in AFL, and we demonstrate on practical examples that our decision procedure can solve a broad range of problems in symbolic testing and program verification.
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Kupriyanov, Andrey
ID - 1391
TI - Array folds logic
VL - 9780
ER -
TY - JOUR
AB - The solution space of genome-scale models of cellular metabolism provides a map between physically
viable flux configurations and cellular metabolic phenotypes described, at the most basic level, by the
corresponding growth rates. By sampling the solution space of E. coliʼs metabolic network, we show
that empirical growth rate distributions recently obtained in experiments at single-cell resolution can
be explained in terms of a trade-off between the higher fitness of fast-growing phenotypes and the
higher entropy of slow-growing ones. Based on this, we propose a minimal model for the evolution of
a large bacterial population that captures this trade-off. The scaling relationships observed in
experiments encode, in such frameworks, for the same distance from the maximum achievable growth
rate, the same degree of growth rate maximization, and/or the same rate of phenotypic change. Being
grounded on genome-scale metabolic network reconstructions, these results allow for multiple
implications and extensions in spite of the underlying conceptual simplicity.
AU - De Martino, Daniele
AU - Capuani, Fabrizio
AU - De Martino, Andrea
ID - 1394
IS - 3
JF - Physical Biology
TI - Growth against entropy in bacterial metabolism: the phenotypic trade-off behind empirical growth rate distributions in E. coli
VL - 13
ER -
TY - THES
AB - CA3 pyramidal neurons are thought to pay a key role in memory storage and pattern completion by activity-dependent synaptic plasticity between CA3-CA3 recurrent excitatory synapses. To examine the induction rules of synaptic plasticity at CA3-CA3 synapses, we performed whole-cell patch-clamp recordings in acute hippocampal slices from rats (postnatal 21-24 days) at room temperature. Compound excitatory postsynaptic potentials (ESPSs) were recorded by tract stimulation in stratum oriens in the presence of 10 µM gabazine. High-frequency stimulation (HFS) induced N-methyl-D-aspartate (NMDA) receptor-dependent long-term potentiation (LTP). Although LTP by HFS did not requier postsynaptic spikes, it was blocked by Na+-channel blockers suggesting that local active processes (e.g.) dendritic spikes) may contribute to LTP induction without requirement of a somatic action potential (AP). We next examined the properties of spike timing-dependent plasticity (STDP) at CA3-CA3 synapses. Unexpectedly, low-frequency pairing of EPSPs and backpropagated action potentialy (bAPs) induced LTP, independent of temporal order. The STDP curve was symmetric and broad, with a half-width of ~150 ms. Consistent with these specific STDP induction properties, post-presynaptic sequences led to a supralinear summation of spine [Ca2+] transients. Furthermore, in autoassociative network models, storage and recall was substantially more robust with symmetric than with asymmetric STDP rules. In conclusion, we found associative forms of LTP at CA3-CA3 recurrent collateral synapses with distinct induction rules. LTP induced by HFS may be associated with dendritic spikes. In contrast, low frequency pairing of pre- and postsynaptic activity induced LTP only if EPSP-AP were temporally very close. Together, these induction mechanisms of synaptiic plasticity may contribute to memory storage in the CA3-CA3 microcircuit at different ranges of activity.
AU - Mishra, Rajiv Kumar
ID - 1396
TI - Synaptic plasticity rules at CA3-CA3 recurrent synapses in hippocampus
ER -
TY - THES
AB - Hybrid zones represent evolutionary laboratories, where recombination brings together alleles in combinations which have not previously been tested by selection. This provides an excellent opportunity to test the effect of molecular variation on fitness, and how this variation is able to spread through populations in a natural context. The snapdragon Antirrhinum majus is polymorphic in the wild for two loci controlling the distribution of yellow and magenta floral pigments. Where the yellow A. m. striatum and the magenta A. m. pseudomajus meet along a valley in the Spanish Pyrenees they form a stable hybrid zone Alleles at these loci recombine to give striking transgressive variation for flower colour. The sharp transition in phenotype over ~1km implies strong selection maintaining the hybrid zone. An indirect assay of pollinator visitation in the field found that pollinators forage in a positive-frequency dependent manner on Antirrhinum, matching previous data on fruit set. Experimental arrays and paternity analysis of wild-pollinated seeds demonstrated assortative mating for pigmentation alleles, and that pollinator behaviour alone is sufficient to explain this pattern. Selection by pollinators should be sufficiently strong to maintain the hybrid zone, although other mechanisms may be at work. At a broader scale I examined evolutionary transitions between yellow and anthocyanin pigmentation in the tribe Antirrhinae, and found that selection has acted strate that pollinators are a major determinant of reproductive success and mating patterns in wild Antirrhinum.
AU - Ellis, Thomas
ID - 1398
TI - The role of pollinator-mediated selection in the maintenance of a flower color polymorphism in an Antirrhinum majus hybrid zone
ER -
TY - JOUR
AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map (Formula presented.) on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within (Formula presented.) distance r from f for a given (Formula presented.). The main drawback of the approach is that the computability of well groups was shown only when (Formula presented.) or (Formula presented.). Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of (Formula presented.) by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and (Formula presented.), our approximation of the (Formula presented.)th well group is exact. For the second part, we find examples of maps (Formula presented.) with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.
AU - Franek, Peter
AU - Krcál, Marek
ID - 1408
IS - 1
JF - Discrete & Computational Geometry
TI - On computability and triviality of well groups
VL - 56
ER -
TY - JOUR
AU - Abbott, Richard
AU - Barton, Nicholas H
AU - Good, Jeffrey
ID - 1409
IS - 11
JF - Molecular Ecology
TI - Genomics of hybridization and its evolutionary consequences
VL - 25
ER -
TY - JOUR
AB - The pollen grains arise after meiosis of pollen mother cells within the anthers. A series of complex structural changes follows, generating mature pollen grains capable of performing the double fertilization of the female megasporophyte. Several signaling molecules, including hormones and lipids, have been involved in the regulation and appropriate control of pollen development. Phosphatidylinositol 4-phophate 5-kinases (PIP5K), which catalyze the biosynthesis of the phosphoinositide PtdIns(4,5)P2, are important for tip polar growth of root hairs and pollen tubes, embryo development, vegetative plant growth, and responses to the environment. Here, we report a role of PIP5Ks during microgametogenesis. PIP5K1 and PIP5K2 are expressed during early stages of pollen development and their transcriptional activity respond to auxin in pollen grains. Early male gametophytic lethality to certain grade was observed in both pip5k1-/- and pip5k2-/- single mutants. The number of pip5k mutant alleles is directly related to the frequency of aborted pollen grains suggesting the two genes are involved in the same function. Indeed PIP5K1 and PIP5K2 are functionally redundant since homozygous double mutants did not render viable pollen grains. The loss of function of PIP5K1 and PIP5K2results in defects in vacuole morphology in pollen at the later stages and epidermal root cells. Our results show that PIP5K1, PIP5K2 and phosphoinositide signaling are important cues for early developmental stages and vacuole formation during microgametogenesis.
AU - Ugalde, José
AU - Rodríguez Furlán, Cecilia
AU - De Rycke, Riet
AU - Norambuena, Lorena
AU - Friml, Jirí
AU - León, Gabriel
AU - Tejos, Ricardo
ID - 1410
JF - Plant Science
TI - Phosphatidylinositol 4-phosphate 5-kinases 1 and 2 are involved in the regulation of vacuole morphology during Arabidopsis thaliana pollen development
VL - 250
ER -
TY - JOUR
AB - We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.
AU - Matoušek, Jiří
AU - Sedgwick, Eric
AU - Tancer, Martin
AU - Wagner, Uli
ID - 1411
IS - 1
JF - Israel Journal of Mathematics
TI - Untangling two systems of noncrossing curves
VL - 212
ER -
TY - JOUR
AB - Combining high-resolution level set surface tracking with lower resolution physics is an inexpensive method for achieving highly detailed liquid animations. Unfortunately, the inherent resolution mismatch introduces several types of disturbing visual artifacts. We identify the primary sources of these artifacts and present simple, efficient, and practical solutions to address them. First, we propose an unconditionally stable filtering method that selectively removes sub-grid surface artifacts not seen by the fluid physics, while preserving fine detail in dynamic splashing regions. It provides comparable results to recent error-correction techniques at lower cost, without substepping, and with better scaling behavior. Second, we show how a modified narrow-band scheme can ensure accurate free surface boundary conditions in the presence of large resolution mismatches. Our scheme preserves the efficiency of the narrow-band methodology, while eliminating objectionable stairstep artifacts observed in prior work. Third, we demonstrate that the use of linear interpolation of velocity during advection of the high-resolution level set surface is responsible for visible grid-aligned kinks; we therefore advocate higher-order velocity interpolation, and show that it dramatically reduces this artifact. While these three contributions are orthogonal, our results demonstrate that taken together they efficiently address the dominant sources of visual artifacts arising with high-resolution embedded liquid surfaces; the proposed approach offers improved visual quality, a straightforward implementation, and substantially greater scalability than competing methods.
AU - Goldade, Ryan
AU - Batty, Christopher
AU - Wojtan, Christopher J
ID - 1412
IS - 2
JF - Computer Graphics Forum
TI - A practical method for high-resolution embedded liquid surfaces
VL - 35
ER -
TY - JOUR
AB - The Fluid Implicit Particle method (FLIP) for liquid simulations uses particles to reduce numerical dissipation and provide important visual cues for events like complex splashes and small-scale features near the liquid surface. Unfortunately, FLIP simulations can be computationally expensive, because they require a dense sampling of particles to fill the entire liquid volume. Furthermore, the vast majority of these FLIP particles contribute nothing to the fluid's visual appearance, especially for larger volumes of liquid. We present a method that only uses FLIP particles within a narrow band of the liquid surface, while efficiently representing the remaining inner volume on a regular grid. We show that a naïve realization of this idea introduces unstable and uncontrollable energy fluctuations, and we propose a novel coupling scheme between FLIP particles and regular grid which overcomes this problem. Our method drastically reduces the particle count and simulation times while yielding results that are nearly indistinguishable from regular FLIP simulations. Our approach is easy to integrate into any existing FLIP implementation.
AU - Ferstl, Florian
AU - Ando, Ryoichi
AU - Wojtan, Christopher J
AU - Westermann, Rüdiger
AU - Thuerey, Nils
ID - 1415
IS - 2
JF - Computer Graphics Forum
TI - Narrow band FLIP for liquid simulations
VL - 35
ER -
TY - JOUR
AB - Anisotropic dipole-dipole interactions between ultracold dipolar fermions break the symmetry of the Fermi surface and thereby deform it. Here we demonstrate that such a Fermi surface deformation induces a topological phase transition - the so-called Lifshitz transition - in the regime accessible to present-day experiments. We describe the impact of the Lifshitz transition on observable quantities such as the Fermi surface topology, the density-density correlation function, and the excitation spectrum of the system. The Lifshitz transition in ultracold atoms can be controlled by tuning the dipole orientation and, in contrast to the transition studied in crystalline solids, is completely interaction driven.
AU - Van Loon, Erik
AU - Katsnelson, Mikhail
AU - Chomaz, Lauriane
AU - Lemeshko, Mikhail
ID - 1416
IS - 19
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Interaction-driven Lifshitz transition with dipolar fermions in optical lattices
VL - 93
ER -
TY - JOUR
AB - Plant development mediated by the phytohormone auxin depends on tightly controlled cellular auxin levels at its target tissue that are largely established by intercellular and intracellular auxin transport mediated by PIN auxin transporters. Among the eight members of the Arabidopsis PIN family, PIN6 is the least characterized candidate. In this study we generated functional, fluorescent protein-tagged PIN6 proteins and performed comprehensive analysis of their subcellular localization and also performed a detailed functional characterization of PIN6 and its developmental roles. The localization study of PIN6 revealed a dual localization at the plasma membrane (PM) and endoplasmic reticulum (ER). Transport and metabolic profiling assays in cultured cells and Arabidopsis strongly suggest that PIN6 mediates both auxin transport across the PM and intracellular auxin homeostasis, including the regulation of free auxin and auxin conjugates levels. As evidenced by the loss- and gain-of-function analysis, the complex function of PIN6 in auxin transport and homeostasis is required for auxin distribution during lateral and adventitious root organogenesis and for progression of these developmental processes. These results illustrate a unique position of PIN6 within the family of PIN auxin transporters and further add complexity to the developmentally crucial process of auxin transport.
AU - Simon, Sibu
AU - Skůpa, Petr
AU - Viaene, Tom
AU - Zwiewka, Marta
AU - Tejos, Ricardo
AU - Klíma, Petr
AU - Čarná, Mária
AU - Rolčík, Jakub
AU - De Rycke, Riet
AU - Moreno, Ignacio
AU - Dobrev, Petre
AU - Orellana, Ariel
AU - Zažímalová, Eva
AU - Friml, Jirí
ID - 1417
IS - 1
JF - New Phytologist
TI - PIN6 auxin transporter at endoplasmic reticulum and plasma membrane mediates auxin homeostasis and organogenesis in Arabidopsis
VL - 211
ER -
TY - JOUR
AB - We study the time-dependent Bogoliubov–de-Gennes equations for generic translation-invariant fermionic many-body systems. For initial states that are close to thermal equilibrium states at temperatures near the critical temperature, we show that the magnitude of the order parameter stays approximately constant in time and, in particular, does not follow a time-dependent Ginzburg–Landau equation, which is often employed as a phenomenological description and predicts a decay of the order parameter in time. The full non-linear structure of the equations is necessary to understand this behavior.
AU - Frank, Rupert
AU - Hainzl, Christian
AU - Schlein, Benjamin
AU - Seiringer, Robert
ID - 1422
IS - 7
JF - Letters in Mathematical Physics
TI - Incompatibility of time-dependent Bogoliubov–de-Gennes and Ginzburg–Landau equations
VL - 106
ER -
TY - JOUR
AB - Direct reciprocity is a mechanism for the evolution of cooperation based on repeated interactions. When individuals meet repeatedly, they can use conditional strategies to enforce cooperative outcomes that would not be feasible in one-shot social dilemmas. Direct reciprocity requires that individuals keep track of their past interactions and find the right response. However, there are natural bounds on strategic complexity: Humans find it difficult to remember past interactions accurately, especially over long timespans. Given these limitations, it is natural to ask how complex strategies need to be for cooperation to evolve. Here, we study stochastic evolutionary game dynamics in finite populations to systematically compare the evolutionary performance of reactive strategies, which only respond to the co-player's previous move, and memory-one strategies, which take into account the own and the co-player's previous move. In both cases, we compare deterministic strategy and stochastic strategy spaces. For reactive strategies and small costs, we find that stochasticity benefits cooperation, because it allows for generous-tit-for-tat. For memory one strategies and small costs, we find that stochasticity does not increase the propensity for cooperation, because the deterministic rule of win-stay, lose-shift works best. For memory one strategies and large costs, however, stochasticity can augment cooperation.
AU - Baek, Seung
AU - Jeong, Hyeongchai
AU - Hilbe, Christian
AU - Nowak, Martin
ID - 1423
JF - Scientific Reports
TI - Comparing reactive and memory-one strategies of direct reciprocity
VL - 6
ER -
TY - JOUR
AB - Brood parasites exploit their host in order to increase their own fitness. Typically, this results in an arms race between parasite trickery and host defence. Thus, it is puzzling to observe hosts that accept parasitism without any resistance. The ‘mafia’ hypothesis suggests that these hosts accept parasitism to avoid retaliation. Retaliation has been shown to evolve when the hosts condition their response to mafia parasites, who use depredation as a targeted response to rejection. However, it is unclear if acceptance would also emerge when ‘farming’ parasites are present in the population. Farming parasites use depredation to synchronize the timing with the host, destroying mature clutches to force the host to re-nest. Herein, we develop an evolutionary model to analyse the interaction between depredatory parasites and their hosts. We show that coevolutionary cycles between farmers and mafia can still induce host acceptance of brood parasites. However, this equilibrium is unstable and in the long-run the dynamics of this host–parasite interaction exhibits strong oscillations: when farmers are the majority, accepters conditional to mafia (the host will reject first and only accept after retaliation by the parasite) have a higher fitness than unconditional accepters (the host always accepts parasitism). This leads to an increase in mafia parasites’ fitness and in turn induce an optimal environment for accepter hosts.
AU - Chakra, Maria
AU - Hilbe, Christian
AU - Traulsen, Arne
ID - 1426
IS - 5
JF - Royal Society Open Science
TI - Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites
VL - 3
ER -
TY - JOUR
AB - Changes in gene expression are an important mode of evolution; however, the proximate mechanism of these changes is poorly understood. In particular, little is known about the effects of mutations within cis binding sites for transcription factors, or the nature of epistatic interactions between these mutations. Here, we tested the effects of single and double mutants in two cis binding sites involved in the transcriptional regulation of the Escherichia coli araBAD operon, a component of arabinose metabolism, using a synthetic system. This system decouples transcriptional control from any posttranslational effects on fitness, allowing a precise estimate of the effect of single and double mutations, and hence epistasis, on gene expression. We found that epistatic interactions between mutations in the araBAD cis-regulatory element are common, and that the predominant form of epistasis is negative. The magnitude of the interactions depended on whether the mutations are located in the same or in different operator sites. Importantly, these epistatic interactions were dependent on the presence of arabinose, a native inducer of the araBAD operon in vivo, with some interactions changing in sign (e.g., from negative to positive) in its presence. This study thus reveals that mutations in even relatively simple cis-regulatory elements interact in complex ways such that selection on the level of gene expression in one environment might perturb regulation in the other environment in an unpredictable and uncorrelated manner.
AU - Lagator, Mato
AU - Igler, Claudia
AU - Moreno, Anaisa
AU - Guet, Calin C
AU - Bollback, Jonathan P
ID - 1427
IS - 3
JF - Molecular Biology and Evolution
TI - Epistatic interactions in the arabinose cis-regulatory element
VL - 33
ER -
TY - CONF
AB - We report on a mathematically rigorous analysis of the superfluid properties of a Bose- Einstein condensate in the many-body ground state of a one-dimensional model of interacting bosons in a random potential.
AU - Könenberg, Martin
AU - Moser, Thomas
AU - Seiringer, Robert
AU - Yngvason, Jakob
ID - 1428
IS - 1
T2 - Journal of Physics: Conference Series
TI - Superfluidity and BEC in a Model of Interacting Bosons in a Random Potential
VL - 691
ER -
TY - JOUR
AB - Solitons are localized waves formed by a balance of focusing and defocusing effects. These nonlinear waves exist in diverse forms of matter yet exhibit similar properties including stability, periodic recurrence and particle-like trajectories. One important property is soliton fission, a process by which an energetic higher-order soliton breaks apart due to dispersive or nonlinear perturbations. Here we demonstrate through both experiment and theory that nonlinear photocarrier generation can induce soliton fission. Using near-field measurements, we directly observe the nonlinear spatial and temporal evolution of optical pulses in situ in a nanophotonic semiconductor waveguide. We develop an analytic formalism describing the free-carrier dispersion (FCD) perturbation and show the experiment exceeds the minimum threshold by an order of magnitude. We confirm these observations with a numerical nonlinear Schrödinger equation model. These results provide a fundamental explanation and physical scaling of optical pulse evolution in free-carrier media and could enable improved supercontinuum sources in gas based and integrated semiconductor waveguides.
AU - Husko, Chad
AU - Wulf, Matthias
AU - Lefrançois, Simon
AU - Combrié, Sylvain
AU - Lehoucq, Gaëlle
AU - De Rossi, Alfredo
AU - Eggleton, Benjamin
AU - Kuipers, Laurens
ID - 1429
JF - Nature Communications
TI - Free-carrier-induced soliton fission unveiled by in situ measurements in nanophotonic waveguides
VL - 7
ER -
TY - JOUR
AB - The rare socially parasitic butterfly Maculinea alcon occurs in two forms, which are characteristic of hygric or xeric habitats and which exploit different host plants and host ants. The status of these two forms has been the subject of considerable controversy. Populations of the two forms are usually spatially distinct, but at Răscruci in Romania both forms occur on the same site (syntopically). We examined the genetic differentiation between the two forms using eight microsatellite markers, and compared with a nearby hygric site, Şardu. Our results showed that while the two forms are strongly differentiated at Răscruci, it is the xeric form there that is most similar to the hygric form at Şardu, and Bayesian clustering algorithms suggest that these two populations have exchanged genes relatively recently. We found strong evidence for population substructuring, caused by high within host ant nest relatedness, indicating very limited dispersal of most ovipositing females, but not association with particular host ant species. Our results are consistent with the results of larger scale phylogeographic studies that suggest that the two forms represent local ecotypes specialising on different host plants, each with a distinct flowering phenology, providing a temporal rather than spatial barrier to gene flow.
AU - Tartally, András
AU - Kelager, Andreas
AU - Fürst, Matthias
AU - Nash, David
ID - 1431
IS - 3
JF - PeerJ
TI - Host plant use drives genetic differentiation in syntopic populations of Maculinea alcon
VL - 2016
ER -
TY - JOUR
AB - CA3–CA3 recurrent excitatory synapses are thought to play a key role in memory storage and pattern completion. Whether the plasticity properties of these synapses are consistent with their proposed network functions remains unclear. Here, we examine the properties of spike timing-dependent plasticity (STDP) at CA3–CA3 synapses. Low-frequency pairing of excitatory postsynaptic potentials (EPSPs) and action potentials (APs) induces long-term potentiation (LTP), independent of temporal order. The STDP curve is symmetric and broad (half-width ~150 ms). Consistent with these STDP induction properties, AP–EPSP sequences lead to supralinear summation of spine [Ca2+] transients. Furthermore, afterdepolarizations (ADPs) following APs efficiently propagate into dendrites of CA3 pyramidal neurons, and EPSPs summate with dendritic ADPs. In autoassociative network models, storage and recall are more robust with symmetric than with asymmetric STDP rules. Thus, a specialized STDP induction rule allows reliable storage and recall of information in the hippocampal CA3 network.
AU - Mishra, Rajiv Kumar
AU - Kim, Sooyun
AU - Guzmán, José
AU - Jonas, Peter M
ID - 1432
JF - Nature Communications
TI - Symmetric spike timing-dependent plasticity at CA3–CA3 synapses optimizes storage and recall in autoassociative networks
VL - 7
ER -
TY - JOUR
AB - We prove that the system of subordination equations, defining the free additive convolution of two probability measures, is stable away from the edges of the support and blow-up singularities by showing that the recent smoothness condition of Kargin is always satisfied. As an application, we consider the local spectral statistics of the random matrix ensemble A+UBU⁎A+UBU⁎, where U is a Haar distributed random unitary or orthogonal matrix, and A and B are deterministic matrices. In the bulk regime, we prove that the empirical spectral distribution of A+UBU⁎A+UBU⁎ concentrates around the free additive convolution of the spectral distributions of A and B on scales down to N−2/3N−2/3.
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 1434
IS - 3
JF - Journal of Functional Analysis
TI - Local stability of the free additive convolution
VL - 271
ER -
TY - JOUR
AB - ATP released from neurons and astrocytes during neuronal activity or under pathophysiological circumstances is able to influence information flow in neuronal circuits by activation of ionotropic P2X and metabotropic P2Y receptors and subsequent modulation of cellular excitability, synaptic strength, and plasticity. In the present paper we review cellular and network effects of P2Y receptors in the brain. We show that P2Y receptors inhibit the release of neurotransmitters, modulate voltage- and ligand-gated ion channels, and differentially influence the induction of synaptic plasticity in the prefrontal cortex, hippocampus, and cerebellum. The findings discussed here may explain how P2Y1 receptor activation during brain injury, hypoxia, inflammation, schizophrenia, or Alzheimer's disease leads to an impairment of cognitive processes. Hence, it is suggested that the blockade of P2Y1 receptors may have therapeutic potential against cognitive disturbances in these states.
AU - Guzmán, José
AU - Gerevich, Zoltan
ID - 1435
JF - Neural Plasticity
TI - P2Y receptors in synaptic transmission and plasticity: Therapeutic potential in cognitive dysfunction
VL - 2016
ER -
TY - JOUR
AB - We study the time evolution of a system of N spinless fermions in R3 which interact through a pair potential, e.g., the Coulomb potential. We compare the dynamics given by the solution to Schrödinger's equation with the time-dependent Hartree-Fock approximation, and we give an estimate for the accuracy of this approximation in terms of the kinetic energy of the system. This leads, in turn, to bounds in terms of the initial total energy of the system.
AU - Bach, Volker
AU - Breteaux, Sébastien
AU - Petrat, Sören P
AU - Pickl, Peter
AU - Tzaneteas, Tim
ID - 1436
IS - 1
JF - Journal de Mathématiques Pures et Appliquées
TI - Kinetic energy estimates for the accuracy of the time-dependent Hartree-Fock approximation with Coulomb interaction
VL - 105
ER -
TY - CONF
AB - In this paper, we consider termination of probabilistic programs with real-valued variables. The questions concerned are: (a) qualitative ones that ask (i) whether the program terminates with probability 1 (almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); (b) quantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) to compute a bound B such that the probability to terminate after B steps decreases exponentially (concentration problem). To solve these questions, we utilize the notion of ranking supermartingales which is a powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmic synthesis of linear ranking-supermartingales over affine probabilistic programs (APP's) with both angelic and demonic non-determinism. An important subclass of APP's is LRAPP which is defined as the class of all APP's over which a linear ranking-supermartingale exists. Our main contributions are as follows. Firstly, we show that the membership problem of LRAPP (i) can be decided in polynomial time for APP's with at most demonic non-determinism, and (ii) is NP-hard and in PSPACE for APP's with angelic non-determinism; moreover, the NP-hardness result holds already for APP's without probability and demonic non-determinism. Secondly, we show that the concentration problem over LRAPP can be solved in the same complexity as for the membership problem of LRAPP. Finally, we show that the expectation problem over LRAPP can be solved in 2EXPTIME and is PSPACE-hard even for APP's without probability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate the effectiveness of our approach to answer the qualitative and quantitative questions over APP's with at most demonic non-determinism.
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Novotny, Petr
AU - Hasheminezhad, Rouzbeh
ID - 1438
TI - Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
VL - 20-22
ER -
TY - CONF
AB - Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. We introduce PSYNC, a domain specific language based on the Heard-Of model, which views asynchronous faulty systems as synchronous ones with an adversarial environment that simulates asynchrony and faults by dropping messages. We define a runtime system for PSYNC that efficiently executes on asynchronous networks. We formalize the relation between the runtime system and PSYNC in terms of observational refinement. The high-level lockstep abstraction introduced by PSYNC simplifies the design and implementation of fault-tolerant distributed algorithms and enables automated formal verification. We have implemented an embedding of PSYNC in the SCALA programming language with a runtime system for asynchronous networks. We show the applicability of PSYNC by implementing several important fault-tolerant distributed algorithms and we compare the implementation of consensus algorithms in PSYNC against implementations in other languages in terms of code size, runtime efficiency, and verification.
AU - Dragoi, Cezara
AU - Henzinger, Thomas A
AU - Zufferey, Damien
ID - 1439
TI - PSYNC: A partially synchronous language for fault-tolerant distributed algorithms
VL - 20-22
ER -
TY - JOUR
AB - Optogenetics and photopharmacology enable the spatio-temporal control of cell and animal behavior by light. Although red light offers deep-tissue penetration and minimal phototoxicity, very few red-light-sensitive optogenetic methods are currently available. We have now developed a red-light-induced homodimerization domain. We first showed that an optimized sensory domain of the cyanobacterial phytochrome 1 can be expressed robustly and without cytotoxicity in human cells. We then applied this domain to induce the dimerization of two receptor tyrosine kinases—the fibroblast growth factor receptor 1 and the neurotrophin receptor trkB. This new optogenetic method was then used to activate the MAPK/ERK pathway non-invasively in mammalian tissue and in multicolor cell-signaling experiments. The light-controlled dimerizer and red-light-activated receptor tyrosine kinases will prove useful to regulate a variety of cellular processes with light. Go deep with red: The sensory domain (S) of the cyanobacterial phytochrome 1 (CPH1) was repurposed to induce the homodimerization of proteins in living cells by red light. By using this domain, light-activated protein kinases were engineered that can be activated orthogonally from many fluorescent proteins and through mammalian tissue. Pr/Pfr=red-/far-red-absorbing state of CPH1.
AU - Gschaider-Reichhart, Eva
AU - Inglés Prieto, Álvaro
AU - Tichy, Alexandra-Madelaine
AU - Mckenzie, Catherine
AU - Janovjak, Harald L
ID - 1441
IS - 21
JF - Angewandte Chemie - International Edition
TI - A phytochrome sensory domain permits receptor activation by red light
VL - 55
ER -
TY - JOUR
AB - The accuracy of interdisciplinarity measurements is directly related to the quality of the underlying bibliographic data. Existing indicators of interdisciplinarity are not capable of reflecting the inaccuracies introduced by incorrect and incomplete records because correct and complete bibliographic data can rarely be obtained. This is the case for the Rao–Stirling index, which cannot handle references that are not categorized into disciplinary fields. We introduce a method that addresses this problem. It extends the Rao–Stirling index to acknowledge missing data by calculating its interval of uncertainty using computational optimization. The evaluation of our method indicates that the uncertainty interval is not only useful for estimating the inaccuracy of interdisciplinarity measurements, but it also delivers slightly more accurate aggregated interdisciplinarity measurements than the Rao–Stirling index.
AU - Calatrava Moreno, Maria
AU - Auzinger, Thomas
AU - Werthner, Hannes
ID - 1446
IS - 1
JF - Scientometrics
TI - On the uncertainty of interdisciplinarity measurements due to incomplete bibliographic data
VL - 107
ER -
TY - JOUR
AB - We develop a new and systematic method for proving entropic Ricci curvature lower bounds for Markov chains on discrete sets. Using different methods, such bounds have recently been obtained in several examples (e.g., 1-dimensional birth and death chains, product chains, Bernoulli–Laplace models, and random transposition models). However, a general method to obtain discrete Ricci bounds had been lacking. Our method covers all of the examples above. In addition we obtain new Ricci curvature bounds for zero-range processes on the complete graph. The method is inspired by recent work of Caputo, Dai Pra and Posta on discrete functional inequalities.
AU - Fathi, Max
AU - Maas, Jan
ID - 1448
IS - 3
JF - The Annals of Applied Probability
TI - Entropic Ricci curvature bounds for discrete interacting systems
VL - 26
ER -
TY - JOUR
AB - The actin cytoskeleton plays important roles in the formation and internalization of endocytic vesicles. In yeast, endocytic vesicles move towards early endosomes along actin cables, however, the molecular machinery regulating interaction between endocytic vesicles and actin cables is poorly understood. The Eps15-like protein Pan1p plays a key role in actin-mediated endocytosis and is negatively regulated by Ark1 and Prk1 kinases. Here we show that pan1 mutated to prevent phosphorylation at all 18 threonines, pan1-18TA, displayed almost the same endocytic defect as ark1Δ prk1Δ cells, and contained abnormal actin concentrations including several endocytic compartments. Early endosomes were highly localized in the actin concentrations and displayed movement along actin cables. The dephosphorylated form of Pan1p also caused stable associations between endocytic vesicles and actin cables, and between endocytic vesicles and endosomes. Thus Pan1 phosphorylation is part of a novel mechanism that regulates endocytic compartment interactions with each other and with actin cables.
AU - Toshima, Junko
AU - Furuya, Eri
AU - Nagano, Makoto
AU - Kanno, Chisa
AU - Sakamoto, Yuta
AU - Ebihara, Masashi
AU - Siekhaus, Daria E
AU - Toshima, Jiro
ID - 1475
IS - February 2016
JF - eLife
TI - Yeast Eps15-like endocytic protein Pan1p regulates the interaction between endocytic vesicles, endosomes and the actin cytoskeleton
VL - 5
ER -
TY - JOUR
AB - The dynamic assembly and disassembly of actin filaments is essential for the formation and transport of vesicles during endocytosis. In yeast, two types of actin structures, namely cortical patches and cytoplasmic cables, play a direct role in endocytosis, but how their interaction is regulated remains unclear. Here, we show that Srv2/CAP, an evolutionarily conserved actin regulator, is required for efficient endocytosis owing to its role in the formation of the actin patches that aid initial vesicle invagination and of the actin cables that these move along. Deletion of the SRV2 gene resulted in the appearance of aberrant fragmented actin cables that frequently moved past actin patches, the sites of endocytosis. We find that the C-terminal CARP domain of Srv2p is vitally important for the proper assembly of actin patches and cables; we also demonstrate that the N-terminal helical folded domain of Srv2 is required for its localization to actin patches, specifically to the ADP-actin rich region through an interaction with cofilin. These results demonstrate the in vivo roles of Srv2p in the regulation of the actin cytoskeleton during clathrin-mediated endocytosis
AU - Toshima, Junko
AU - Horikomi, Chika
AU - Okada, Asuka
AU - Hatori, Makiko
AU - Nagano, Makoto
AU - Masuda, Atsushi
AU - Yamamoto, Wataru
AU - Siekhaus, Daria E
AU - Toshima, Jiro
ID - 1476
IS - 2
JF - Journal of Cell Science
TI - Srv2/CAP is required for polarized actin cable assembly and patch internalization during clathrin-mediated endocytosis
VL - 129
ER -
TY - JOUR
AB - We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Tracol, Mathieu
ID - 1477
IS - 5
JF - Journal of Computer and System Sciences
TI - What is decidable about partially observable Markov decision processes with ω-regular objectives
VL - 82
ER -