TY  DATA
AB  Script to perform a simple exponential lifetime fit of a ROI on time stacks acquired with a FLIM X16 TCSPC detector (+example data)
AU  Hauschild, Robert
ID  5588
KW  FLIM
KW  FRET
KW  fluorescence lifetime imaging
TI  Fluorescence lifetime analysis of FLIM X16 TCSPC data
ER 
TY  CHAP
AB  Primary neuronal cell culture preparations are widely used to investigate synaptic functions. This chapter describes a detailed protocol for the preparation of a neuronal cell culture in which giant calyxtype synaptic terminals are formed. This chapter also presents detailed protocols for utilizing the main technical advantages provided by such a preparation, namely, labeling and imaging of synaptic organelles and electrophysiological recordings directly from presynaptic terminals.
AU  Dimitrov, Dimitar
AU  Guillaud, Laurent
AU  Eguchi, Kohgaku
AU  Takahashi, Tomoyuki
ED  Skaper, Stephen D.
ID  562
T2  Neurotrophic Factors
TI  Culture of mouse giant central nervous system synapses and application for imaging and electrophysiological analyses
VL  1727
ER 
TY  JOUR
AB  In continuous populations with local migration, nearby pairs of individuals have on average more similar genotypes
than geographically well separated pairs. A barrier to gene flow distorts this classical pattern of isolation by distance. Genetic similarity is decreased for sample pairs on different sides of the barrier and increased for pairs on the same side near the barrier. Here, we introduce an inference scheme that utilizes this signal to detect and estimate the strength of a linear barrier to gene flow in twodimensions. We use a diffusion approximation to model the effects of a barrier on the geographical spread of ancestry backwards in time. This approach allows us to calculate the chance of recent coalescence and probability of identity by descent. We introduce an inference scheme that fits these theoretical results to the geographical covariance structure of bialleleic genetic markers. It can estimate the strength of the barrier as well as several demographic parameters. We investigate the power of our inference scheme to detect barriers by applying it to a wide range of simulated data. We also showcase an example application to a Antirrhinum majus (snapdragon) flower color hybrid zone, where we do not detect any signal of a strong genome wide barrier to gene flow.
AU  Ringbauer, Harald
AU  Kolesnikov, Alexander
AU  Field, David
AU  Barton, Nicholas H
ID  563
IS  3
JF  Genetics
TI  Estimating barriers to gene flow from distorted isolationbydistance patterns
VL  208
ER 
TY  JOUR
AB  We reexamine the model of Kirkpatrick and Barton for the spread of an inversion into a local population. This model assumes that local selection maintains alleles at two or more loci, despite immigration of alternative alleles at these loci from another population. We show that an inversion is favored because it prevents the breakdown of linkage disequilibrium generated by migration; the selective advantage of an inversion is proportional to the amount of recombination between the loci involved, as in other cases where inversions are selected for. We derive expressions for the rate of spread of an inversion; when the loci covered by the inversion are tightly linked, these conditions deviate substantially from those proposed previously, and imply that an inversion can then have only a small advantage.
AU  Charlesworth, Brian
AU  Barton, Nicholas H
ID  565
IS  1
JF  Genetics
TI  The spread of an inversion with migration and selection
VL  208
ER 
TY  JOUR
AB  We consider large random matrices X with centered, independent entries which have comparable but not necessarily identical variances. Girko's circular law asserts that the spectrum is supported in a disk and in case of identical variances, the limiting density is uniform. In this special case, the local circular law by Bourgade et. al. [11,12] shows that the empirical density converges even locally on scales slightly above the typical eigenvalue spacing. In the general case, the limiting density is typically inhomogeneous and it is obtained via solving a system of deterministic equations. Our main result is the local inhomogeneous circular law in the bulk spectrum on the optimal scale for a general variance profile of the entries of X.
AU  Alt, Johannes
AU  Erdös, László
AU  Krüger, Torben H
ID  566
IS  1
JF  Annals Applied Probability
TI  Local inhomogeneous circular law
VL  28
ER 
TY  JOUR
AB  The release of IgM is the first line of an antibody response and precedes the generation of high affinity IgG in germinal centers. Once secreted by freshly activated plasmablasts, IgM is released into the efferent lymph of reactive lymph nodes as early as 3 d after immunization. As pentameric IgM has an enormous size of 1,000 kD, its diffusibility is low, and one might wonder how it can pass through the densely lymphocytepacked environment of a lymph node parenchyma in order to reach its exit. In this issue of JEM, Thierry et al. show that, in order to reach the blood stream, IgM molecules take a specific microanatomical route via lymph node conduits.
AU  Reversat, Anne
AU  Sixt, Michael K
ID  5672
IS  12
JF  Journal of Experimental Medicine
SN  00221007
TI  IgM's exit route
VL  215
ER 
TY  JOUR
AB  Cell polarity, manifested by the localization of proteins to distinct polar plasma membrane domains, is a key prerequisite of multicellular life. In plants, PIN auxin transporters are prominent polarity markers crucial for a plethora of developmental processes. Cell polarity mechanisms in plants are distinct from other eukaryotes and still largely elusive. In particular, how the cell polarities are propagated and maintained following cell division remains unknown. Plant cytokinesis is orchestrated by the cell plate—a transient centrifugally growing endomembrane compartment ultimately forming the cross wall1. Trafficking of polar membrane proteins is typically redirected to the cell plate, and these will consequently have opposite polarity in at least one of the daughter cells2–5. Here, we provide mechanistic insights into postcytokinetic reestablishment of cell polarity as manifested by the apical, polar localization of PIN2. We show that the apical domain is defined in a cellintrinsic manner and that reestablishment of PIN2 localization to this domain requires de novo protein secretion and endocytosis, but not basaltoapical transcytosis. Furthermore, we identify a PINOIDrelated kinase WAG1, which phosphorylates PIN2 in vitro6 and is transcriptionally upregulated specifically in dividing cells, as a crucial regulator of postcytokinetic PIN2 polarity reestablishment.
AU  Glanc, Matous
AU  Fendrych, Matyas
AU  Friml, Jirí
ID  5673
IS  12
JF  Nature Plants
SN  20550278
TI  Mechanistic framework for cellintrinsic reestablishment of PIN2 polarity after cell division
VL  4
ER 
TY  JOUR
AB  In epithelial tissues, cells tightly connect to each other through cell–cell junctions, but they also present the remarkable capacity of reorganizing themselves without compromising tissue integrity. Upon injury, simple epithelia efficiently resolve small lesions through the action of actin cytoskeleton contractile structures at the wound edge and cellular rearrangements. However, the underlying mechanisms and how they cooperate are still poorly understood. In this study, we combine live imaging and theoretical modeling to reveal a novel and indispensable role for occluding junctions (OJs) in this process. We demonstrate that OJ loss of function leads to defects in woundclosure dynamics: instead of contracting, wounds dramatically increase their area. OJ mutants exhibit phenotypes in cell shape, cellular rearrangements, and mechanical properties as well as in actin cytoskeleton dynamics at the wound edge. We propose that OJs are essential for wound closure by impacting on epithelial mechanics at the tissue level, which in turn is crucial for correct regulation of the cellular events occurring at the wound edge.
AU  Carvalho, Lara
AU  Patricio, Pedro
AU  Ponte, Susana
AU  Heisenberg, CarlPhilipp J
AU  Almeida, Luis
AU  Nunes, André S.
AU  Araújo, Nuno A.M.
AU  Jacinto, Antonio
ID  5676
IS  12
JF  Journal of Cell Biology
SN  00219525
TI  Occluding junctions as novel regulators of tissue mechanics during wound repair
VL  217
ER 
TY  JOUR
AB  Recently, contractbased design has been proposed as an “orthogonal” approach that complements system design methodologies proposed so far to cope with the complexity of system design. Contractbased design provides a rigorous scaffolding for verification, analysis, abstraction/refinement, and even synthesis. A number of results have been obtained in this domain but a unified treatment of the topic that can help put contractbased design in perspective was missing. This monograph intends to provide such a treatment where contracts are precisely defined and characterized so that they can be used in design methodologies with no ambiguity. In particular, this monograph identifies the essence of complex system design using contracts through a mathematical “metatheory”, where all the properties of the methodology are derived from a very abstract and generic notion of contract. We show that the metatheory provides deep and illuminating links with existing contract and interface theories, as well as guidelines for designing new theories. Our study encompasses contracts for both software and systems, with emphasis on the latter. We illustrate the use of contracts with two examples: requirement engineering for a parking garage management, and the development of contracts for timing and scheduling in the context of the Autosar methodology in use in the automotive sector.
AU  Benveniste, Albert
AU  Nickovic, Dejan
AU  Caillaud, Benoît
AU  Passerone, Roberto
AU  Raclet, Jean Baptiste
AU  Reinkemeier, Philipp
AU  SangiovanniVincentelli, Alberto
AU  Damm, Werner
AU  Henzinger, Thomas A
AU  Larsen, Kim G.
ID  5677
IS  23
JF  Foundations and Trends in Electronic Design Automation
SN  15513939
TI  Contracts for system design
VL  12
ER 
TY  CONF
AB  We study the almostsure termination problem for probabilistic programs. First, we show that supermartingales with lower bounds on conditional absolute difference provide a sound approach for the almostsure termination problem. Moreover, using this approach we can obtain explicit optimal bounds on tail probabilities of nontermination within a given number of steps. Second, we present a new approach based on Central Limit Theorem for the almostsure termination problem, and show that this approach can establish almostsure termination of programs which none of the existing approaches can handle. Finally, we discuss algorithmic approaches for the two above methods that lead to automated analysis techniques for almostsure termination of probabilistic programs.
AU  Huang, Mingzhang
AU  Fu, Hongfei
AU  Chatterjee, Krishnendu
ED  Ryu, Sukyoung
ID  5679
SN  03029743
TI  New approaches for almostsure termination of probabilistic programs
VL  11275
ER 
TY  GEN
AU  Danowski, Patrick
ID  5686
TI  An Austrian proposal for the Classification of Open Access Tuples (COAT)  Distinguish different Open Access types beyond colors
ER 
TY  JOUR
AB  Because of the intrinsic randomness of the evolutionary process, a mutant with a fitness advantage has some chance to be selected but no certainty. Any experiment that searches for advantageous mutants will lose many of them due to random drift. It is therefore of great interest to find population structures that improve the odds of advantageous mutants. Such structures are called amplifiers of natural selection: they increase the probability that advantageous mutants are selected. Arbitrarily strong amplifiers guarantee the selection of advantageous mutants, even for very small fitness advantage. Despite intensive research over the past decade, arbitrarily strong amplifiers have remained rare. Here we show how to construct a large variety of them. Our amplifiers are so simple that they could be useful in biotechnology, when optimizing biological molecules, or as a diagnostic tool, when searching for faster dividing cells or viruses. They could also occur in natural population structures.
AU  Pavlogiannis, Andreas
AU  Tkadlec, Josef
AU  Chatterjee, Krishnendu
AU  Nowak, Martin A.
ID  5751
IS  1
JF  Communications Biology
SN  23993642
TI  Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory
VL  1
ER 
TY  DATA
AB  File S1. Variant Calling Format file of the ingroup: 197 haploid sequences of D. melanogaster from Zambia (Africa) aligned to the D. melanogaster 5.57 reference genome.
File S2. Variant Calling Format file of the outgroup: 1 haploid sequence of D. simulans aligned to the D. melanogaster 5.57 reference genome.
File S3. Annotations of each transcript in coding regions with SNPeff: Ps (# of synonymous polymorphic sites); Pn (# of nonsynonymous polymorphic sites); Ds (# of synonymous divergent sites); Dn (# of nonsynonymous divergent sites); DoS; ⍺ MK . All variants were included.
File S4. Annotations of each transcript in noncoding regions with SNPeff: Ps (# of synonymous polymorphic sites); Pu (# of UTR polymorphic sites); Ds (# of synonymous divergent sites); Du (# of UTR divergent sites); DoS; ⍺ MK . All variants were included.
File S5. Annotations of each transcript in coding regions with SNPGenie: Ps (# of synonymous polymorphic sites); πs (synonymous diversity); Ss_p (total # of synonymous sites in the polymorphism data); Pn (# of nonsynonymous polymorphic sites); πn (nonsynonymous diversity); Sn_p (total # of nonsynonymous sites in the polymorphism data); Ds (# of synonymous divergent sites); ks (synonymous evolutionary rate); Ss_d (total # of synonymous sites in the divergence data); Dn (# of nonsynonymous divergent sites); kn (nonsynonymous evolutionary rate); Sn_d (total # of non
synonymous sites in the divergence data); DoS; ⍺ MK . All variants were included.
File S6. Gene expression values (RPKM summed over all transcripts) for each sample. Values were quantilenormalized across all samples.
File S7. Final dataset with all covariates, ⍺ MK , ωA MK and DoS for coding sites, excluding variants below 5% frequency.
File S8. Final dataset with all covariates, ⍺ MK , ωA MK and DoS for noncoding sites, excluding variants below 5%
frequency.
File S9. Final dataset with all covariates, ⍺ EWK , ωA EWK and deleterious SFS for coding sites obtained with the EyreWalker and Keightley method on binned data and using all variants.
AU  Fraisse, Christelle
ID  5757
KW  (mal)adaptation
KW  pleiotropy
KW  selective constraint
KW  evodevo
KW  gene expression
KW  Drosophila melanogaster
TI  Supplementary Files for "Pleiotropy modulates the efficacy of selection in Drosophila melanogaster"
ER 
TY  JOUR
AB  Cuprate superconductors have long been thought of as having strong electronic correlations but negligible spinorbit coupling. Using spin and angleresolved photoemission spectroscopy, we discovered that one of the most studied cuprate superconductors, Bi2212, has a nontrivial spin texture with a spinmomentum locking that circles the Brillouin zone center and a spinlayer locking that allows states of opposite spin to be localized in different parts of the unit cell. Our findings pose challenges for the vast majority of models of cuprates, such as the Hubbard model and its variants, where spinorbit interaction has been mostly neglected, and open the intriguing question of how the hightemperature superconducting state emerges in the presence of this nontrivial spin texture.
AU  Gotlieb, Kenneth
AU  Lin, ChiuYun
AU  Serbyn, Maksym
AU  Zhang, Wentao
AU  Smallwood, Christopher L.
AU  Jozwiak, Christopher
AU  Eisaki, Hiroshi
AU  Hussain, Zahid
AU  Vishwanath, Ashvin
AU  Lanzara, Alessandra
ID  5767
IS  6420
JF  Science
SN  00368075
TI  Revealing hidden spinmomentum locking in a hightemperature cuprate superconductor
VL  362
ER 
TY  JOUR
AB  Retroviruses assemble and bud from infected cells in an immature form and require proteolytic maturation for infectivity. The CA (capsid) domains of the Gag polyproteins assemble a protein lattice as a truncated sphere in the immature virion. Proteolytic cleavage of Gag induces dramatic structural rearrangements; a subset of cleaved CA subsequently assembles into the mature core, whose architecture varies among retroviruses. Murine leukemia virus (MLV) is the prototypical γretrovirus and serves as the basis of retroviral vectors, but the structure of the MLV CA layer is unknown. Here we have combined Xray crystallography with cryoelectron tomography to determine the structures of immature and mature MLV CA layers within authentic viral particles. This reveals the structural changes associated with maturation, and, by comparison with HIV1, uncovers conserved and variable features. In contrast to HIV1, most MLV CA is used for assembly of the mature core, which adopts variable, multilayered morphologies and does not form a closed structure. Unlike in HIV1, there is similarity between protein–protein interfaces in the immature MLV CA layer and those in the mature CA layer, and structural maturation of MLV could be achieved through domain rotations that largely maintain hexameric interactions. Nevertheless, the dramatic architectural change on maturation indicates that extensive disassembly and reassembly are required for mature core growth. The core morphology suggests that wrapping of the genome in CA sheets may be sufficient to protect the MLV ribonucleoprotein during cell entry.
AU  Qu, Kun
AU  Glass, Bärbel
AU  Doležal, Michal
AU  Schur, Florian
AU  Murciano, Brice
AU  Rein, Alan
AU  Rumlová, Michaela
AU  Ruml, Tomáš
AU  Kräusslich, HansGeorg
AU  Briggs, John A. G.
ID  5770
IS  50
JF  Proceedings of the National Academy of Sciences
SN  00278424
TI  Structure and architecture of immature and mature murine leukemia virus capsids
VL  115
ER 
TY  JOUR
AB  Bioluminescence is found across the entire tree of life, conferring a spectacular set of visually oriented functions from attracting mates to scaring off predators. Half a dozen different luciferins, molecules that emit light when enzymatically oxidized, are known. However, just one biochemical pathway for luciferin biosynthesis has been described in full, which is found only in bacteria. Here, we report identification of the fungal luciferase and three other key enzymes that together form the biosynthetic cycle of the fungal luciferin from caffeic acid, a simple and widespread metabolite. Introduction of the identified genes into the genome of the yeast Pichia pastoris along with caffeic acid biosynthesis genes resulted in a strain that is autoluminescent in standard media. We analyzed evolution of the enzymes of the luciferin biosynthesis cycle and found that fungal bioluminescence emerged through a series of events that included two independent gene duplications. The retention of the duplicated enzymes of the luciferin pathway in nonluminescent fungi shows that the gene duplication was followed by functional sequence divergence of enzymes of at least one gene in the biosynthetic pathway and suggests that the evolution of fungal bioluminescence proceeded through several closely related stepping stone nonluminescent biochemical reactions with adaptive roles. The availability of a complete eukaryotic luciferin biosynthesis pathway provides several applications in biomedicine and bioengineering.
AU  Kotlobay, Alexey A.
AU  Sarkisyan, Karen
AU  Mokrushina, Yuliana A.
AU  MarcetHouben, Marina
AU  Serebrovskaya, Ekaterina O.
AU  Markina, Nadezhda M.
AU  Gonzalez Somermeyer, Louisa
AU  Gorokhovatsky, Andrey Y.
AU  Vvedensky, Andrey
AU  Purtov, Konstantin V.
AU  Petushkov, Valentin N.
AU  Rodionova, Natalja S.
AU  Chepurnyh, Tatiana V.
AU  Fakhranurova, Liliia
AU  Guglya, Elena B.
AU  Ziganshin, Rustam
AU  Tsarkova, Aleksandra S.
AU  Kaskova, Zinaida M.
AU  Shender, Victoria
AU  Abakumov, Maxim
AU  Abakumova, Tatiana O.
AU  Povolotskaya, Inna S.
AU  Eroshkin, Fedor M.
AU  Zaraisky, Andrey G.
AU  Mishin, Alexander S.
AU  Dolgov, Sergey V.
AU  Mitiouchkina, Tatiana Y.
AU  Kopantzev, Eugene P.
AU  Waldenmaier, Hans E.
AU  Oliveira, Anderson G.
AU  Oba, Yuichi
AU  Barsova, Ekaterina
AU  Bogdanova, Ekaterina A.
AU  Gabaldón, Toni
AU  Stevani, Cassius V.
AU  Lukyanov, Sergey
AU  Smirnov, Ivan V.
AU  Gitelson, Josef I.
AU  Kondrashov, Fyodor
AU  Yampolsky, Ilia V.
ID  5780
IS  50
JF  Proceedings of the National Academy of Sciences of the United States of America
SN  00278424
TI  Genetically encodable bioluminescent system from fungi
VL  115
ER 
TY  JOUR
AB  Branching morphogenesis remains a subject of abiding interest. Although much is
known about the gene regulatory programs and signaling pathways that operate at
the cellular scale, it has remained unclear how the macroscopic features of branched
organs, including their size, network topology and spatial patterning, are encoded.
Lately, it has been proposed that, these features can be explained quantitatively in
several organs within a single unifying framework. Based on large
scale organ recon

structions and cell lineage tracing, it has been argued that morphogenesis follows
from the collective dynamics of sublineage
restricted self
renewing progenitor cells,
localized at ductal tips, that act cooperatively to drive a serial process of ductal elon

gation and stochastic tip bifurcation. By correlating differentiation or cell cycle exit
with proximity to maturing ducts, this dynamic results in the specification of a com
plex network of defined density and statistical organization. These results suggest
that, for several mammalian tissues, branched epithelial structures develop as a self
organized process, reliant upon a strikingly simple, but generic, set of local rules,
without recourse to a rigid and deterministic sequence of genetically programmed
events. Here, we review the basis of these findings and discuss their implications.
AU  Hannezo, Edouard B
AU  Simons, Benjamin D.
ID  5787
IS  9
JF  Development Growth and Differentiation
SN  00121592
TI  Statistical theory of branching morphogenesis
VL  60
ER 
TY  CONF
AB  In twoplayer games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner or payoff of the game. Such games are central in formal verification since they model the interaction between a nonterminating system and its environment. We study bidding games in which the players bid for the right to move the token. Two bidding rules have been defined. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the “bank” rather than the other player. While poorman reachability games have been studied before, we present, for the first time, results on infiniteduration poorman games. A central quantity in these games is the ratio between the two players’ initial budgets. The questions we study concern a necessary and sufficient ratio with which a player can achieve a goal. For reachability objectives, such threshold ratios are known to exist for both bidding rules. We show that the properties of poorman reachability games extend to complex qualitative objectives such as parity, similarly to the Richman case. Our most interesting results concern quantitative poorman games, namely poorman meanpayoff games, where we construct optimal strategies depending on the initial ratio, by showing a connection with randomturn based games. The connection in itself is interesting, because it does not hold for reachability poorman games. We also solve the complexity problems that arise in poorman bidding games.
AU  Avni, Guy
AU  Henzinger, Thomas A
AU  IbsenJensen, Rasmus
ID  5788
SN  03029743
TI  Infiniteduration poormanbidding games
VL  11316
ER 
TY  CONF
AB  Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An εperturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with · is the uniform norm (i.e., sup norm). We present a polynomialtime solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NPcomplete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.
AU  Fulek, Radoslav
AU  Tóth, Csaba D.
ID  5791
SN  9783030044138
TI  Crossing minimization in perturbed drawings
VL  11282
ER 
TY  JOUR
AB  We present an approach to interacting quantum manybody systems based on the notion of quantum groups, also known as qdeformed Lie algebras. In particular, we show that, if the symmetry of a free quantum particle corresponds to a Lie group G, in the presence of a manybody environment this particle can be described by a deformed group, Gq. Crucially, the single deformation parameter, q, contains all the information about the manyparticle interactions in the system. We exemplify our approach by considering a quantum rotor interacting with a bath of bosons, and demonstrate that extracting the value of q from closedform solutions in the perturbative regime allows one to predict the behavior of the system for arbitrary values of the impuritybath coupling strength, in good agreement with nonperturbative calculations. Furthermore, the value of the deformation parameter allows one to predict at which coupling strengths rotorbath interactions result in a formation of a stable quasiparticle. The approach based on quantum groups does not only allow for a drastic simplification of impurity problems, but also provides valuable insights into hidden symmetries of interacting manyparticle systems.
AU  Yakaboylu, Enderalp
AU  Shkolnikov, Mikhail
AU  Lemeshko, Mikhail
ID  5794
IS  25
JF  Physical Review Letters
SN  00319007
TI  Quantum groups as hidden symmetries of quantum impurities
VL  121
ER 
TY  JOUR
AB  Inside a twodimensional region (``cake""), there are m nonoverlapping tiles of a certain kind (``toppings""). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same ``certain kind,"" such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axisparallel rectangles. (4) The cake is an axisparallel rectilinear polygon and the toppings are axisparallel rectangles. In all four cases, we provide tight bounds on the number of blanks.
AU  Akopyan, Arseniy
AU  Segal Halevi, Erel
ID  58
IS  3
JF  SIAM Journal on Discrete Mathematics
TI  Counting blanks in polygonal arrangements
VL  32
ER 
TY  JOUR
AB  CLE peptides have been implicated in various developmental processes of plants and mediate their responses to environmental stimuli. However, the biological relevance of most CLE genes remains to be functionally characterized. Here, we report that CLE9, which is expressed in stomata, acts as an essential regulator in the induction of stomatal closure. Exogenous application of CLE9 peptides or overexpression of CLE9 effectively led to stomatal closure and enhanced drought tolerance, whereas CLE9 lossoffunction mutants were sensitivity to drought stress. CLE9induced stomatal closure was impaired in abscisic acid (ABA)deficient mutants, indicating that ABA is required for CLE9medaited guard cell signalling. We further deciphered that two guard cell ABAsignalling components, OST1 and SLAC1, were responsible for CLE9induced stomatal closure. MPK3 and MPK6 were activated by the CLE9 peptide, and CLE9 peptides failed to close stomata in mpk3 and mpk6 mutants. In addition, CLE9 peptides stimulated the induction of hydrogen peroxide (H2O2) and nitric oxide (NO) synthesis associated with stomatal closure, which was abolished in the NADPH oxidasedeficient mutants or nitric reductase mutants, respectively. Collectively, our results reveal a novel ABAdependent function of CLE9 in the regulation of stomatal apertures, thereby suggesting a potential role of CLE9 in the stress acclimatization of plants.
AU  Zhang, Luosha
AU  Shi, Xiong
AU  Zhang, Yutao
AU  Wang, Jiajing
AU  Yang, Jingwei
AU  Ishida, Takashi
AU  Jiang, Wenqian
AU  Han, Xiangyu
AU  Kang, Jingke
AU  Wang, Xuening
AU  Pan, Lixia
AU  Lv, Shuo
AU  Cao, Bing
AU  Zhang, Yonghong
AU  Wu, Jinbin
AU  Han, Huibin
AU  Hu, Zhubing
AU  Cui, Langjun
AU  Sawa, Shinichiro
AU  He, Junmin
AU  Wang, Guodong
ID  5830
JF  Plant Cell and Environment
SN  01407791
TI  CLE9 peptideinduced stomatal closure is mediated by abscisic acid, hydrogen peroxide, and nitric oxide in arabidopsis thaliana
ER 
TY  JOUR
AB  Spatial patterns are ubiquitous on the subcellular, cellular and tissue level, and can be studied using imaging techniques such as light and fluorescence microscopy. Imaging data provide quantitative information about biological systems; however, mechanisms causing spatial patterning often remain elusive. In recent years, spatiotemporal mathematical modelling has helped to overcome this problem. Yet, outliers and structured noise limit modelling of whole imaging data, and models often consider spatial summary statistics. Here, we introduce an integrated datadriven modelling approach that can cope with measurement artefacts and whole imaging data. Our approach combines mechanistic models of the biological processes with robust statistical models of the measurement process. The parameters of the integrated model are calibrated using a maximumlikelihood approach. We used this integrated modelling approach to study in vivo gradients of the chemokine (CC motif) ligand 21 (CCL21). CCL21 gradients guide dendritic cells and are important in the adaptive immune response. Using artificial data, we verified that the integrated modelling approach provides reliable parameter estimates in the presence of measurement noise and that bias and variance of these estimates are reduced compared to conventional approaches. The application to experimental data allowed the parametrization and subsequent refinement of the model using additional mechanisms. Among other results, modelbased hypothesis testing predicted lymphatic vesseldependent concentration of heparan sulfate, the binding partner of CCL21. The selected model provided an accurate description of the experimental data and was partially validated using published data. Our findings demonstrate that integrated statistical modelling of whole imaging data is computationally feasible and can provide novel biological insights.
AU  Hross, Sabrina
AU  Theis, Fabian J.
AU  Sixt, Michael K
AU  Hasenauer, Jan
ID  5858
IS  149
JF  Journal of the Royal Society Interface
SN  17425689
TI  Mechanistic description of spatial processes using integrative modelling of noisecorrupted imaging data
VL  15
ER 
TY  JOUR
AB  The emergence of syntax during childhood is a remarkable example of how complex correlations unfold in nonlinear ways through development. In particular, rapid transitions seem to occur as children reach the age of two, which seems to separate a twoword, treelike network of syntactic relations among words from the scalefree graphs associated with the adult, complex grammar. Here, we explore the evolution of syntax networks through language acquisition using the chromatic number, which captures the transition and provides a natural link to standard theories on syntactic structures. The data analysis is compared to a null model of network growth dynamics which is shown to display nontrivial and sensible differences. At a more general level, we observe that the chromatic classes define independent regions of the graph, and thus, can be interpreted as the footprints of incompatibility relations, somewhat as opposed to modularity considerations.
AU  CorominasMurtra, Bernat
AU  Fibla, Martí Sànchez
AU  Valverde, Sergi
AU  Solé, Ricard
ID  5859
IS  12
JF  Royal Society Open Science
SN  20545703
TI  Chromatic transitions in the emergence of syntax networks
VL  5
ER 
TY  JOUR
AB  A major problem for evolutionary theory is understanding the socalled openended nature of evolutionary change, from its definition to its origins. Openended evolution (OEE) refers to the unbounded increase in complexity that seems to characterize evolution on multiple scales. This property seems to be a characteristic feature of biological and technological evolution and is strongly tied to the generative potential associated with combinatorics, which allows the system to grow and expand their available state spaces. Interestingly, many complex systems presumably displaying OEE, from language to proteins, share a common statistical property: the presence of Zipf's Law. Given an inventory of basic items (such as words or protein domains) required to build more complex structures (sentences or proteins) Zipf's Law tells us that most of these elements are rare whereas a few of them are extremely common. Using algorithmic information theory, in this paper we provide a fundamental definition for openendedness, which can be understood as postulates. Its statistical counterpart, based on standard Shannon information theory, has the structure of a variational problem which is shown to lead to Zipf's Law as the expected consequence of an evolutionary process displaying OEE. We further explore the problem of information conservation through an OEE process and we conclude that statistical information (standard Shannon information) is not conserved, resulting in the paradoxical situation in which the increase of information content has the effect of erasing itself. We prove that this paradox is solved if we consider nonstatistical forms of information. This last result implies that standard information theory may not be a suitable theoretical framework to explore the persistence and increase of the information content in OEE systems.
AU  CorominasMurtra, Bernat
AU  Seoane, Luís F.
AU  Solé, Ricard
ID  5860
IS  149
JF  Journal of the Royal Society Interface
SN  17425689
TI  Zipf's Law, unbounded complexity and openended evolution
VL  15
ER 
TY  JOUR
AB  In zebrafish larvae, it is the cell type that determines how the cell responds to a chemokine signal.
AU  Alanko, Jonna H
AU  Sixt, Michael K
ID  5861
JF  eLife
SN  2050084X
TI  The cell sets the tone
VL  7
ER 
TY  JOUR
AB  Despite the remarkable number of scientific breakthroughs of the last 100 years, the treatment of neurodevelopmental
disorders (e.g., autism spectrum disorder, intellectual disability) remains a great challenge. Recent advancements in
genomics, such as wholeexome or wholegenome sequencing, have enabled scientists to identify numerous
mutations underlying neurodevelopmental disorders. Given the few hundred risk genes that have been discovered,
the etiological variability and the heterogeneous clinical presentation, the need for genotype — along with phenotype
based diagnosis of individual patients has become a requisite. In this review we look at recent advancements in
genomic analysis and their translation into clinical practice.
AU  Tarlungeanu, DoraClara
AU  Novarino, Gaia
ID  5888
IS  8
JF  Experimental & Molecular Medicine
SN  20926413
TI  Genomics in neurodevelopmental disorders: an avenue to personalized medicine
VL  50
ER 
TY  CONF
AB  Formalizing properties of systems with continuous dynamics is a challenging task. In this paper, we propose a formal framework for specifying and monitoring rich temporal properties of realvalued signals. We introduce signal firstorder logic (SFO) as a specification language that combines firstorder logic with linearreal arithmetic and unary function symbols interpreted as piecewiselinear signals. We first show that while the satisfiability problem for SFO is undecidable, its membership and monitoring problems are decidable. We develop an offline monitoring procedure for SFO that has polynomial complexity in the size of the input trace and the specification, for a fixed number of quantifiers and function symbols. We show that the algorithm has computation time linear in the size of the input trace for the important fragment of boundedresponse specifications interpreted over input traces with finite variability. We can use our results to extend signal temporal logic with firstorder quantifiers over time and value parameters, while preserving its efficient monitoring. We finally demonstrate the practical appeal of our logic through a case study in the microelectronics domain.
AU  Bakhirkin, Alexey
AU  Ferrere, Thomas
AU  Henzinger, Thomas A
AU  Nickovicl, Deian
ID  5959
SN  9781538655603
T2  2018 International Conference on Embedded Software
TI  Keynote: The firstorder logic of signals
ER 
TY  JOUR
AB  In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a boundederror context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion.
AU  Rohou, Simon
AU  Franek, Peter
AU  Aubry, Clément
AU  Jaulin, Luc
ID  5960
IS  12
JF  The International Journal of Robotics Research
SN  02783649
TI  Proving the existence of loops in robot trajectories
VL  37
ER 
TY  CONF
AB  Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neural networks. Given the recent practical focus on distributed machine learning, significant work has been dedicated to the convergence properties of this algorithm under the inconsistent and noisy updates arising from execution in a distributed environment. However, surprisingly, the convergence properties of this classic algorithm in the standard sharedmemory model are still not wellunderstood. In this work, we address this gap, and provide new convergence bounds for lockfree concurrent stochastic gradient descent, executing in the classic asynchronous shared memory model, against a strong adaptive adversary. Our results give improved upper and lower bounds on the "price of asynchrony'' when executing the fundamental SGD algorithm in a concurrent setting. They show that this classic optimization tool can converge faster and with a wider range of parameters than previously known under asynchronous iterations. At the same time, we exhibit a fundamental tradeoff between the maximum delay in the system and the rate at which SGD can converge, which governs the set of parameters under which this algorithm can still work efficiently.
AU  Alistarh, DanAdrian
AU  De Sa, Christopher
AU  Konstantinov, Nikola H
ID  5962
SN  9781450357951
T2  Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  PODC '18
TI  The convergence of stochastic gradient descent in asynchronous shared memory
ER 
TY  CONF
AB  There has been significant progress in understanding the parallelism inherent to iterative sequential algorithms: for many classic algorithms, the depth of the dependence structure is now well understood, and scheduling techniques have been developed to exploit this shallow dependence structure for efficient parallel implementations. A related, applied research strand has studied methods by which certain iterative taskbased algorithms can be efficiently parallelized via relaxed concurrent priority schedulers. These allow for high concurrency when inserting and removing tasks, at the cost of executing superfluous work due to the relaxed semantics of the scheduler. In this work, we take a step towards unifying these two research directions, by showing that there exists a family of relaxed priority schedulers that can efficiently and deterministically execute classic iterative algorithms such as greedy maximal independent set (MIS) and matching. Our primary result shows that, given a randomized scheduler with an expected relaxation factor of k in terms of the maximum allowed priority inversions on a task, and any graph on n vertices, the scheduler is able to execute greedy MIS with only an additive factor of \poly(k) expected additional iterations compared to an exact (but not scalable) scheduler. This counterintuitive result demonstrates that the overhead of relaxation when computing MIS is not dependent on the input size or structure of the input graph. Experimental results show that this overhead can be clearly offset by the gain in performance due to the highly scalable scheduler. In sum, we present an efficient method to deterministically parallelize iterative sequential algorithms, with provable runtime guarantees in terms of the number of executed tasks to completion.
AU  Alistarh, DanAdrian
AU  Brown, Trevor A
AU  Kopinsky, Justin
AU  Nadiradze, Giorgi
ID  5963
SN  9781450357951
T2  Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  PODC '18
TI  Relaxed schedulers can efficiently parallelize iterative algorithms
ER 
TY  CONF
AB  A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarsegrained lockbased algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc.
AU  Aksenov, Vitaly
AU  Alistarh, DanAdrian
AU  Kuznetsov, Petr
ID  5964
SN  9781450357951
T2  Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  PODC '18
TI  Brief Announcement: Performance prediction for coarsegrained locking
ER 
TY  CONF
AB  Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue~\citeMQ pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting~\citeAKLN17. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic poweroftwochoices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps.
AU  Alistarh, DanAdrian
AU  Brown, Trevor A
AU  Kopinsky, Justin
AU  Li, Jerry Z.
AU  Nadiradze, Giorgi
ID  5965
SN  9781450357999
T2  Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  SPAA '18
TI  Distributionally linearizable data structures
ER 
TY  CONF
AB  The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem. Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins'' and "requestor aborts'' implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems. We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms. Moreover, we prove that, under a simplified adversarial model, our algorithms are constantcompetitive with the offline optimum in terms of throughput. We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to nontrivial performance improvements for classic concurrent data structures.
AU  Alistarh, DanAdrian
AU  Haider, Syed Kamran
AU  Kübler, Raphael
AU  Nadiradze, Giorgi
ID  5966
SN  9781450357999
T2  Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  SPAA '18
TI  The transactional conflict problem
ER 
TY  CONF
AB  The Big Match is a multistage twoplayer game. In each stage Player 1 hides one or two pebbles in his hand, and his opponent has to guess that number; Player 1 loses a point if Player 2 is correct, and otherwise he wins a point. As soon as Player 1 hides one pebble, the players cannot change their choices in any future stage.
Blackwell and Ferguson (1968) give an εoptimal strategy for Player 1 that hides, in each stage, one pebble with a probability that depends on the entire past history. Any strategy that depends just on the clock or on a finite memory is worthless. The longstanding natural open problem has been whether every strategy that depends just on the clock and a finite memory is worthless. We prove that there is such a strategy that is εoptimal. In fact, we show that just two states of memory are sufficient.
AU  Hansen, Kristoffer Arnsfelt
AU  IbsenJensen, Rasmus
AU  Neyman, Abraham
ID  5967
SN  9781450358293
T2  Proceedings of the 2018 ACM Conference on Economics and Computation  EC '18
TI  The Big Match with a clock and a bit of memory
ER 
TY  JOUR
AB  We consider a Wignertype ensemble, i.e. large hermitian N×N random matrices H=H∗ with centered independent entries and with a general matrix of variances Sxy=𝔼∣∣Hxy∣∣2. The norm of H is asymptotically given by the maximum of the support of the selfconsistent density of states. We establish a bound on this maximum in terms of norms of powers of S that substantially improves the earlier bound 2∥S∥1/2∞ given in [O. Ajanki, L. Erdős and T. Krüger, Universality for general Wignertype matrices, Prob. Theor. Rel. Fields169 (2017) 667–727]. The key element of the proof is an effective Markov chain approximation for the contributions of the weighted Dyck paths appearing in the iterative solution of the corresponding Dyson equation.
AU  Erdös, László
AU  Mühlbacher, Peter
ID  5971
JF  Random matrices: Theory and applications
SN  20103263
TI  Bounds on the norm of Wignertype random matrices
ER 
TY  JOUR
AB  We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Harvey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formulation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition.
AU  Kolmogorov, Vladimir
ID  5975
IS  6
JF  SIAM Journal on Computing
SN  00975397
TI  Commutativity in the algorithmic Lovász local lemma
VL  47
ER 
TY  JOUR
AB  We propose FlexMaps, a novel framework for fabricating smooth shapes out of flat, flexible panels with tailored mechanical properties. We start by mapping the 3D surface onto a 2D domain as in traditional UV mapping to design a set of deformable flat panels called FlexMaps. For these panels, we design and obtain specific mechanical properties such that, once they are assembled, the static equilibrium configuration matches the desired 3D shape. FlexMaps can be fabricated from an almost rigid material, such as wood or plastic, and are made flexible in a controlled way by using computationally designed spiraling microstructures.
AU  Malomo, Luigi
AU  Perez Rodriguez, Jesus
AU  Iarussi, Emmanuel
AU  Pietroni, Nico
AU  Miguel, Eder
AU  Cignoni, Paolo
AU  Bickel, Bernd
ID  5976
IS  6
JF  ACM Transactions on Graphics
SN  07300301
TI  FlexMaps: Computational design of flat flexible shells for shaping 3D objects
VL  37
ER 
TY  CONF
AB  We consider the MAPinference problem for graphical models,which is a valued constraint satisfaction problem defined onreal numbers with a natural summation operation. We proposea family of relaxations (different from the famous SheraliAdams hierarchy), which naturally define lower bounds for itsoptimum. This family always contains a tight relaxation andwe give an algorithm able to find it and therefore, solve theinitial nonrelaxed NPhard problem.The relaxations we consider decompose the original probleminto two nonoverlapping parts: an easy LPtight part and adifficult one. For the latter part a combinatorial solver must beused. As we show in our experiments, in a number of applications the second, difficult part constitutes only a small fractionof the whole problem. This property allows to significantlyreduce the computational time of the combinatorial solver andtherefore solve problems which were out of reach before.
AU  Haller, Stefan
AU  Swoboda, Paul
AU  Savchynskyy, Bogdan
ID  5978
T2  Proceedings of the 32st AAAI Conference on Artificial Intelligence
TI  Exact MAPinference by confining combinatorial search with LP relaxation
ER 
TY  JOUR
AB  In the present work, we detail a fast and simple solutionbased method to synthesize hexagonal SnSe2 nanoplates (NPLs) and their use to produce crystallographically textured SnSe2 nanomaterials. We also demonstrate that the same strategy can be used to produce orthorhombic SnSe nanostructures and nanomaterials. NPLs are grown through a screw dislocationdriven mechanism. This mechanism typically results in pyramidal structures, but we demonstrate here that the growth from multiple dislocations results in flowerlike structures. Crystallographically textured SnSe2 bulk nanomaterials obtained from the hot pressing of these SnSe2 structures display highly anisotropic charge and heat transport properties and thermoelectric (TE) figures of merit limited by relatively low electrical conductivities. To improve this parameter, SnSe2 NPLs are blended here with metal nanoparticles. The electrical conductivities of the blends are significantly improved with respect to bare SnSe2 NPLs, what translates into a threefold increase of the TE Figure of merit, reaching unprecedented ZT values up to 0.65.
AU  Zhang, Yu
AU  Liu, Yu
AU  Lim, Khak Ho
AU  Xing, Congcong
AU  Li, Mengyao
AU  Zhang, Ting
AU  Tang, Pengyi
AU  Arbiol, Jordi
AU  Llorca, Jordi
AU  Ng, Ka Ming
AU  Ibáñez, Maria
AU  Guardia, Pablo
AU  Prato, Mirko
AU  Cadavid, Doris
AU  Cabot, Andreu
ID  5982
IS  52
JF  Angewandte Chemie International Edition
SN  14337851
TI  Tin diselenide molecular precursor for solutionprocessable thermoelectric materials
VL  57
ER 
TY  JOUR
AB  We study a quantum impurity possessing both translational and internal rotational degrees of freedom interacting with a bosonic bath. Such a system corresponds to a “rotating polaron,” which can be used to model, e.g., a rotating molecule immersed in an ultracold Bose gas or superfluid helium. We derive the Hamiltonian of the rotating polaron and study its spectrum in the weak and strongcoupling regimes using a combination of variational, diagrammatic, and meanfield approaches. We reveal how the coupling between linear and angular momenta affects stable quasiparticle states, and demonstrate that internal rotation leads to an enhanced selflocalization in the translational degrees of freedom.
AU  Yakaboylu, Enderalp
AU  Midya, Bikashkali
AU  Deuchert, Andreas
AU  Leopold, Nikolai K
AU  Lemeshko, Mikhail
ID  5983
IS  22
JF  Physical Review B
SN  24699950
TI  Theory of the rotating polaron: Spectrum and selflocalization
VL  98
ER 
TY  JOUR
AB  Gproteincoupled receptors (GPCRs) form the largest receptor family, relay environmental stimuli to changes in cell behavior and represent prime drug targets. Many GPCRs are classified as orphan receptors because of the limited knowledge on their ligands and coupling to cellular signaling machineries. Here, we engineer a library of 63 chimeric receptors that contain the signaling domains of human orphan and understudied GPCRs functionally linked to the lightsensing domain of rhodopsin. Upon stimulation with visible light, we identify activation of canonical cell signaling pathways, including cAMP, Ca2+, MAPK/ERK, and Rhodependent pathways, downstream of the engineered receptors. For the human pseudogene GPR33, we resurrect a signaling function that supports its hypothesized role as a pathogen entry site. These results demonstrate that substituting unknown chemical activators with a light switch can reveal information about protein function and provide an optically controlled protein library for exploring the physiology and therapeutic potential of understudied GPCRs.
AU  Morri, Maurizio
AU  SanchezRomero, Inmaculada
AU  Tichy, AlexandraMadelaine
AU  Kainrath, Stephanie
AU  Gerrard, Elliot J.
AU  Hirschfeld, Priscila
AU  Schwarz, Jan
AU  Janovjak, Harald L
ID  5984
IS  1
JF  Nature Communications
SN  20411723
TI  Optical functionalization of human class A orphan Gproteincoupled receptors
VL  9
ER 
TY  JOUR
AB  Schistosomes are the causative agents of schistosomiasis, a neglected tropical disease affecting over 230 million people worldwide.Additionally to their major impact on human health, they are also models of choice in evolutionary biology. These parasitic flatwormsare unique among the common hermaphroditic trematodes as they have separate sexes. This socalled “evolutionary scandal”displays a female heterogametic genetic sexdetermination system (ZZ males and ZW females), as well as a pronounced adult sexualdimorphism. These phenotypic differences are determined by a shared set of genes in both sexes, potentially leading to intralocussexual conflicts. To resolve these conflicts in sexually selected traits, molecular mechanisms such as sexbiased gene expression couldoccur, but parentoforigin gene expression also provides an alternative. In this work we investigated the latter mechanism, that is,genes expressed preferentially from either the maternal or the paternal allele, inSchistosoma mansonispecies. To this end, transcriptomes from male and female hybrid adults obtained by strain crosses were sequenced. Strainspecific single nucleotide polymorphism (SNP) markers allowed us to discriminate the parental origin, while reciprocal crosses helped to differentiate parentalexpression from strainspecific expression. We identified genes containing SNPs expressed in a parentoforigin manner consistentwith paternal and maternal imprints. Although the majority of the SNPs was identified in mitochondrial and Zspecific loci, theremaining SNPs found in male and female transcriptomes were situated in genes that have the potential to explain sexual differencesin schistosome parasites. Furthermore, we identified and validated four new Zspecific scaffolds.
AU  KincaidSmith, Julien
AU  Picard, Marion A L
AU  Cosseau, Céline
AU  Boissier, Jérôme
AU  Severac, Dany
AU  Grunau, Christoph
AU  Toulza, Eve
ID  5989
IS  3
JF  Genome Biology and Evolution
SN  17596653
TI  ParentofOriginDependent Gene Expression in Male and Female Schistosome Parasites
VL  10
ER 
TY  JOUR
AB  A Ge–Si core–shell nanowire is used to realize a Josephson field‐effect transistor with highly transparent contacts to superconducting leads. By changing the electric field, access to two distinct regimes, not combined before in a single device, is gained: in the accumulation mode the device is highly transparent and the supercurrent is carried by multiple subbands, while near depletion, the supercurrent is carried by single‐particle levels of a strongly coupled quantum dot operating in the few‐hole regime. These results establish Ge–Si nanowires as an important platform for hybrid superconductor–semiconductor physics and Majorana fermions.
AU  Ridderbos, Joost
AU  Brauns, Matthias
AU  Shen, Jie
AU  de Vries, Folkert K.
AU  Li, Ang
AU  Bakkers, Erik P. A. M.
AU  Brinkman, Alexander
AU  Zwanenburg, Floris A.
ID  5990
IS  44
JF  Advanced Materials
SN  09359648
TI  Josephson effect in a fewhole quantum dot
VL  30
ER 
TY  JOUR
AB  Lamellipodia are flat membrane protrusions formed during mesenchymal motion. Polymerization at the leading edge assembles the actin filament network and generates protrusion force. How this force is supported by the network and how the assembly rate is shared between protrusion and network retrograde flow determines the protrusion rate. We use mathematical modeling to understand experiments changing the Factin density in lamellipodia of B16F1 melanoma cells by modulation of Arp2/3 complex activity or knockout of the formins FMNL2 and FMNL3. Cells respond to a reduction of density with a decrease of protrusion velocity, an increase in the ratio of force to filament number, but constant network assembly rate. The relation between protrusion force and tension gradient in the Factin network and the density dependency of friction, elasticity, and viscosity of the network explain the experimental observations. The formins act as filament nucleators and elongators with differential rates. Modulation of their activity suggests an effect on network assembly rate. Contrary to these expectations, the effect of changes in elongator composition is much weaker than the consequences of the density change. We conclude that the force acting on the leading edge membrane is the force required to drive Factin network retrograde flow.
AU  Dolati, Setareh
AU  Kage, Frieda
AU  Mueller, Jan
AU  Müsken, Mathias
AU  Kirchner, Marieluise
AU  Dittmar, Gunnar
AU  Sixt, Michael K
AU  Rottner, Klemens
AU  Falcke, Martin
ID  5992
IS  22
JF  Molecular Biology of the Cell
SN  10591524
TI  On the relation between filament density, force generation, and protrusion rate in mesenchymal cell motility
VL  29
ER 
TY  JOUR
AB  In this article, we consider the termination problem of probabilistic programs with realvalued variables. Thequestions concerned are: qualitative ones that ask (i) whether the program terminates with probability 1(almostsure termination) and (ii) whether the expected termination time is finite (finite termination); andquantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) tocompute a boundBsuch that the probability not to terminate afterBsteps decreases exponentially (concentration problem). To solve these questions, we utilize the notion of ranking supermartingales, which isa powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmicsynthesis of linear rankingsupermartingales over affine probabilistic programs (Apps) with both angelic anddemonic nondeterminism. An important subclass of Apps is LRApp which is defined as the class of all Appsover which a linear rankingsupermartingale exists.Our main contributions are as follows. Firstly, we show that the membership problem of LRApp (i) canbe decided in polynomial time for Apps with at most demonic nondeterminism, and (ii) isNPhard and inPSPACEfor Apps with angelic nondeterminism. Moreover, theNPhardness result holds already for Appswithout probability and demonic nondeterminism. Secondly, we show that the concentration problem overLRApp can be solved in the same complexity as for the membership problem of LRApp. Finally, we show thatthe expectation problem over LRApp can be solved in2EXPTIMEand isPSPACEhard even for Apps withoutprobability and nondeterminism (i.e., deterministic programs). Our experimental results demonstrate theeffectiveness of our approach to answer the qualitative and quantitative questions over Apps with at mostdemonic nondeterminism.
AU  Chatterjee, Krishnendu
AU  Fu, Hongfei
AU  Novotný, Petr
AU  Hasheminezhad, Rouzbeh
ID  5993
IS  2
JF  ACM Transactions on Programming Languages and Systems
SN  01640925
TI  Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
VL  40
ER 
TY  JOUR
AB  Motivation
Computational prediction of the effect of mutations on protein stability is used by researchers in many fields. The utility of the prediction methods is affected by their accuracy and bias. Bias, a systematic shift of the predicted change of stability, has been noted as an issue for several methods, but has not been investigated systematically. Presence of the bias may lead to misleading results especially when exploring the effects of combination of different mutations.
Results
Here we use a protocol to measure the bias as a function of the number of introduced mutations. It is based on a selfconsistency test of the reciprocity the effect of a mutation. An advantage of the used approach is that it relies solely on crystal structures without experimentally measured stability values. We applied the protocol to four popular algorithms predicting change of protein stability upon mutation, FoldX, Eris, Rosetta and IMutant, and found an inherent bias. For one program, FoldX, we manage to substantially reduce the bias using additional relaxation by Modeller. Authors using algorithms for predicting effects of mutations should be aware of the bias described here.
AU  Usmanova, Dinara R
AU  Bogatyreva, Natalya S
AU  Ariño Bernad, Joan
AU  Eremina, Aleksandra A
AU  Gorshkova, Anastasiya A
AU  Kanevskiy, German M
AU  Lonishin, Lyubov R
AU  Meister, Alexander V
AU  Yakupova, Alisa G
AU  Kondrashov, Fyodor
AU  Ivankov, Dmitry
ID  5995
IS  21
JF  Bioinformatics
SN  13674803
TI  Selfconsistency test reveals systematic bias in programs for prediction change of stability upon mutation
VL  34
ER 
TY  JOUR
AB  In pipes, turbulence sets in despite the linear stability of the laminar Hagen–Poiseuille flow. The Reynolds number ( ) for which turbulence first appears in a given experiment – the ‘natural transition point’ – depends on imperfections of the setup, or, more precisely, on the magnitude of finite amplitude perturbations. At onset, turbulence typically only occupies a certain fraction of the flow, and this fraction equally is found to differ from experiment to experiment. Despite these findings, Reynolds proposed that after sufficiently long times, flows may settle to steady conditions: below a critical velocity, flows should (regardless of initial conditions) always return to laminar, while above this velocity, eddying motion should persist. As will be shown, even in pipes several thousand diameters long, the spatiotemporal intermittent flow patterns observed at the end of the pipe strongly depend on the initial conditions, and there is no indication that different flow patterns would eventually settle to a (statistical) steady state. Exploiting the fact that turbulent puffs do not age (i.e. they are memoryless), we continuously recreate the puff sequence exiting the pipe at the pipe entrance, and in doing so introduce periodic boundary conditions for the puff pattern. This procedure allows us to study the evolution of the flow patterns for arbitrary long times, and we find that after times in excess of advective time units, indeed a statistical steady state is reached. Although the resulting flows remain spatiotemporally intermittent, puff splitting and decay rates eventually reach a balance, so that the turbulent fraction fluctuates around a welldefined level which only depends on . In accordance with Reynolds’ proposition, we find that at lower (here 2020), flows eventually always resume to laminar, while for higher ( ), turbulence persists. The critical point for pipe flow hence falls in the interval of $2020 , which is in very good agreement with the recently proposed value of . The latter estimate was based on singlepuff statistics and entirely neglected puff interactions. Unlike in typical contact processes where such interactions strongly affect the percolation threshold, in pipe flow, the critical point is only marginally influenced. Interactions, on the other hand, are responsible for the approach to the statistical steady state. As shown, they strongly affect the resulting flow patterns, where they cause ‘puff clustering’, and these regions of large puff densities are observed to travel across the puff pattern in a wavelike fashion.
AU  Vasudevan, Mukund
AU  Hof, Björn
ID  5996
JF  Journal of Fluid Mechanics
SN  00221120
TI  The critical point of the transition to turbulence in pipe flow
VL  839
ER 
TY  JOUR
AB  Genome amplification and cellular senescence are commonly associated with pathological processes. While physiological roles for polyploidization and senescence have been described in mouse development, controversy exists over their significance in humans. Here, we describe tetraploidization and senescence as phenomena of normal human placenta development. During pregnancy, placental extravillous trophoblasts (EVTs) invade the pregnant endometrium, termed decidua, to establish an adapted microenvironment required for the developing embryo. This process is critically dependent on continuous cell proliferation and differentiation, which is thought to follow the classical model of cell cycle arrest prior to terminal differentiation. Strikingly, flow cytometry and DNAseq revealed that EVT formation is accompanied with a genomewide polyploidization, independent of mitotic cycles. DNA replication in these cells was analysed by a fluorescent cellcycle indicator reporter system, cell cycle marker expression and EdU incorporation. Upon invasion into the decidua, EVTs widely lose their replicative potential and enter a senescent state characterized by high senescenceassociated (SA) βgalactosidase activity, induction of a SA secretory phenotype as well as typical metabolic alterations. Furthermore, we show that the shift from endocycledependent genome amplification to growth arrest is disturbed in androgenic complete hydatidiform moles (CHM), a hyperplastic pregnancy disorder associated with increased risk of developing choriocarinoma. Senescence is decreased in CHMEVTs, accompanied by exacerbated endoreduplication and hyperploidy. We propose induction of cellular senescence as a ploidylimiting mechanism during normal human placentation and unravel a link between excessive polyploidization and reduced senescence in CHM.
AU  Velicky, Philipp
AU  Meinhardt, Gudrun
AU  Plessl, Kerstin
AU  Vondra, Sigrid
AU  Weiss, Tamara
AU  Haslinger, Peter
AU  Lendl, Thomas
AU  Aumayr, Karin
AU  Mairhofer, Mario
AU  Zhu, Xiaowei
AU  Schütz, Birgit
AU  Hannibal, Roberta L.
AU  Lindau, Robert
AU  Weil, Beatrix
AU  Ernerudh, Jan
AU  Neesen, Jürgen
AU  Egger, Gerda
AU  Mikula, Mario
AU  Röhrl, Clemens
AU  Urban, Alexander E.
AU  Baker, Julie
AU  Knöfler, Martin
AU  Pollheimer, Jürgen
ID  5998
IS  10
JF  PLOS Genetics
SN  15537404
TI  Genome amplification and cellular senescence are hallmarks of human placenta development
VL  14
ER 
TY  JOUR
AB  We introduce for each quiver Q and each algebraic oriented cohomology theory A, the cohomological Hall algebra (CoHA) of Q, as the Ahomology of the moduli of representations of the preprojective algebra of Q. This generalizes the Ktheoretic Hall algebra of commuting varieties defined by SchiffmannVasserot. When A is the Morava Ktheory, we show evidence that this algebra is a candidate for Lusztig's reformulated conjecture on modular representations of algebraic groups.
We construct an action of the preprojective CoHA on the Ahomology of Nakajima quiver varieties. We compare this with the action of the Borel subalgebra of Yangian when A is the intersection theory. We also give a shuffle algebra description of this CoHA in terms of the underlying formal group law of A. As applications, we obtain a shuffle description of the Yangian.
AU  Yang, Yaping
AU  Zhao, Gufang
ID  5999
IS  5
JF  Proceedings of the London Mathematical Society
SN  00246115
TI  The cohomological Hall algebra of a preprojective algebra
VL  116
ER 
TY  JOUR
AB  The Bogoliubov free energy functional is analysed. The functional serves as a model of a translationinvariant Bose gas at positive temperature. We prove the existence of minimizers in the case of repulsive interactions given by a sufficiently regular twobody potential. Furthermore, we prove the existence of a phase transition in this model and provide its phase diagram.
AU  Napiórkowski, Marcin M
AU  Reuvers, Robin
AU  Solovej, Jan Philip
ID  6002
IS  3
JF  Archive for Rational Mechanics and Analysis
SN  00039527
TI  The Bogoliubov free energy functional I: Existence of minimizers and phase diagram
VL  229
ER 
TY  JOUR
AB  Digital fabrication devices are powerful tools for creating tangible reproductions of 3D digital models. Most available printing technologies aim at producing an accurate copy of a tridimensional shape. However, fabrication technologies can also be used to create a stylistic representation of a digital shape. We refer to this class of methods as ‘stylized fabrication methods’. These methods abstract geometric and physical features of a given shape to create an unconventional representation, to produce an optical illusion or to devise a particular interaction with the fabricated model. In this state‐of‐the‐art report, we classify and overview this broad and emerging class of approaches and also propose possible directions for future research.
AU  Bickel, Bernd
AU  Cignoni, Paolo
AU  Malomo, Luigi
AU  Pietroni, Nico
ID  6003
IS  6
JF  Computer Graphics Forum
SN  01677055
TI  State of the art on stylized fabrication
VL  37
ER 
TY  CONF
AB  Network games are widely used as a model for selfish resourceallocation problems. In the classicalmodel, each player selects a path connecting her source and target vertices. The cost of traversingan edge depends on theload; namely, number of players that traverse it. Thus, it abstracts the factthat different users may use a resource at different times and for different durations, which playsan important role in determining the costs of the users in reality. For example, when transmittingpackets in a communication network, routing traffic in a road network, or processing a task in aproduction system, actual sharing and congestion of resources crucially depends on time.In [13], we introducedtimed network games, which add a time component to network games.Each vertexvin the network is associated with a cost function, mapping the load onvto theprice that a player pays for staying invfor one time unit with this load. Each edge in thenetwork is guarded by the time intervals in which it can be traversed, which forces the players tospend time in the vertices. In this work we significantly extend the way time can be referred toin timed network games. In the model we study, the network is equipped withclocks, and, as intimed automata, edges are guarded by constraints on the values of the clocks, and their traversalmay involve a reset of some clocks. We argue that the stronger model captures many realisticnetworks. The addition of clocks breaks the techniques we developed in [13] and we developnew techniques in order to show that positive results on classic network games carry over to thestronger timed setting.
AU  Avni, Guy
AU  Guha, Shibashis
AU  Kupferman, Orna
ID  6005
SN  18688969
TI  Timed network games with clocks
VL  117
ER 
TY  JOUR
AB  Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. Search problems for NGs include finding special strategy profiles such as a Nash equilibrium and a globallyoptimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state spaces. We describe an abstractionrefinement methodology for reasoning about NGs. Our methodology is based on an abstraction function that maps the state space of an NG to a much smaller state space. We search for a global optimum and a Nash equilibrium by reasoning on an under and an overapproximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. We extend the abstractionrefinement methodology to labeled networks, where the objectives of the players are regular languages. Our experimental results demonstrate the effectiveness of the methodology.
AU  Avni, Guy
AU  Guha, Shibashis
AU  Kupferman, Orna
ID  6006
IS  3
JF  Games
SN  20734336
TI  An abstractionrefinement methodology for reasoning about network games
VL  9
ER 
TY  JOUR
AB  The optic tectum (TeO), or superior colliculus, is a multisensory midbrain center that organizes spatially orienting responses to relevant stimuli. To define the stimulus with the highest priority at each moment, a network of reciprocal connections between the TeO and the isthmi promotes competition between concurrent tectal inputs. In the avian midbrain, the neurons mediating enhancement and suppression of tectal inputs are located in separate isthmic nuclei, facilitating the analysis of the neural processes that mediate competition. A specific subset of radial neurons in the intermediate tectal layers relay retinal inputs to the isthmi, but at present it is unclear whether separate neurons innervate individual nuclei or a single neural type sends a common input to several of them. In this study, we used in vitro neural tracing and cellfilling experiments in chickens to show that single neurons innervate, via axon collaterals, the three nuclei that comprise the isthmotectal network. This demonstrates that the input signals representing the strength of the incoming stimuli are simultaneously relayed to the mechanisms promoting both enhancement and suppression of the input signals. By performing in vivo recordings in anesthetized chicks, we also show that this common input generates synchrony between both antagonistic mechanisms, demonstrating that activity enhancement and suppression are closely coordinated. From a computational point of view, these results suggest that these tectal neurons constitute integrative nodes that combine inputs from different sources to drive in parallel several concurrent neural processes, each performing complementary functions within the network through different firing patterns and connectivity.
AU  GarridoCharad, Florencia
AU  Vega Zuniga, Tomas A
AU  GutiérrezIbáñez, Cristián
AU  Fernandez, Pedro
AU  LópezJury, Luciana
AU  GonzálezCabrera, Cristian
AU  Karten, Harvey J.
AU  Luksch, Harald
AU  Marín, Gonzalo J.
ID  6010
IS  32
JF  Proceedings of the National Academy of Sciences
SN  00278424
TI  “Shepherd’s crook” neurons drive and synchronize the enhancing and suppressive mechanisms of the midbrain stimulus selection network
VL  115
ER 
TY  CONF
AB  We establish a datadependent notion of algorithmic stability for Stochastic Gradient Descent (SGD), and employ it to develop novel generalization bounds. This is in contrast to previous distributionfree algorithmic stability results for SGD which depend on the worstcase constants. By virtue of the datadependent argument, our bounds provide new insights into learning with SGD on convex and nonconvex problems. In the convex case, we show that the bound on the generalization error depends on the risk at the initialization point. In the nonconvex case, we prove that the expected curvature of the objective function around the initialization point has crucial influence on the generalization error. In both cases, our results suggest a simple datadriven strategy to stabilize SGD by prescreening its initialization. As a corollary, our results allow us to show optimistic generalization bounds that exhibit fast convergence rates for SGD subject to a vanishing empirical risk and low noise of stochastic gradient.
AU  Kuzborskij, Ilja
AU  Lampert, Christoph
ID  6011
T2  Proceedings of the 35 th International Conference on Machine Learning
TI  Datadependent stability of stochastic gradient descent
VL  80
ER 
TY  CONF
AB  We present an approach to identify concise equations from data using a shallow neural network approach. In contrast to ordinary blackbox regression, this approach allows understanding functional relations and generalizing them from observed data to unseen parts of the parameter space. We show how to extend the class of learnable equations for a recently proposed equation learning network to include divisions, and we improve the learning and model selection strategy to be useful for challenging realworld data. For systems governed by analytical expressions, our method can in many cases identify the true underlying equation and extrapolate to unseen domains. We demonstrate its effectiveness by experiments on a cartpendulum system, where only 2 random rollouts are required to learn the forward dynamics and successfully achieve the swingup task.
AU  Sahoo, Subham
AU  Lampert, Christoph
AU  Martius, Georg S
ID  6012
T2  Proceedings of the 35th International Conference on Machine Learning
TI  Learning equations for extrapolation and control
VL  80
ER 
TY  JOUR
AB  The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δmatroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even Δmatroids, we then extend the tractability result to larger classes of Δmatroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, coindependent, compact, local, linear, and binary, with the following caveat:We represent Δmatroids by lists of tuples, while the last two use a representation by matrices. Since an n ×n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Δmatroids.
AU  Kazda, Alexandr
AU  Kolmogorov, Vladimir
AU  Rolinek, Michal
ID  6032
IS  2
JF  ACM Transactions on Algorithms
TI  Even deltamatroids and the complexity of planar boolean CSPs
VL  15
ER 
TY  JOUR
AB  We establish the existence of a global solution for a new family of fluidlike equations, which are obtained in certain regimes in as the meanfield evolution of the supercurrent density in a (2D section of a) typeII superconductor with pinning and with imposed electric current. We also consider general vortexsheet initial data, and investigate the uniqueness and regularity properties of the solution. For some choice of parameters, the equation under investigation coincides with the socalled lake equation from 2D shallow water fluid dynamics, and our analysis then leads to a new existence result for rough initial data.
AU  Duerinckx, Mitia
AU  Fischer, Julian L
ID  606
IS  5
JF  Annales de l'Institut Henri Poincare (C) Non Linear Analysis
TI  Wellposedness for meanfield evolutions arising in superconductivity
VL  35
ER 
TY  JOUR
AB  Animal social networks are shaped by multiple selection pressures, including the need to ensure efficient communication and functioning while simultaneously limiting disease transmission. Social animals could potentially further reduce epidemic risk by altering their social networks in the presence of pathogens, yet there is currently no evidence for such pathogentriggered responses. We tested this hypothesis experimentally in the ant Lasius niger using a combination of automated tracking, controlled pathogen exposure, transmission quantification, and temporally explicit simulations. Pathogen exposure induced behavioral changes in both exposed ants and their nestmates, which helped contain the disease by reinforcing key transmissioninhibitory properties of the colony's contact network. This suggests that social network plasticity in response to pathogens is an effective strategy for mitigating the effects of disease in social groups.
AU  Stroeymeyt, Nathalie
AU  Grasse, Anna V
AU  Crespi, Alessandro
AU  Mersch, Danielle
AU  Cremer, Sylvia
AU  Keller, Laurent
ID  7
IS  6417
JF  Science
SN  10959203
TI  Social network plasticity decreases disease transmission in a eusocial insect
VL  362
ER 
TY  JOUR
AB  We consider the totally asymmetric simple exclusion process in a critical scaling parametrized by a≥0, which creates a shock in the particle density of order aT−1/3, T the observation time. When starting from step initial data, we provide bounds on the limiting law which in particular imply that in the double limit lima→∞limT→∞ one recovers the product limit law and the degeneration of the correlation length observed at shocks of order 1. This result is shown to apply to a general lastpassage percolation model. We also obtain bounds on the twopoint functions of several airy processes.
AU  Nejjar, Peter
ID  70
IS  2
JF  Latin American Journal of Probability and Mathematical Statistics
SN  19800436
TI  Transition to shocks in TASEP and decoupling of last passage times
VL  15
ER 
TY  JOUR
AB  We consider the NPhard problem of MAPinference for undirected discrete graphical models. We propose a polynomial time and practically efficient algorithm for finding a part of its optimal solution. Specifically, our algorithm marks some labels of the considered graphical model either as (i) optimal, meaning that they belong to all optimal solutions of the inference problem; (ii) nonoptimal if they provably do not belong to any solution. With access to an exact solver of a linear programming relaxation to the MAPinference problem, our algorithm marks the maximal possible (in a specified sense) number of labels. We also present a version of the algorithm, which has access to a suboptimal dual solver only and still can ensure the (non)optimality for the marked labels, although the overall number of the marked labels may decrease. We propose an efficient implementation, which runs in time comparable to a single run of a suboptimal dual solver. Our method is wellscalable and shows stateoftheart results on computational benchmarks from machine learning and computer vision.
AU  Shekhovtsov, Alexander
AU  Swoboda, Paul
AU  Savchynskyy, Bogdan
ID  703
IS  7
JF  IEEE Transactions on Pattern Analysis and Machine Intelligence
SN  01628828
TI  Maximum persistency via iterative relaxed inference with graphical models
VL  40
ER 
TY  CONF
AB  Training deep learning models has received tremendous research interest recently. In particular, there has been intensive research on reducing the communication cost of training when using multiple computational devices, through reducing the precision of the underlying data representation. Naturally, such methods induce system tradeoffs—lowering communication precision could decrease communication overheads and improve scalability; but, on the other hand, it can also reduce the accuracy of training. In this paper, we study this tradeoff space, and ask:Can lowprecision communication consistently improve the endtoend performance of training modern neural networks, with no accuracy loss?From the performance point of view, the answer to this question may appear deceptively easy: compressing communication through low precision should help when the ratio between communication and computation is high. However, this answer is less straightforward when we try to generalize this principle across various neural network architectures (e.g., AlexNet vs. ResNet),number of GPUs (e.g., 2 vs. 8 GPUs), machine configurations(e.g., EC2 instances vs. NVIDIA DGX1), communication primitives (e.g., MPI vs. NCCL), and even different GPU architectures(e.g., Kepler vs. Pascal). Currently, it is not clear how a realistic realization of all these factors maps to the speed up provided by lowprecision communication. In this paper, we conduct an empirical study to answer this question and report the insights.
AU  Grubic, Demjan
AU  Tam, Leo
AU  Alistarh, DanAdrian
AU  Zhang, Ce
ID  7116
SN  23672005
T2  Proceedings of the 21st International Conference on Extending Database Technology
TI  Synchronous multiGPU training for deep learning with lowprecision communications: An empirical study
ER 
TY  CONF
AB  Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (polylogarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question.
On the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and poweroftwochoices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.
AU  Alistarh, DanAdrian
AU  Aspnes, James
AU  Gelashvili, Rati
ID  7123
SN  9781611975031
T2  Proceedings of the 29th Annual ACMSIAM Symposium on Discrete Algorithms
TI  Spaceoptimal majority in population protocols
ER 
TY  JOUR
AB  Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function class we present a runtime comparison between stochastic search algorithms using different search strategies. The (1+1) EA is a simple and wellstudied evolutionary algorithm that has to jump across the valley to a point of higher fitness because it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population genetics, are both able to cross the fitness valley by accepting worsening moves. We show that the runtime of the (1+1) EA depends critically on the length of the valley while the runtimes of the nonelitist algorithms depend crucially on the depth of the valley. Moreover, we show that both SSWM and Metropolis can also efficiently optimise a rugged function consisting of consecutive valleys.
AU  Oliveto, Pietro
AU  Paixao, Tiago
AU  Pérez Heredia, Jorge
AU  Sudholt, Dirk
AU  Trubenova, Barbora
ID  723
IS  5
JF  Algorithmica
TI  How to escape local optima in black box optimisation when non elitism outperforms elitism
VL  80
ER 
TY  JOUR
AB  This paper is devoted to automatic competitive analysis of realtime scheduling algorithms for firmdeadline tasksets, where only completed tasks con tribute some utility to the system. Given such a taskset T , the competitive ratio of an online scheduling algorithm A for T is the worstcase utility ratio of A over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the competitive analysis and competitive synthesis problems. For the competitive analysis case, given any taskset T and any finitememory on line scheduling algorithm A , we show that the competitive ratio of A in T can be computed in polynomial time in the size of the state space of A . Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many wellknown online scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required Preliminary versions of this paper have appeared in Chatterjee et al. ( 2013 , 2014 ). B Andreas Pavlogiannis pavlogiannis@ist.ac.at Krishnendu Chatterjee krish.chat@ist.ac.at Alexander Kößler koe@ecs.tuwien.ac.at Ulrich Schmid s@ecs.tuwien.ac.at 1 IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400 Klosterneuburg, Austria 2 Embedded Computing Systems Group, Vienna University of Technology, Treitlstrasse 3, 1040 Vienna, Austria 123 RealTime Syst for finding worstcase scenarios) by computing power. For the competitive synthesis case, we are just given a taskset T , and the goal is to automatically synthesize an opti mal online scheduling algorithm A , i.e., one that guarantees the largest competitive ratio possible for T . We show how the competitive synthesis problem can be reduced to a twoplayer graph game with partial information, and establish that the compu tational complexity of solving this game is Np complete. The competitive synthesis problem is hence in Np in the size of the state space of the nondeterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a given taskset, which is in fact the most common situation in realtime systems design.
AU  Chatterjee, Krishnendu
AU  Pavlogiannis, Andreas
AU  Kößler, Alexander
AU  Schmid, Ulrich
ID  738
IS  1
JF  RealTime Systems
TI  Automated competitive analysis of real time scheduling with graph games
VL  54
ER 
TY  CONF
AB  Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he "wastes" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (nontrivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper.
AU  Pietrzak, Krzysztof Z
ID  7407
SN  18688969
T2  10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
TI  Proofs of catalytic space
VL  124
ER 
TY  JOUR
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 higherdimensional 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 (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the dcells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any ddimensional piecewiselinear manifold M, with a constant (Formula presented.) 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  742
IS  1
JF  Geometriae Dedicata
TI  On expansion and topological overlap
VL  195
ER 
TY  GEN
AB  We prove that any convex body in the plane can be partitioned into m convex parts of equal areas and perimeters for any integer m≥2; this result was previously known for prime powers m=pk. We also give a higherdimensional generalization.
AU  Akopyan, Arseniy
AU  Avvakumov, Sergey
AU  Karasev, Roman
ID  75
TI  Convex fair partitions into arbitrary number of pieces
ER 
TY  JOUR
AB  Consider a fullyconnected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous Ccounting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C>1. In the selfstabilising firing squad problem, the task is to eventually guarantee that all nonfaulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the nottoodistant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for selfstabilising Byzantine firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions.
AU  Lenzen, Christoph
AU  Rybicki, Joel
ID  76
JF  Distributed Computing
TI  Nearoptimal selfstabilising counting and firing squads
ER 
TY  JOUR
AB  Holes confined in quantum dots have gained considerable interest in the past few years due to their potential as spin qubits. Here we demonstrate twoaxis control of a spin 3/2 qubit in natural Ge. The qubit is formed in a hut wire double quantum dot device. The Pauli spin blockade principle allowed us to demonstrate electric dipole spin resonance by applying a radio frequency electric field to one of the electrodes defining the double quantum dot. Coherent hole spin oscillations with Rabi frequencies reaching 140 MHz are demonstrated and dephasing times of 130 ns are measured. The reported results emphasize the potential of Ge as a platform for fast and electrically tunable hole spin qubit devices.
AU  Watzinger, Hannes
AU  Kukucka, Josip
AU  Vukusic, Lada
AU  Gao, Fei
AU  Wang, Ting
AU  Schäffler, Friedrich
AU  Zhang, Jian
AU  Katsaros, Georgios
ID  77
IS  3902
JF  Nature Communications
TI  A germanium hole spin qubit
VL  9
ER 
TY  JOUR
AB  The goal of this article is to introduce the reader to the theory of intrinsic geometry of convex surfaces. We illustrate the power of the tools by proving a theorem on convex surfaces containing an arbitrarily long closed simple geodesic. Let us remind ourselves that a curve in a surface is called geodesic if every sufficiently short arc of the curve is length minimizing; if, in addition, it has no selfintersections, we call it simple geodesic. A tetrahedron with equal opposite edges is called isosceles. The axiomatic method of Alexandrov geometry allows us to work with the metrics of convex surfaces directly, without approximating it first by a smooth or polyhedral metric. Such approximations destroy the closed geodesics on the surface; therefore it is difficult (if at all possible) to apply approximations in the proof of our theorem. On the other hand, a proof in the smooth or polyhedral case usually admits a translation into Alexandrov’s language; such translation makes the result more general. In fact, our proof resembles a translation of the proof given by Protasov. Note that the main theorem implies in particular that a smooth convex surface does not have arbitrarily long simple closed geodesics. However we do not know a proof of this corollary that is essentially simpler than the one presented below.
AU  Akopyan, Arseniy
AU  Petrunin, Anton
ID  106
IS  3
JF  Mathematical Intelligencer
TI  Long geodesics on convex surfaces
VL  40
ER 
TY  JOUR
AB  In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.
AU  Akopyan, Arseniy
AU  Balitskiy, Alexey
AU  Grigorev, Mikhail
ID  1064
IS  4
JF  Discrete & Computational Geometry
SN  01795376
TI  On the circle covering theorem by A.W. Goodman and R.E. Goodman
VL  59
ER 
TY  JOUR
AB  We introduce the notion of “nonmalleable codes” which relaxes the notion of error correction and error detection. Informally, a code is nonmalleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error correction and error detection, nonmalleability can be achieved for very rich classes of modifications. We construct an efficient code that is nonmalleable with respect to modifications that affect each bit of the codeword arbitrarily (i.e., leave it untouched, flip it, or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a nonmalleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient nonmalleable codes in the randomoracle model for very general classes of tampering functions—e.g., functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of nonmalleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g., signature cards) against “tampering attacks.” In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that nonmalleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret state with a nonmalleable code while it is stored in memory.
AU  Dziembowski, Stefan
AU  Pietrzak, Krzysztof Z
AU  Wichs, Daniel
ID  107
IS  4
JF  Journal of the ACM
TI  Nonmalleable codes
VL  65
ER 
TY  CONF
AB  Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \'collision graph\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and nonmalleable codes.
AU  Obremski, Marciej
AU  Skorski, Maciej
ID  108
TI  Inverted leftover hash lemma
VL  2018
ER 
TY  CHAP
AB  We prove that every congruence distributive variety has directed Jónsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original Jónsson or Gumm terms. This result is equivalent to a pair of claims about absorption for admissible preorders in congruence distributive and congruence modular varieties, respectively. For finite algebras, these absorption theorems have already seen significant applications, but until now, it was not clear if the theorems hold for general algebras as well. Our method also yields a novel proof of a result by P. Lipparini about the existence of a chain of terms (which we call Pixley terms) in varieties that are at the same time congruence distributive and kpermutable for some k.
AU  Kazda, Alexandr
AU  Kozik, Marcin
AU  McKenzie, Ralph
AU  Moore, Matthew
ED  Czelakowski, J
ID  10864
SN  22112758
T2  Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science
TI  Absorption and directed Jónsson terms
VL  16
ER 
TY  JOUR
AB  Acquisition of evolutionary novelties is a fundamental process for adapting to the external environment and invading new niches and results in the diversification of life, which we can see in the world today. How such novel phenotypic traits are acquired in the course of evolution and are built up in developing embryos has been a central question in biology. Wholegenome duplication (WGD) is a process of genome doubling that supplies raw genetic materials and increases genome complexity. Recently, it has been gradually revealed that WGD and subsequent fate changes of duplicated genes can facilitate phenotypic evolution. Here, we review the current understanding of the relationship between WGD and the acquisition of evolutionary novelties. We show some examples of this link and discuss how WGD and subsequent duplicated genes can facilitate phenotypic evolution as well as when such genomic doubling can be advantageous for adaptation.
AU  Yuuta, Moriyama
AU  KoshibaTakeuchi, Kazuko
ID  10880
IS  5
JF  Briefings in Functional Genomics
KW  Genetics
KW  Molecular Biology
KW  Biochemistry
KW  General Medicine
SN  20412649
TI  Significance of wholegenome duplications on the emergence of evolutionary novelties
VL  17
ER 
TY  CONF
AB  We report on a novel strategy to derive meanfield limits of quantum mechanical systems in which a large number of particles weakly couple to a secondquantized radiation field. The technique combines the method of counting and the coherent state approach to study the growth of the correlations among the particles and in the radiation field. As an instructional example, we derive the Schrödinger–Klein–Gordon system of equations from the Nelson model with ultraviolet cutoff and possibly massless scalar field. In particular, we prove the convergence of the reduced density matrices (of the nonrelativistic particles and the field bosons) associated with the exact time evolution to the projectors onto the solutions of the Schrödinger–Klein–Gordon equations in trace norm. Furthermore, we derive explicit bounds on the rate of convergence of the oneparticle reduced density matrix of the nonrelativistic particles in Sobolev norm.
AU  Leopold, Nikolai K
AU  Pickl, Peter
ID  11
TI  Meanfield limits of particles in interaction with quantised radiation fields
VL  270
ER 
TY  JOUR
AB  We give a lower bound on the ground state energy of a system of two fermions of one species interacting with two fermions of another species via point interactions. We show that there is a critical mass ratio m2 ≈ 0.58 such that the system is stable, i.e., the energy is bounded from below, for m∈[m2,m2−1]. So far it was not known whether this 2 + 2 system exhibits a stable region at all or whether the formation of fourbody bound states causes an unbounded spectrum for all mass ratios, similar to the Thomas effect. Our result gives further evidence for the stability of the more general N + M system.
AU  Moser, Thomas
AU  Seiringer, Robert
ID  154
IS  3
JF  Mathematical Physics Analysis and Geometry
SN  13850172
TI  Stability of the 2+2 fermionic system with point interactions
VL  21
ER 
TY  CONF
AB  There is currently significant interest in operating devices in the quantum regime, where their behaviour cannot be explained through classical mechanics. Quantum states, including entangled states, are fragile and easily disturbed by excessive thermal noise. Here we address the question of whether it is possible to create nonreciprocal devices that encourage the flow of thermal noise towards or away from a particular quantum device in a network. Our work makes use of the cascaded systems formalism to answer this question in the affirmative, showing how a threeport device can be used as an effective thermal transistor, and illustrates how this formalism maps onto an experimentallyrealisable optomechanical system. Our results pave the way to more resilient quantum devices and to the use of thermal noise as a resource.
AU  Xuereb, André
AU  Aquilina, Matteo
AU  Barzanjeh, Shabir
ED  Andrews, D L
ED  Ostendorf, A
ED  Bain, A J
ED  Nunzi, J M
ID  155
TI  Routing thermal noise through quantum networks
VL  10672
ER 
TY  CONF
AB  Imprecision in timing can sometimes be beneficial: Metric interval temporal logic (MITL), disabling the expression of punctuality constraints, was shown to translate to timed automata, yielding an elementary decision procedure. We show how this principle extends to other forms of densetime specification using regular expressions. By providing a clean, automatonbased formal framework for nonpunctual languages, we are able to recover and extend several results in timed systems. Metric interval regular expressions (MIRE) are introduced, providing regular expressions with nonsingular duration constraints. We obtain that MIRE are expressively complete relative to a class of oneclock timed automata, which can be determinized using additional clocks. Metric interval dynamic logic (MIDL) is then defined using MIRE as temporal modalities. We show that MIDL generalizes known extensions of MITL, while translating to timed automata at comparable cost.
AU  Ferrere, Thomas
ID  156
TI  The compound interest in relaxing punctuality
VL  10951
ER 
TY  JOUR
AB  Social dilemmas occur when incentives for individuals are misaligned with group interests 17 . According to the 'tragedy of the commons', these misalignments can lead to overexploitation and collapse of public resources. The resulting behaviours can be analysed with the tools of game theory 8 . The theory of direct reciprocity 915 suggests that repeated interactions can alleviate such dilemmas, but previous work has assumed that the public resource remains constant over time. Here we introduce the idea that the public resource is instead changeable and depends on the strategic choices of individuals. An intuitive scenario is that cooperation increases the public resource, whereas defection decreases it. Thus, cooperation allows the possibility of playing a more valuable game with higher payoffs, whereas defection leads to a less valuable game. We analyse this idea using the theory of stochastic games 1619 and evolutionary game theory. We find that the dependence of the public resource on previous interactions can greatly enhance the propensity for cooperation. For these results, the interaction between reciprocity and payoff feedback is crucial: neither repeated interactions in a constant environment nor single interactions in a changing environment yield similar cooperation rates. Our framework shows which feedbacks between exploitation and environment  either naturally occurring or designed  help to overcome social dilemmas.
AU  Hilbe, Christian
AU  Šimsa, Štepán
AU  Chatterjee, Krishnendu
AU  Nowak, Martin
ID  157
IS  7713
JF  Nature
TI  Evolution of cooperation in stochastic games
VL  559
ER 
TY  JOUR
AB  The angiosperm seed is composed of three genetically distinct tissues: the diploid embryo that originates from the fertilized egg cell, the triploid endosperm that is produced from the fertilized central cell, and the maternal sporophytic integuments that develop into the seed coat1. At the onset of embryo development in Arabidopsis thaliana, the zygote divides asymmetrically, producing a small apical embryonic cell and a larger basal cell that connects the embryo to the maternal tissue2. The coordinated and synchronous development of the embryo and the surrounding integuments, and the alignment of their growth axes, suggest communication between maternal tissues and the embryo. In contrast to animals, however, where a network of maternal factors that direct embryo patterning have been identified3,4, only a few maternal mutations have been described to affect embryo development in plants5–7. Early embryo patterning in Arabidopsis requires accumulation of the phytohormone auxin in the apical cell by directed transport from the suspensor8–10. However, the origin of this auxin has remained obscure. Here we investigate the source of auxin for early embryogenesis and provide evidence that the mother plant coordinates seed development by supplying auxin to the early embryo from the integuments of the ovule. We show that auxin response increases in ovules after fertilization, due to upregulated auxin biosynthesis in the integuments, and this maternally produced auxin is required for correct embryo development.
AU  Robert, Hélène
AU  Park, Chulmin
AU  Gutièrrez, Carla
AU  Wójcikowska, Barbara
AU  Pěnčík, Aleš
AU  Novák, Ondřej
AU  Chen, Junyi
AU  Grunewald, Wim
AU  Dresselhaus, Thomas
AU  Friml, Jirí
AU  Laux, Thomas
ID  158
IS  8
JF  Nature Plants
TI  Maternal auxin supply contributes to early embryo patterning in Arabidopsis
VL  4
ER 
TY  JOUR
AB  Ltype Ca2+ channels (LTCCs) play a crucial role in excitationcontraction coupling and release of hormones from secretory cells. They are targets of antihypertensive and antiarrhythmic drugs such as diltiazem. Here, we present a photoswitchable diltiazem, FHU779, which can be used to reversibly block endogenous LTCCs by light. FHU779 is as potent as diltiazem and can be used to place pancreatic βcell function and cardiac activity under optical control.
AU  Fehrentz, Timm
AU  Huber, Florian
AU  Hartrampf, Nina
AU  Bruegmann, Tobias
AU  Frank, James
AU  Fine, Nicholas
AU  Malan, Daniela
AU  Danzl, Johann G
AU  Tikhonov, Denis
AU  Sumser, Maritn
AU  Sasse, Philipp
AU  Hodson, David
AU  Zhorov, Boris
AU  Klocker, Nikolaj
AU  Trauner, Dirk
ID  159
IS  8
JF  Nature Chemical Biology
TI  Optical control of Ltype Ca2+ channels using a diltiazem photoswitch
VL  14
ER 
TY  JOUR
AB  We report quantitative evidence of mixinglayer elastic instability in a viscoelastic fluid flow between two widely spaced obstacles hindering a channel flow at Re 1 and Wi 1. Two mixing layers with nonuniform shear velocity profiles are formed in the region between the obstacles. The mixinglayer instability arises in the vicinity of an inflection point on the shear velocity profile with a steep variation in the elastic stress. The instability results in an intermittent appearance of small vortices in the mixing layers and an amplification of spatiotemporal averaged vorticity in the elastic turbulence regime. The latter is characterized through scaling of friction factor with Wi and both pressure and velocity spectra. Furthermore, the observations reported provide improved understanding of the stability of the mixing layer in a viscoelastic fluid at large elasticity, i.e., Wi 1 and Re 1 and oppose the current view of suppression of vorticity solely by polymer additives.
AU  Varshney, Atul
AU  Steinberg, Victor
ID  16
IS  10
JF  Physical Review Fluids
TI  Mixing layer instability and vorticity amplification in a creeping viscoelastic flow
VL  3
ER 
TY  CONF
AB  We present layered concurrent programs, a compact and expressive notation for specifying refinement proofs of concurrent programs. A layered concurrent program specifies a sequence of connected concurrent programs, from most concrete to most abstract, such that common parts of different programs are written exactly once. These programs are expressed in the ordinary syntax of imperative concurrent programs using gated atomic actions, sequencing, choice, and (recursive) procedure calls. Each concurrent program is automatically extracted from the layered program. We reduce refinement to the safety of a sequence of concurrent checker programs, one each to justify the connection between every two consecutive concurrent programs. These checker programs are also automatically extracted from the layered program. Layered concurrent programs have been implemented in the CIVL verifier which has been successfully used for the verification of several complex concurrent programs.
AU  Kragl, Bernhard
AU  Qadeer, Shaz
ID  160
TI  Layered Concurrent Programs
VL  10981
ER 
TY  JOUR
AB  Which properties of metabolic networks can be derived solely from stoichiometry? Predictive results have been obtained by flux balance analysis (FBA), by postulating that cells set metabolic fluxes to maximize growth rate. Here we consider a generalization of FBA to singlecell level using maximum entropy modeling, which we extend and test experimentally. Specifically, we define for Escherichia coli metabolism a flux distribution that yields the experimental growth rate: the model, containing FBA as a limit, provides a better match to measured fluxes and it makes a wide range of predictions: on flux variability, regulation, and correlations; on the relative importance of stoichiometry vs. optimization; on scaling relations for growth rate distributions. We validate the latter here with singlecell data at different subinhibitory antibiotic concentrations. The model quantifies growth optimization as emerging from the interplay of competitive dynamics in the population and regulation of metabolism at the level of single cells.
AU  De Martino, Daniele
AU  Mc, Andersson Anna
AU  Bergmiller, Tobias
AU  Guet, Calin C
AU  Tkacik, Gasper
ID  161
IS  1
JF  Nature Communications
TI  Statistical mechanics for metabolic networks during steady state growth
VL  9
ER 
TY  JOUR
AB  For ultrafast fixation of biological samples to avoid artifacts, highpressure freezing (HPF) followed by freeze substitution (FS) is preferred over chemical fixation at room temperature. After HPF, samples are maintained at low temperature during dehydration and fixation, while avoiding damaging recrystallization. This is a notoriously slow process. McDonald and Webb demonstrated, in 2011, that sample agitation during FS dramatically reduces the necessary time. Then, in 2015, we (H.G. and S.R.) introduced an agitation module into the cryochamber of an automated FS unit and demonstrated that the preparation of algae could be shortened from days to a couple of hours. We argued that variability in the processing, reproducibility, and safety issues are better addressed using automated FS units. For dissemination, we started lowcost manufacturing of agitation modules for two of the most widely used FS units, the Automatic Freeze Substitution Systems, AFS(1) and AFS2, from Leica Microsystems, using three dimensional (3D)printing of the major components. To test them, several labs independently used the modules on a wide variety of specimens that had previously been processed by manual agitation, or without agitation. We demonstrate that automated processing with sample agitation saves time, increases flexibility with respect to sample requirements and protocols, and produces data of at least as good quality as other approaches.
AU  Reipert, Siegfried
AU  Goldammer, Helmuth
AU  Richardson, Christine
AU  Goldberg, Martin
AU  Hawkins, Timothy
AU  Hollergschwandtner, Elena
AU  Kaufmann, Walter
AU  Antreich, Sebastian
AU  Stierhof, York
ID  163
IS  12
JF  Journal of Histochemistry and Cytochemistry
TI  Agitation modules: Flexible means to accelerate automated freeze substitution
VL  66
ER 
TY  JOUR
AB  Creeping flow of polymeric fluid without inertia exhibits elastic instabilities and elastic turbulence accompanied by drag enhancement due to elastic stress produced by flowstretched polymers. However, in inertiadominated flow at high Re and low fluid elasticity El, a reduction in turbulent frictional drag is caused by an intricate competition between inertial and elastic stresses. Here we explore the effect of inertia on the stability of viscoelastic flow in a broad range of control parameters El and (Re,Wi). We present the stability diagram of observed flow regimes in WiRe coordinates and find that the instabilities' onsets show an unexpectedly nonmonotonic dependence on El. Further, three distinct regions in the diagram are identified based on El. Strikingly, for highelasticity fluids we discover a complete relaminarization of flow at Reynolds number in the range of 1 to 10, different from a wellknown turbulent drag reduction. These counterintuitive effects may be explained by a finite polymer extensibility and a suppression of vorticity at high Wi. Our results call for further theoretical and numerical development to uncover the role of inertial effect on elastic turbulence in a viscoelastic flow.
AU  Varshney, Atul
AU  Steinberg, Victor
ID  17
IS  10
JF  Physical Review Fluids
TI  Drag enhancement and drag reduction in viscoelastic flow
VL  3
ER 
TY  JOUR
AB  An Nsuperconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by nodedisjoint paths. It is known that linearsize and boundeddegree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density 25.3 (where the density is the number of edges divided by N). The previously best known densities were 28 [12] and 27.4136 [17].
AU  Kolmogorov, Vladimir
AU  Rolinek, Michal
ID  18
IS  10
JF  Ars Combinatoria
SN  03817032
TI  Superconcentrators of density 25.3
VL  141
ER 
TY  JOUR
AB  In this paper we define and study the classical Uniform Electron Gas (UEG), a system of infinitely many electrons whose density is constant everywhere in space. The UEG is defined differently from Jellium, which has a positive constant background but no constraint on the density. We prove that the UEG arises in Density Functional Theory in the limit of a slowly varying density, minimizing the indirect Coulomb energy. We also construct the quantum UEG and compare it to the classical UEG at low density.
AU  Lewi, Mathieu
AU  Lieb, Élliott
AU  Seiringer, Robert
ID  180
JF  Journal de l'Ecole Polytechnique  Mathematiques
TI  Statistical mechanics of the uniform electron gas
VL  5
ER 
TY  JOUR
AB  We consider large random matrices X with centered, independent entries but possibly di erent variances. We compute the normalized trace of f(X)g(X∗) for f, g functions analytic on the spectrum of X. We use these results to compute the long time asymptotics for systems of coupled di erential equations with random coe cients. We show that when the coupling is critical, the norm squared of the solution decays like t−1/2.
AU  Erdös, László
AU  Krüger, Torben H
AU  Renfrew, David T
ID  181
IS  3
JF  SIAM Journal on Mathematical Analysis
TI  Power law decay for systems of randomly coupled differential equations
VL  50
ER 
TY  CONF
AB  We describe a new algorithm for the parametric identification problem for signal temporal logic (STL), stated as follows. Given a densetime realvalued signal w and a parameterized temporal logic formula φ, compute the subset of the parameter space that renders the formula satisfied by the signal. Unlike previous solutions, which were based on search in the parameter space or quantifier elimination, our procedure works recursively on φ and computes the evolution over time of the set of valid parameter assignments. This procedure is similar to that of monitoring or computing the robustness of φ relative to w. Our implementation and experiments demonstrate that this approach can work well in practice.
AU  Bakhirkin, Alexey
AU  Ferrere, Thomas
AU  Maler, Oded
ID  182
SN  9781450356428
T2  Proceedings of the 21st International Conference on Hybrid Systems
TI  Efficient parametric identification for STL
ER 
TY  CONF
AB  We prove that for every d ≥ 2, deciding if a pure, ddimensional, simplicial complex is shellable is NPhard, hence NPcomplete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, ddimensional, simplicial complex is kdecomposable is NPhard. For d ≥ 3, both problems remain NPhard when restricted to contractible pure ddimensional complexes.
AU  Goaoc, Xavier
AU  Paták, Pavel
AU  Patakova, Zuzana
AU  Tancer, Martin
AU  Wagner, Uli
ID  184
TI  Shellability is NPcomplete
VL  99
ER 
TY  CONF
AB  We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical HananiTutte theorem to the setting of approximating maps of graphs on 2dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose intercluster edges are partitioned into bundles, and (ii) a region R of a 2dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.
AU  Fulek, Radoslav
AU  Kynčl, Jan
ID  185
SN  9783959770668
TI  HananiTutte for approximating maps of graphs
VL  99
ER 
TY  CONF
AB  Given a locally finite X ⊆ ℝd and a radius r ≥ 0, the kfold cover of X and r consists of all points in ℝd that have k or more points of X within distance r. We consider two filtrations  one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k  and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in ℝd+1 whose horizontal integer slices are the orderk Delaunay mosaics of X, and construct a zigzag module from Delaunay mosaics that is isomorphic to the persistence module of the multicovers.
AU  Edelsbrunner, Herbert
AU  Osang, Georg F
ID  187
TI  The multicover persistence of Euclidean balls
VL  99
ER 
TY  CONF
AB  Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex.
AU  Edelsbrunner, Herbert
AU  Virk, Ziga
AU  Wagner, Hubert
ID  188
TI  Smallest enclosing spheres and Chernoff points in Bregman geometry
VL  99
ER 
TY  JOUR
AB  Bacteria regulate genes to survive antibiotic stress, but regulation can be far from perfect. When regulation is not optimal, mutations that change gene expression can contribute to antibiotic resistance. It is not systematically understood to what extent natural gene regulation is or is not optimal for distinct antibiotics, and how changes in expression of specific genes quantitatively affect antibiotic resistance. Here we discover a simple quantitative relation between fitness, gene expression, and antibiotic potency, which rationalizes our observation that a multitude of genes and even innate antibiotic defense mechanisms have expression that is critically nonoptimal under antibiotic treatment. First, we developed a pooledstrain drugdiffusion assay and screened Escherichia coli overexpression and knockout libraries, finding that resistance to a range of 31 antibiotics could result from changing expression of a large and functionally diverse set of genes, in a primarily but not exclusively drugspecific manner. Second, by synthetically controlling the expression of singledrug and multidrug resistance genes, we observed that their fitnessexpression functions changed dramatically under antibiotic treatment in accordance with a logsensitivity relation. Thus, because many genes are nonoptimally expressed under antibiotic treatment, many regulatory mutations can contribute to resistance by altering expression and by activating latent defenses.
AU  Palmer, Adam
AU  Chait, Remy P
AU  Kishony, Roy
ID  19
IS  11
JF  Molecular Biology and Evolution
TI  Nonoptimal gene expression creates latent potential for antibiotic resistance
VL  35
ER 
TY  JOUR
AB  The German cockroach, Blattella germanica, is a worldwide pest that infests buildings, including homes, restaurants, and hospitals, often living in unsanitary conditions. As a disease vector and producer of allergens, this species has major health and economic impacts on humans. Factors contributing to the success of the German cockroach include its resistance to a broad range of insecticides, immunity to many pathogens, and its ability, as an extreme generalist omnivore, to survive on most food sources. The recently published genome shows that B. germanica has an exceptionally high number of protein coding genes. In this study, we investigate the functions of the 93 significantly expanded gene families with the aim to better understand the success of B. germanica as a major pest despite such inhospitable conditions. We find major expansions in gene families with functions related to the detoxification of insecticides and allelochemicals, defense against pathogens, digestion, sensory perception, and gene regulation. These expansions might have allowed B. germanica to develop multiple resistance mechanisms to insecticides and pathogens, and enabled a broad, flexible diet, thus explaining its success in unsanitary conditions and under recurrent chemical control. The findings and resources presented here provide insights for better understanding molecular mechanisms that will facilitate more effective cockroach control.
AU  Harrison, Mark
AU  Arning, Nicolas
AU  Kremer, Lucas
AU  Ylla, Guillem
AU  Belles, Xavier
AU  Bornberg Bauer, Erich
AU  Huylmans, Ann K
AU  Jongepier, Evelien
AU  Puilachs, Maria
AU  Richards, Stephen
AU  Schal, Coby
ID  190
JF  Journal of Experimental Zoology Part B: Molecular and Developmental Evolution
TI  Expansions of key protein families in the German cockroach highlight the molecular basis of its remarkable success as a global indoor pest
VL  330
ER 
TY  JOUR
AB  The phytohormone auxin is the information carrier in a plethora of developmental and physiological processes in plants(1). It has been firmly established that canonical, nuclear auxin signalling acts through regulation of gene transcription(2). Here, we combined microfluidics, live imaging, genetic engineering and computational modelling to reanalyse the classical case of root growth inhibition(3) by auxin. We show that Arabidopsis roots react to addition and removal of auxin by extremely rapid adaptation of growth rate. This process requires intracellular auxin perception but not transcriptional reprogramming. The formation of the canonical TIR1/AFBAux/IAA coreceptor complex is required for the growth regulation, hinting to a novel, nontranscriptional branch of this signalling pathway. Our results challenge the current understanding of root growth regulation by auxin and suggest another, presumably nontranscriptional, signalling output of the canonical auxin pathway.
AU  Fendrych, Matyas
AU  Akhmanova, Maria
AU  Merrin, Jack
AU  Glanc, Matous
AU  Hagihara, Shinya
AU  Takahashi, Koji
AU  Uchida, Naoyuki
AU  Torii, Keiko U
AU  Friml, Jirí
ID  192
IS  7
JF  Nature Plants
TI  Rapid and reversible root growth inhibition by TIR1 auxin signalling
VL  4
ER 