@article{5787, abstract = {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.}, author = {Hannezo, Edouard B and Simons, Benjamin D.}, issn = {00121592}, journal = {Development Growth and Differentiation}, number = {9}, pages = {512--521}, publisher = {Wiley}, title = {{Statistical theory of branching morphogenesis}}, doi = {10.1111/dgd.12570}, volume = {60}, year = {2018}, } @inproceedings{297, abstract = {Graph games played by two players over finite-state graphs are central in many problems in computer science. In particular, graph games with ω -regular winning conditions, specified as parity objectives, which can express properties such as safety, liveness, fairness, are the basic framework for verification and synthesis of reactive systems. The decisions for a player at various states of the graph game are represented as strategies. While the algorithmic problem for solving graph games with parity objectives has been widely studied, the most prominent data-structure for strategy representation in graph games has been binary decision diagrams (BDDs). However, due to the bit-level representation, BDDs do not retain the inherent flavor of the decisions of strategies, and are notoriously hard to minimize to obtain succinct representation. In this work we propose decision trees for strategy representation in graph games. Decision trees retain the flavor of decisions of strategies and allow entropy-based minimization to obtain succinct trees. However, decision trees work in settings (e.g., probabilistic models) where errors are allowed, and overfitting of data is typically avoided. In contrast, for strategies in graph games no error is allowed, and the decision tree must represent the entire strategy. We develop new techniques to extend decision trees to overcome the above obstacles, while retaining the entropy-based techniques to obtain succinct trees. We have implemented our techniques to extend the existing decision tree solvers. We present experimental results for problems in reactive synthesis to show that decision trees provide a much more efficient data-structure for strategy representation as compared to BDDs.}, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Kretinsky, Jan and Toman, Viktor}, location = {Thessaloniki, Greece}, pages = {385 -- 407}, publisher = {Springer}, title = {{Strategy representation by decision trees in reactive synthesis}}, doi = {10.1007/978-3-319-89960-2_21}, volume = {10805}, year = {2018}, } @inproceedings{141, abstract = {Given a model and a specification, the fundamental model-checking problem asks for algorithmic verification of whether the model satisfies the specification. We consider graphs and Markov decision processes (MDPs), which are fundamental models for reactive systems. One of the very basic specifications that arise in verification of reactive systems is the strong fairness (aka Streett) objective. Given different types of requests and corresponding grants, the objective requires that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All ω -regular objectives can be expressed as Streett objectives and hence they are canonical in verification. To handle the state-space explosion, symbolic algorithms are required that operate on a succinct implicit representation of the system rather than explicitly accessing the system. While explicit algorithms for graphs and MDPs with Streett objectives have been widely studied, there has been no improvement of the basic symbolic algorithms. The worst-case numbers of symbolic steps required for the basic symbolic algorithms are as follows: quadratic for graphs and cubic for MDPs. In this work we present the first sub-quadratic symbolic algorithm for graphs with Streett objectives, and our algorithm is sub-quadratic even for MDPs. Based on our algorithmic insights we present an implementation of the new symbolic approach and show that it improves the existing approach on several academic benchmark examples.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H and Loitzenbauer, Veronika and Oraee, Simin and Toman, Viktor}, location = {Oxford, United Kingdom}, pages = {178--197}, publisher = {Springer}, title = {{Symbolic algorithms for graphs and Markov decision processes with fairness objectives}}, doi = {10.1007/978-3-319-96142-2_13}, volume = {10982}, year = {2018}, } @inproceedings{298, abstract = {Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains. Alwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost. In this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps. As has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles for at least Ω(n) steps. Along the way we construct a family of maximally “depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅}, author = {Alwen, Joel F and Blocki, Jeremiah and Pietrzak, Krzysztof Z}, location = {Tel Aviv, Israel}, pages = {99 -- 130}, publisher = {Springer}, title = {{Sustained space complexity}}, doi = {10.1007/978-3-319-78375-8_4}, volume = {10821}, year = {2018}, } @article{36, abstract = {Wheat (Triticum ssp.) is one of the most important human food sources. However, this crop is very sensitive to temperature changes. Specifically, processes during wheat leaf, flower, and seed development and photosynthesis, which all contribute to the yield of this crop, are affected by high temperature. While this has to some extent been investigated on physiological, developmental, and molecular levels, very little is known about early signalling events associated with an increase in temperature. Phosphorylation-mediated signalling mechanisms, which are quick and dynamic, are associated with plant growth and development, also under abiotic stress conditions. Therefore, we probed the impact of a short-term and mild increase in temperature on the wheat leaf and spikelet phosphoproteome. In total, 3822 (containing 5178 phosphosites) and 5581 phosphopeptides (containing 7023 phosphosites) were identified in leaf and spikelet samples, respectively. Following statistical analysis, the resulting data set provides the scientific community with a first large-scale plant phosphoproteome under the control of higher ambient temperature. This community resource on the high temperature-mediated wheat phosphoproteome will be valuable for future studies. Our analyses also revealed a core set of common proteins between leaf and spikelet, suggesting some level of conserved regulatory mechanisms. Furthermore, we observed temperature-regulated interconversion of phosphoforms, which probably impacts protein activity.}, author = {Vu, Lam and Zhu, Tingting and Verstraeten, Inge and Van De Cotte, Brigitte and Gevaert, Kris and De Smet, Ive}, journal = {Journal of Experimental Botany}, number = {19}, pages = {4609 -- 4624}, publisher = {Oxford University Press}, title = {{Temperature-induced changes in the wheat phosphoproteome reveal temperature-regulated interconversion of phosphoforms}}, doi = {10.1093/jxb/ery204}, volume = {69}, year = {2018}, } @article{326, abstract = {Three-dimensional (3D) super-resolution microscopy technique structured illumination microscopy (SIM) imaging of dendritic spines along the dendrite has not been previously performed in fixed tissues, mainly due to deterioration of the stripe pattern of the excitation laser induced by light scattering and optical aberrations. To address this issue and solve these optical problems, we applied a novel clearing reagent, LUCID, to fixed brains. In SIM imaging, the penetration depth and the spatial resolution were improved in LUCID-treated slices, and 160-nm spatial resolution was obtained in a large portion of the imaging volume on a single apical dendrite. Furthermore, in a morphological analysis of spine heads of layer V pyramidal neurons (L5PNs) in the medial prefrontal cortex (mPFC) of chronic dexamethasone (Dex)-treated mice, SIM imaging revealed an altered distribution of spine forms that could not be detected by high-NA confocal imaging. Thus, super-resolution SIM imaging represents a promising high-throughput method for revealing spine morphologies in single dendrites.}, author = {Sawada, Kazuaki and Kawakami, Ryosuke and Shigemoto, Ryuichi and Nemoto, Tomomi}, journal = {European Journal of Neuroscience}, number = {9}, pages = {1033 -- 1042}, publisher = {Wiley}, title = {{Super resolution structural analysis of dendritic spines using three-dimensional structured illumination microscopy in cleared mouse brain slices}}, doi = {10.1111/ejn.13901}, volume = {47}, year = {2018}, } @article{5770, abstract = {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 X-ray 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 HIV-1, uncovers conserved and variable features. In contrast to HIV-1, 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 HIV-1, 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.}, author = {Qu, Kun and Glass, Bärbel and Doležal, Michal and Schur, Florian and Murciano, Brice and Rein, Alan and Rumlová, Michaela and Ruml, Tomáš and Kräusslich, Hans-Georg and Briggs, John A. G.}, issn = {00278424}, journal = {Proceedings of the National Academy of Sciences}, number = {50}, pages = {E11751--E11760}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Structure and architecture of immature and mature murine leukemia virus capsids}}, doi = {10.1073/pnas.1811580115}, volume = {115}, year = {2018}, } @article{608, abstract = {Synthesis is the automated construction of a system from its specification. In real life, hardware and software systems are rarely constructed from scratch. Rather, a system is typically constructed from a library of components. Lustig and Vardi formalized this intuition and studied LTL synthesis from component libraries. In real life, designers seek optimal systems. In this paper we add optimality considerations to the setting. We distinguish between quality considerations (for example, size - the smaller a system is, the better it is), and pricing (for example, the payment to the company who manufactured the component). We study the problem of designing systems with minimal quality-cost and price. A key point is that while the quality cost is individual - the choices of a designer are independent of choices made by other designers that use the same library, pricing gives rise to a resource-allocation game - designers that use the same component share its price, with the share being proportional to the number of uses (a component can be used several times in a design). We study both closed and open settings, and in both we solve the problem of finding an optimal design. In a setting with multiple designers, we also study the game-theoretic problems of the induced resource-allocation game.}, author = {Avni, Guy and Kupferman, Orna}, journal = {Theoretical Computer Science}, pages = {50 -- 72}, publisher = {Elsevier}, title = {{Synthesis from component libraries with costs}}, doi = {10.1016/j.tcs.2017.11.001}, volume = {712}, year = {2018}, } @article{705, abstract = {Although dopamine receptors D1 and D2 play key roles in hippocampal function, their synaptic localization within the hippocampus has not been fully elucidated. In order to understand precise functions of pre- or postsynaptic dopamine receptors (DRs), the development of protocols to differentiate pre- and postsynaptic DRs is essential. So far, most studies on determination and quantification of DRs did not discriminate between subsynaptic localization. Therefore, the aim of the study was to generate a robust workflow for the localization of DRs. This work provides the basis for future work on hippocampal DRs, in light that DRs may have different functions at pre- or postsynaptic sites. Synaptosomes from rat hippocampi isolated by a sucrose gradient protocol were prepared for super-resolution direct stochastic optical reconstruction microscopy (dSTORM) using Bassoon as a presynaptic zone and Homer1 as postsynaptic density marker. Direct labeling of primary validated antibodies against dopamine receptors D1 (D1R) and D2 (D2R) with Alexa Fluor 594 enabled unequivocal assignment of D1R and D2R to both, pre- and postsynaptic sites. D1R immunoreactivity clusters were observed within the presynaptic active zone as well as at perisynaptic sites at the edge of the presynaptic active zone. The results may be useful for the interpretation of previous studies and the design of future work on DRs in the hippocampus. Moreover, the reduction of the complexity of brain tissue by the use of synaptosomal preparations and dSTORM technology may represent a useful tool for synaptic localization of brain proteins.}, author = {Miklosi, Andras and Del Favero, Giorgia and Bulat, Tanja and Höger, Harald and Shigemoto, Ryuichi and Marko, Doris and Lubec, Gert}, journal = {Molecular Neurobiology}, number = {6}, pages = {4857 – 4869}, publisher = {Springer}, title = {{Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes}}, doi = {10.1007/s12035-017-0688-y}, volume = {55}, year = {2018}, } @article{148, abstract = {Land plants evolved from charophytic algae, among which Charophyceae possess the most complex body plans. We present the genome of Chara braunii; comparison of the genome to those of land plants identified evolutionary novelties for plant terrestrialization and land plant heritage genes. C. braunii employs unique xylan synthases for cell wall biosynthesis, a phragmoplast (cell separation) mechanism similar to that of land plants, and many phytohormones. C. braunii plastids are controlled via land-plant-like retrograde signaling, and transcriptional regulation is more elaborate than in other algae. The morphological complexity of this organism may result from expanded gene families, with three cases of particular note: genes effecting tolerance to reactive oxygen species (ROS), LysM receptor-like kinases, and transcription factors (TFs). Transcriptomic analysis of sexual reproductive structures reveals intricate control by TFs, activity of the ROS gene network, and the ancestral use of plant-like storage and stress protection proteins in the zygote.}, author = {Nishiyama, Tomoaki and Sakayama, Hidetoshi and De Vries, Jan and Buschmann, Henrik and Saint Marcoux, Denis and Ullrich, Kristian and Haas, Fabian and Vanderstraeten, Lisa and Becker, Dirk and Lang, Daniel and Vosolsobě, Stanislav and Rombauts, Stephane and Wilhelmsson, Per and Janitza, Philipp and Kern, Ramona and Heyl, Alexander and Rümpler, Florian and Calderón Villalobos, Luz and Clay, John and Skokan, Roman and Toyoda, Atsushi and Suzuki, Yutaka and Kagoshima, Hiroshi and Schijlen, Elio and Tajeshwar, Navindra and Catarino, Bruno and Hetherington, Alexander and Saltykova, Assia and Bonnot, Clemence and Breuninger, Holger and Symeonidi, Aikaterini and Radhakrishnan, Guru and Van Nieuwerburgh, Filip and Deforce, Dieter and Chang, Caren and Karol, Kenneth and Hedrich, Rainer and Ulvskov, Peter and Glöckner, Gernot and Delwiche, Charles and Petrášek, Jan and Van De Peer, Yves and Friml, Jirí and Beilby, Mary and Dolan, Liam and Kohara, Yuji and Sugano, Sumio and Fujiyama, Asao and Delaux, Pierre Marc and Quint, Marcel and Theissen, Gunter and Hagemann, Martin and Harholt, Jesper and Dunand, Christophe and Zachgo, Sabine and Langdale, Jane and Maumus, Florian and Van Der Straeten, Dominique and Gould, Sven B and Rensing, Stefan}, journal = {Cell}, number = {2}, pages = {448 -- 464.e24}, publisher = {Cell Press}, title = {{The Chara genome: Secondary complexity and implications for plant terrestrialization}}, doi = {10.1016/j.cell.2018.06.033}, volume = {174}, year = {2018}, } @article{403, abstract = {The ability to adapt growth and development to temperature variations is crucial to generate plant varieties resilient to predicted temperature changes. However, the mechanisms underlying plant response to progressive increases in temperature have just started to be elucidated. Here, we report that the Cyclin-dependent Kinase G1 (CDKG1) is a central element in a thermo-sensitive mRNA splicing cascade that transduces changes in ambient temperature into differential expression of the fundamental spliceosome component, ATU2AF65A. CDKG1 is alternatively spliced in a temperature-dependent manner. We found that this process is partly dependent on both the Cyclin-dependent Kinase G2 (CDKG2) and the interacting co-factor CYCLIN L1 resulting in two distinct messenger RNAs. Relative abundance of both CDKG1 transcripts correlates with ambient temperature and possibly with different expression levels of the associated protein isoforms. Both CDKG1 alternative transcripts are necessary to fully complement the expression of ATU2AF65A across the temperature range. Our data support a previously unidentified temperature-dependent mechanism based on the alternative splicing of CDKG1 and regulated by CDKG2 and CYCLIN L1. We propose that changes in ambient temperature affect the relative abundance of CDKG1 transcripts and this in turn translates into differential CDKG1 protein expression coordinating the alternative splicing of ATU2AF65A. This article is protected by copyright. All rights reserved.}, author = {Cavallari, Nicola and Nibau, Candida and Fuchs, Armin and Dadarou, Despoina and Barta, Andrea and Doonan, John}, journal = {The Plant Journal}, number = {6}, pages = {1010 -- 1022}, publisher = {Wiley}, title = {{The cyclin‐dependent kinase G group defines a thermo‐sensitive alternative splicing circuit modulating the expression of Arabidopsis ATU 2AF 65A}}, doi = {10.1111/tpj.13914}, volume = {94}, year = {2018}, } @inproceedings{156, abstract = {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 dense-time specification using regular expressions. By providing a clean, automaton-based formal framework for non-punctual languages, we are able to recover and extend several results in timed systems. Metric interval regular expressions (MIRE) are introduced, providing regular expressions with non-singular duration constraints. We obtain that MIRE are expressively complete relative to a class of one-clock 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.}, author = {Ferrere, Thomas}, location = {Oxford, UK}, pages = {147 -- 164}, publisher = {Springer}, title = {{The compound interest in relaxing punctuality}}, doi = {10.1007/978-3-319-95582-7_9}, volume = {10951}, year = {2018}, } @article{40, abstract = {Hanemaaijer et al. (Molecular Ecology, 27, 2018) describe the genetic consequences of the introgression of an insecticide resistance allele into a mosquito population. Linked alleles initially increased, but many of these later declined. It is hard to determine whether this decline was due to counter‐selection, rather than simply to chance.}, author = {Barton, Nicholas H}, issn = {1365294X}, journal = {Molecular Ecology}, number = {24}, pages = {4973--4975}, publisher = {Wiley}, title = {{The consequences of an introgression event}}, doi = {10.1111/mec.14950}, volume = {27}, year = {2018}, } @article{5861, abstract = {In zebrafish larvae, it is the cell type that determines how the cell responds to a chemokine signal.}, author = {Alanko, Jonna H and Sixt, Michael K}, issn = {2050084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{The cell sets the tone}}, doi = {10.7554/eLife.37888}, volume = {7}, year = {2018}, } @article{147, abstract = {The trafficking of subcellular cargos in eukaryotic cells crucially depends on vesicle budding, a process mediated by ARF-GEFs (ADP-ribosylation factor guanine nucleotide exchange factors). In plants, ARF-GEFs play essential roles in endocytosis, vacuolar trafficking, recycling, secretion, and polar trafficking. Moreover, they are important for plant development, mainly through controlling the polar subcellular localization of PIN-FORMED (PIN) transporters of the plant hormone auxin. Here, using a chemical genetics screen in Arabidopsis thaliana, we identified Endosidin 4 (ES4), an inhibitor of eukaryotic ARF-GEFs. ES4 acts similarly to and synergistically with the established ARF-GEF inhibitor Brefeldin A and has broad effects on intracellular trafficking, including endocytosis, exocytosis, and vacuolar targeting. Additionally, Arabidopsis and yeast (Sacharomyces cerevisiae) mutants defective in ARF-GEF show altered sensitivity to ES4. ES4 interferes with the activation-based membrane association of the ARF1 GTPases, but not of their mutant variants that are activated independently of ARF-GEF activity. Biochemical approaches and docking simulations confirmed that ES4 specifically targets the SEC7 domain-containing ARF-GEFs. These observations collectively identify ES4 as a chemical tool enabling the study of ARF-GEF-mediated processes, including ARF-GEF-mediated plant development.}, author = {Kania, Urszula and Nodzyński, Tomasz and Lu, Qing and Hicks, Glenn R and Nerinckx, Wim and Mishev, Kiril and Peurois, Francois and Cherfils, Jacqueline and De, Rycke Riet Maria and Grones, Peter and Robert, Stéphanie and Russinova, Eugenia and Friml, Jirí}, issn = {1040-4651}, journal = {The Plant Cell}, number = {10}, pages = {2553 -- 2572}, publisher = {Oxford University Press}, title = {{The inhibitor Endosidin 4 targets SEC7 domain-type ARF GTPase exchange factors and interferes with sub cellular trafficking in eukaryotes}}, doi = {10.1105/tpc.18.00127}, volume = {30}, year = {2018}, } @article{146, abstract = {The root cap protects the stem cell niche of angiosperm roots from damage. In Arabidopsis, lateral root cap (LRC) cells covering the meristematic zone are regularly lost through programmed cell death, while the outermost layer of the root cap covering the tip is repeatedly sloughed. Efficient coordination with stem cells producing new layers is needed to maintain a constant size of the cap. We present a signalling pair, the peptide IDA-LIKE1 (IDL1) and its receptor HAESA-LIKE2 (HSL2), mediating such communication. Live imaging over several days characterized this process from initial fractures in LRC cell files to full separation of a layer. Enhanced expression of IDL1 in the separating root cap layers resulted in increased frequency of sloughing, balanced with generation of new layers in a HSL2-dependent manner. Transcriptome analyses linked IDL1-HSL2 signalling to the transcription factors BEARSKIN1/2 and genes associated with programmed cell death. Mutations in either IDL1 or HSL2 slowed down cell division, maturation and separation. Thus, IDL1-HSL2 signalling potentiates dynamic regulation of the homeostatic balance between stem cell division and sloughing activity.}, author = {Shi, Chun Lin and Von Wangenheim, Daniel and Herrmann, Ullrich and Wildhagen, Mari and Kulik, Ivan and Kopf, Andreas and Ishida, Takashi and Olsson, Vilde and Anker, Mari Kristine and Albert, Markus and Butenko, Melinka A and Felix, Georg and Sawa, Shinichiro and Claassen, Manfred and Friml, Jirí and Aalen, Reidunn B}, journal = {Nature Plants}, number = {8}, pages = {596 -- 604}, publisher = {Nature Publishing Group}, title = {{The dynamics of root cap sloughing in Arabidopsis is regulated by peptide signalling}}, doi = {10.1038/s41477-018-0212-z}, volume = {4}, year = {2018}, } @article{293, abstract = {People sometimes make their admirable deeds and accomplishments hard to spot, such as by giving anonymously or avoiding bragging. Such ‘buried’ signals are hard to reconcile with standard models of signalling or indirect reciprocity, which motivate costly pro-social behaviour by reputational gains. To explain these phenomena, we design a simple game theory model, which we call the signal-burying game. This game has the feature that senders can bury their signal by deliberately reducing the probability of the signal being observed. If the signal is observed, however, it is identified as having been buried. We show under which conditions buried signals can be maintained, using static equilibrium concepts and calculations of the evolutionary dynamics. We apply our analysis to shed light on a number of otherwise puzzling social phenomena, including modesty, anonymous donations, subtlety in art and fashion, and overeagerness.}, author = {Hoffman, Moshe and Hilbe, Christian and Nowak, Martin}, journal = {Nature Human Behaviour}, pages = {397 -- 404}, publisher = {Nature Publishing Group}, title = {{The signal-burying game can explain why we obscure positive traits and good deeds}}, doi = {10.1038/s41562-018-0354-z}, volume = {2}, year = {2018}, } @article{455, abstract = {The derivation of effective evolution equations is central to the study of non-stationary quantum many-body systems, and widely used in contexts such as superconductivity, nuclear physics, Bose–Einstein condensation and quantum chemistry. We reformulate the Dirac–Frenkel approximation principle in terms of reduced density matrices and apply it to fermionic and bosonic many-body systems. We obtain the Bogoliubov–de Gennes and Hartree–Fock–Bogoliubov equations, respectively. While we do not prove quantitative error estimates, our formulation does show that the approximation is optimal within the class of quasifree states. Furthermore, we prove well-posedness of the Bogoliubov–de Gennes equations in energy space and discuss conserved quantities}, author = {Benedikter, Niels P and Sok, Jérémy and Solovej, Jan}, journal = {Annales Henri Poincare}, number = {4}, pages = {1167 -- 1214}, publisher = {Birkhäuser}, title = {{The Dirac–Frenkel principle for reduced density matrices and the Bogoliubov–de Gennes equations}}, doi = {10.1007/s00023-018-0644-z}, volume = {19}, year = {2018}, } @article{314, abstract = {The interface of physics and biology pro-vides a fruitful environment for generatingnew concepts and exciting ways forwardto understanding living matter. Examplesof successful studies include the estab-lishment and readout of morphogen gra-dients during development, signal pro-cessing in protein and genetic networks,the role of fluctuations in determining thefates of cells and tissues, and collectiveeffects in proteins and in tissues. It is nothard to envision that significant further ad-vances will translate to societal benefitsby initiating the development of new de-vices and strategies for curing disease.However, research at the interface posesvarious challenges, in particular for youngscientists, and current institutions arerarely designed to facilitate such scientificprograms. In this Letter, we propose aninternational initiative that addressesthese challenges through the establish-ment of a worldwide network of platformsfor cross-disciplinary training and incuba-tors for starting new collaborations.}, author = {Bauer, Guntram and Fakhri, Nikta and Kicheva, Anna and Kondev, Jané and Kruse, Karsten and Noji, Hiroyuki and Riveline, Daniel and Saunders, Timothy and Thatta, Mukund and Wieschaus, Eric}, issn = {2405-4712}, journal = {Cell Systems}, number = {4}, pages = {400 -- 402}, publisher = {Cell Press}, title = {{The science of living matter for tomorrow}}, doi = {10.1016/j.cels.2018.04.003}, volume = {6}, year = {2018}, } @article{565, abstract = {We re-examine 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. }, author = {Charlesworth, Brian and Barton, Nicholas H}, journal = {Genetics}, number = {1}, pages = {377 -- 382}, publisher = {Genetics }, title = {{The spread of an inversion with migration and selection}}, doi = {10.1534/genetics.117.300426}, volume = {208}, year = {2018}, } @article{446, abstract = {We prove that in Thomas–Fermi–Dirac–von Weizsäcker theory, a nucleus of charge Z > 0 can bind at most Z + C electrons, where C is a universal constant. This result is obtained through a comparison with Thomas-Fermi theory which, as a by-product, gives bounds on the screened nuclear potential and the radius of the minimizer. A key ingredient of the proof is a novel technique to control the particles in the exterior region, which also applies to the liquid drop model with a nuclear background potential.}, author = {Frank, Rupert and Phan Thanh, Nam and Van Den Bosch, Hanne}, journal = {Communications on Pure and Applied Mathematics}, number = {3}, pages = {577 -- 614}, publisher = {Wiley-Blackwell}, title = {{The ionization conjecture in Thomas–Fermi–Dirac–von Weizsäcker theory}}, doi = {10.1002/cpa.21717}, volume = {71}, year = {2018}, } @article{430, abstract = {In this issue of GENETICS, a new method for detecting natural selection on polygenic traits is developed and applied to sev- eral human examples ( Racimo et al. 2018 ). By de fi nition, many loci contribute to variation in polygenic traits, and a challenge for evolutionary ge neticists has been that these traits can evolve by small, nearly undetectable shifts in allele frequencies across each of many, typically unknown, loci. Recently, a helpful remedy has arisen. Genome-wide associ- ation studies (GWAS) have been illuminating sets of loci that can be interrogated jointly for c hanges in allele frequencies. By aggregating small signal s of change across many such loci, directional natural selection is now in principle detect- able using genetic data, even for highly polygenic traits. This is an exciting arena of progress – with these methods, tests can be made for selection associated with traits, and we can now study selection in what may be its most prevalent mode. The continuing fast pace of GWAS publications suggest there will be many more polygenic tests of selection in the near future, as every new GWAS is an opportunity for an accom- panying test of polygenic selection. However, it is important to be aware of complications th at arise in interpretation, especially given that these studies may easily be misinter- preted both in and outside the evolutionary genetics commu- nity. Here, we provide context for understanding polygenic tests and urge caution regarding how these results are inter- preted and reported upon more broadly.}, author = {Novembre, John and Barton, Nicholas H}, journal = {Genetics}, number = {4}, pages = {1351 -- 1355}, publisher = {Genetics Society of America}, title = {{Tread lightly interpreting polygenic tests of selection}}, doi = {10.1534/genetics.118.300786}, volume = {208}, year = {2018}, } @article{199, abstract = {Sex-biased genes are central to the study of sexual selection, sexual antagonism, and sex chromosome evolution. We describe a comprehensive de novo assembled transcriptome in the common frog Rana temporaria based on five developmental stages and three adult tissues from both sexes, obtained from a population with karyotypically homomorphic but genetically differentiated sex chromosomes. This allows the study of sex-biased gene expression throughout development, and its effect on the rate of gene evolution while accounting for pleiotropic expression, which is known to negatively correlate with the evolutionary rate. Overall, sex-biased genes had little overlap among developmental stages and adult tissues. Late developmental stages and gonad tissues had the highest numbers of stage-or tissue-specific genes. We find that pleiotropic gene expression is a better predictor than sex bias for the evolutionary rate of genes, though it often interacts with sex bias. Although genetically differentiated, the sex chromosomes were not enriched in sex-biased genes, possibly due to a very recent arrest of XY recombination. These results extend our understanding of the developmental dynamics, tissue specificity, and genomic localization of sex-biased genes.}, author = {Ma, Wen and Veltsos, Paris and Toups, Melissa A and Rodrigues, Nicolas and Sermier, Roberto and Jeffries, Daniel and Perrin, Nicolas}, journal = {Genes}, number = {6}, publisher = {MDPI AG}, title = {{Tissue specificity and dynamics of sex biased gene expression in a common frog population with differentiated, yet homomorphic, sex chromosomes}}, doi = {10.3390/genes9060294}, volume = {9}, year = {2018}, } @article{543, abstract = {A central goal in theoretical neuroscience is to predict the response properties of sensory neurons from first principles. To this end, “efficient coding” posits that sensory neurons encode maximal information about their inputs given internal constraints. There exist, however, many variants of efficient coding (e.g., redundancy reduction, different formulations of predictive coding, robust coding, sparse coding, etc.), differing in their regimes of applicability, in the relevance of signals to be encoded, and in the choice of constraints. It is unclear how these types of efficient coding relate or what is expected when different coding objectives are combined. Here we present a unified framework that encompasses previously proposed efficient coding models and extends to unique regimes. We show that optimizing neural responses to encode predictive information can lead them to either correlate or decorrelate their inputs, depending on the stimulus statistics; in contrast, at low noise, efficiently encoding the past always predicts decorrelation. Later, we investigate coding of naturalistic movies and show that qualitatively different types of visual motion tuning and levels of response sparsity are predicted, depending on whether the objective is to recover the past or predict the future. Our approach promises a way to explain the observed diversity of sensory neural responses, as due to multiple functional goals and constraints fulfilled by different cell types and/or circuits.}, author = {Chalk, Matthew J and Marre, Olivier and Tkacik, Gasper}, journal = {PNAS}, number = {1}, pages = {186 -- 191}, publisher = {National Academy of Sciences}, title = {{Toward a unified theory of efficient, predictive, and sparse coding}}, doi = {10.1073/pnas.1711114115}, volume = {115}, year = {2018}, } @article{421, abstract = {Cell shape is determined by a balance of intrinsic properties of the cell as well as its mechanochemical environment. Inhomogeneous shape changes underlie many morphogenetic events and involve spatial gradients in active cellular forces induced by complex chemical signaling. Here, we introduce a mechanochemical model based on the notion that cell shape changes may be induced by external diffusible biomolecules that influence cellular contractility (or equivalently, adhesions) in a concentration-dependent manner—and whose spatial profile in turn is affected by cell shape. We map out theoretically the possible interplay between chemical concentration and cellular structure. Besides providing a direct route to spatial gradients in cell shape profiles in tissues, we show that the dependence on cell shape helps create robust mechanochemical gradients.}, author = {Dasbiswas, Kinjal and Hannezo, Claude-Edouard B and Gov, Nir}, journal = {Biophysical Journal}, number = {4}, pages = {968 -- 977}, publisher = {Biophysical Society}, title = {{Theory of eppithelial cell shape transitions induced by mechanoactive chemical gradients}}, doi = {10.1016/j.bpj.2017.12.022}, volume = {114}, year = {2018}, } @article{63, abstract = {African cichlids display a remarkable assortment of jaw morphologies, pigmentation patterns, and mating behaviors. In addition to this previously documented diversity, recent studies have documented a rich diversity of sex chromosomes within these fishes. Here we review the known sex-determination network within vertebrates, and the extraordinary number of sex chromosomes systems segregating in African cichlids. We also propose a model for understanding the unusual number of sex chromosome systems within this clade.}, author = {Gammerdinger, William J and Kocher, Thomas}, journal = {Genes}, number = {10}, publisher = {MDPI AG}, title = {{Unusual diversity of sex chromosomes in African cichlid fishes}}, doi = {10.3390/genes9100480}, volume = {9}, year = {2018}, } @article{296, abstract = {The thermodynamic description of many-particle systems rests on the assumption of ergodicity, the ability of a system to explore all allowed configurations in the phase space. Recent studies on many-body localization have revealed the existence of systems that strongly violate ergodicity in the presence of quenched disorder. Here, we demonstrate that ergodicity can be weakly broken by a different mechanism, arising from the presence of special eigenstates in the many-body spectrum that are reminiscent of quantum scars in chaotic non-interacting systems. In the single-particle case, quantum scars correspond to wavefunctions that concentrate in the vicinity of unstable periodic classical trajectories. We show that many-body scars appear in the Fibonacci chain, a model with a constrained local Hilbert space that has recently been experimentally realized in a Rydberg-atom quantum simulator. The quantum scarred eigenstates are embedded throughout the otherwise thermalizing many-body spectrum but lead to direct experimental signatures, as we show for periodic recurrences that reproduce those observed in the experiment. Our results suggest that scarred many-body bands give rise to a new universality class of quantum dynamics, opening up opportunities for the creation of novel states with long-lived coherence in systems that are now experimentally realizable.}, author = {Turner, Christopher and Michailidis, Alexios and Abanin, Dmitry and Serbyn, Maksym and Papić, Zlatko}, journal = {Nature Physics}, pages = {745 -- 749}, publisher = {Nature Publishing Group}, title = {{Weak ergodicity breaking from quantum many-body scars}}, doi = {10.1038/s41567-018-0137-5}, volume = {14}, year = {2018}, } @article{607, abstract = {We study the Fokker-Planck equation derived in the large system limit of the Markovian process describing the dynamics of quantitative traits. The Fokker-Planck equation is posed on a bounded domain and its transport and diffusion coefficients vanish on the domain's boundary. We first argue that, despite this degeneracy, the standard no-flux boundary condition is valid. We derive the weak formulation of the problem and prove the existence and uniqueness of its solutions by constructing the corresponding contraction semigroup on a suitable function space. Then, we prove that for the parameter regime with high enough mutation rate the problem exhibits a positive spectral gap, which implies exponential convergence to equilibrium.Next, we provide a simple derivation of the so-called Dynamic Maximum Entropy (DynMaxEnt) method for approximation of observables (moments) of the Fokker-Planck solution, which can be interpreted as a nonlinear Galerkin approximation. The limited applicability of the DynMaxEnt method inspires us to introduce its modified version that is valid for the whole range of admissible parameters. Finally, we present several numerical experiments to demonstrate the performance of both the original and modified DynMaxEnt methods. We observe that in the parameter regimes where both methods are valid, the modified one exhibits slightly better approximation properties compared to the original one.}, author = {Bodova, Katarina and Haskovec, Jan and Markowich, Peter}, journal = {Physica D: Nonlinear Phenomena}, pages = {108--120}, publisher = {Elsevier}, title = {{Well posedness and maximum entropy approximation for the dynamics of quantitative traits}}, doi = {10.1016/j.physd.2017.10.015}, volume = {376-377}, year = {2018}, } @article{294, abstract = {We developed a method to calculate two-photon processes in quantum mechanics that replaces the infinite summation over the intermediate states by a perturbation expansion. This latter consists of a series of commutators that involve position, momentum, and Hamiltonian quantum operators. We analyzed several single- and many-particle cases for which a closed-form solution to the perturbation expansion exists, as well as more complicated cases for which a solution is found by convergence. Throughout the article, Rayleigh and Raman scattering are taken as examples of two-photon processes. The present method provides a clear distinction between the Thomson scattering, regarded as classical scattering, and quantum contributions. Such a distinction lets us derive general results concerning light scattering. Finally, possible extensions to the developed formalism are discussed.}, author = {Fratini, Filippo and Safari, Laleh and Amaro, Pedro and Santos, José}, journal = {Physical Review A - Atomic, Molecular, and Optical Physics}, number = {4}, publisher = {American Physical Society}, title = {{Two-photon processes based on quantum commutators}}, doi = {10.1103/PhysRevA.97.043842}, volume = {97}, year = {2018}, } @article{606, abstract = {We establish the existence of a global solution for a new family of fluid-like equations, which are obtained in certain regimes in as the mean-field evolution of the supercurrent density in a (2D section of a) type-II superconductor with pinning and with imposed electric current. We also consider general vortex-sheet initial data, and investigate the uniqueness and regularity properties of the solution. For some choice of parameters, the equation under investigation coincides with the so-called lake equation from 2D shallow water fluid dynamics, and our analysis then leads to a new existence result for rough initial data.}, author = {Duerinckx, Mitia and Fischer, Julian L}, journal = {Annales de l'Institut Henri Poincare (C) Non Linear Analysis}, number = {5}, pages = {1267--1319}, publisher = {Elsevier}, title = {{Well-posedness for mean-field evolutions arising in superconductivity}}, doi = {10.1016/j.anihpc.2017.11.004}, volume = {35}, year = {2018}, } @inproceedings{5959, abstract = {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 real-valued signals. We introduce signal first-order logic (SFO) as a specification language that combines first-order logic with linear-real arithmetic and unary function symbols interpreted as piecewise-linear 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 bounded-response specifications interpreted over input traces with finite variability. We can use our results to extend signal temporal logic with first-order 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 micro-electronics domain.}, author = {Bakhirkin, Alexey and Ferrere, Thomas and Henzinger, Thomas A and Nickovicl, Deian}, booktitle = {2018 International Conference on Embedded Software}, isbn = {9781538655603}, location = {Turin, Italy}, pages = {1--10}, publisher = {IEEE}, title = {{Keynote: The first-order logic of signals}}, doi = {10.1109/emsoft.2018.8537203}, year = {2018}, } @inproceedings{5962, abstract = {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 shared-memory model are still not well-understood. In this work, we address this gap, and provide new convergence bounds for lock-free 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 trade-off 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.}, author = {Alistarh, Dan-Adrian and De Sa, Christopher and Konstantinov, Nikola H}, booktitle = {Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18}, isbn = {9781450357951}, location = {Egham, United Kingdom}, pages = {169--178}, publisher = {ACM Press}, title = {{The convergence of stochastic gradient descent in asynchronous shared memory}}, doi = {10.1145/3212734.3212763}, year = {2018}, } @article{5860, abstract = {A major problem for evolutionary theory is understanding the so-called open-ended nature of evolutionary change, from its definition to its origins. Open-ended 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 open-endedness, 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 non-statistical 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.}, author = {Corominas-Murtra, Bernat and Seoane, Luís F. and Solé, Ricard}, issn = {17425689}, journal = {Journal of the Royal Society Interface}, number = {149}, publisher = {Royal Society Publishing}, title = {{Zipf's Law, unbounded complexity and open-ended evolution}}, doi = {10.1098/rsif.2018.0395}, volume = {15}, year = {2018}, } @inproceedings{5961, abstract = {The area of machine learning has made considerable progress over the past decade, enabled by the widespread availability of large datasets, as well as by improved algorithms and models. Given the large computational demands of machine learning workloads, parallelism, implemented either through single-node concurrency or through multi-node distribution, has been a third key ingredient to advances in machine learning. The goal of this tutorial is to provide the audience with an overview of standard distribution techniques in machine learning, with an eye towards the intriguing trade-offs between synchronization and communication costs of distributed machine learning algorithms, on the one hand, and their convergence, on the other.The tutorial will focus on parallelization strategies for the fundamental stochastic gradient descent (SGD) algorithm, which is a key tool when training machine learning models, from classical instances such as linear regression, to state-of-the-art neural network architectures. The tutorial will describe the guarantees provided by this algorithm in the sequential case, and then move on to cover both shared-memory and message-passing parallelization strategies, together with the guarantees they provide, and corresponding trade-offs. The presentation will conclude with a broad overview of ongoing research in distributed and concurrent machine learning. The tutorial will assume no prior knowledge beyond familiarity with basic concepts in algebra and analysis. }, author = {Alistarh, Dan-Adrian}, booktitle = {Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18}, isbn = {9781450357951}, location = {Egham, United Kingdom}, pages = {487--488}, publisher = {ACM Press}, title = {{A brief tutorial on distributed and concurrent machine learning}}, doi = {10.1145/3212734.3212798}, year = {2018}, } @article{5960, abstract = {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 bounded-error 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.}, author = {Rohou, Simon and Franek, Peter and Aubry, Clément and Jaulin, Luc}, issn = {1741-3176}, journal = {The International Journal of Robotics Research}, number = {12}, pages = {1500--1516}, publisher = {SAGE Publications}, title = {{Proving the existence of loops in robot trajectories}}, doi = {10.1177/0278364918808367}, volume = {37}, year = {2018}, } @inproceedings{5963, abstract = {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 task-based 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 counter-intuitive 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.}, author = {Alistarh, Dan-Adrian and Brown, Trevor A and Kopinsky, Justin and Nadiradze, Giorgi}, booktitle = {Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18}, isbn = {9781450357951}, location = {Egham, United Kingdom}, pages = {377--386}, publisher = {ACM Press}, title = {{Relaxed schedulers can efficiently parallelize iterative algorithms}}, doi = {10.1145/3212734.3212756}, year = {2018}, } @inproceedings{5965, abstract = {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 power-of-two-choices 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.}, author = {Alistarh, Dan-Adrian and Brown, Trevor A and Kopinsky, Justin and Li, Jerry Z. and Nadiradze, Giorgi}, booktitle = {Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18}, isbn = {9781450357999}, location = {Vienna, Austria}, pages = {133--142}, publisher = {ACM Press}, title = {{Distributionally linearizable data structures}}, doi = {10.1145/3210377.3210411}, year = {2018}, } @inproceedings{5967, abstract = {The Big Match is a multi-stage two-player 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 long-standing 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. }, author = {Hansen, Kristoffer Arnsfelt and Ibsen-Jensen, Rasmus and Neyman, Abraham}, booktitle = {Proceedings of the 2018 ACM Conference on Economics and Computation - EC '18}, isbn = {9781450358293}, location = {Ithaca, NY, United States}, pages = {149--150}, publisher = {ACM Press}, title = {{The Big Match with a clock and a bit of memory}}, doi = {10.1145/3219166.3219198}, year = {2018}, } @inproceedings{5966, abstract = {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 constant-competitive 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 non-trivial performance improvements for classic concurrent data structures.}, author = {Alistarh, Dan-Adrian and Haider, Syed Kamran and Kübler, Raphael and Nadiradze, Giorgi}, booktitle = {Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18}, isbn = {9781450357999}, location = {Vienna, Austria}, pages = {383--392}, publisher = {ACM Press}, title = {{The transactional conflict problem}}, doi = {10.1145/3210377.3210406}, year = {2018}, } @article{5975, abstract = {We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey 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 formu-lation 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.}, author = {Kolmogorov, Vladimir}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {6}, pages = {2029--2056}, publisher = {Society for Industrial & Applied Mathematics (SIAM)}, title = {{Commutativity in the algorithmic Lovász local lemma}}, doi = {10.1137/16m1093306}, volume = {47}, year = {2018}, } @inproceedings{5964, abstract = {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 coarse-grained lock-based 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.}, author = {Aksenov, Vitaly and Alistarh, Dan-Adrian and Kuznetsov, Petr}, booktitle = {Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18}, isbn = {9781450357951}, location = {Egham, United Kingdom}, pages = {411--413}, publisher = {ACM Press}, title = {{Brief Announcement: Performance prediction for coarse-grained locking}}, doi = {10.1145/3212734.3212785}, year = {2018}, } @article{5971, abstract = {We consider a Wigner-type 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 self-consistent 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 Wigner-type 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.}, author = {Erdös, László and Mühlbacher, Peter}, issn = {2010-3271}, journal = {Random matrices: Theory and applications}, publisher = {World Scientific Publishing}, title = {{Bounds on the norm of Wigner-type random matrices}}, doi = {10.1142/s2010326319500096}, year = {2018}, } @article{5984, abstract = {G-protein-coupled 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 light-sensing domain of rhodopsin. Upon stimulation with visible light, we identify activation of canonical cell signaling pathways, including cAMP-, Ca2+-, MAPK/ERK-, and Rho-dependent 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.}, author = {Morri, Maurizio and Sanchez-Romero, Inmaculada and Tichy, Alexandra-Madelaine and Kainrath, Stephanie and Gerrard, Elliot J. and Hirschfeld, Priscila and Schwarz, Jan and Janovjak, Harald L}, issn = {2041-1723}, journal = {Nature Communications}, number = {1}, publisher = {Springer Nature}, title = {{Optical functionalization of human class A orphan G-protein-coupled receptors}}, doi = {10.1038/s41467-018-04342-1}, volume = {9}, year = {2018}, } @article{5976, abstract = {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.}, author = {Malomo, Luigi and Perez Rodriguez, Jesus and Iarussi, Emmanuel and Pietroni, Nico and Miguel, Eder and Cignoni, Paolo and Bickel, Bernd}, issn = {0730-0301}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {Association for Computing Machinery (ACM)}, title = {{FlexMaps: Computational design of flat flexible shells for shaping 3D objects}}, doi = {10.1145/3272127.3275076}, volume = {37}, year = {2018}, } @article{5983, abstract = {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 strong-coupling regimes using a combination of variational, diagrammatic, and mean-field approaches. We reveal how the coupling between linear and angular momenta affects stable quasiparticle states, and demonstrate that internal rotation leads to an enhanced self-localization in the translational degrees of freedom.}, author = {Yakaboylu, Enderalp and Midya, Bikashkali and Deuchert, Andreas and Leopold, Nikolai K and Lemeshko, Mikhail}, issn = {2469-9969}, journal = {Physical Review B}, number = {22}, publisher = {American Physical Society}, title = {{Theory of the rotating polaron: Spectrum and self-localization}}, doi = {10.1103/physrevb.98.224506}, volume = {98}, year = {2018}, } @article{5982, abstract = {In the present work, we detail a fast and simple solution-based 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 dislocation-driven mechanism. This mechanism typically results in pyramidal structures, but we demonstrate here that the growth from multiple dislocations results in flower-like 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 three-fold increase of the TE Figure of merit, reaching unprecedented ZT values up to 0.65.}, author = {Zhang, Yu and Liu, Yu and Lim, Khak Ho and Xing, Congcong and Li, Mengyao and Zhang, Ting and Tang, Pengyi and Arbiol, Jordi and Llorca, Jordi and Ng, Ka Ming and Ibáñez, Maria and Guardia, Pablo and Prato, Mirko and Cadavid, Doris and Cabot, Andreu}, issn = {1433-7851}, journal = {Angewandte Chemie International Edition}, number = {52}, pages = {17063--17068}, publisher = {Wiley}, title = {{Tin diselenide molecular precursor for solution-processable thermoelectric materials}}, doi = {10.1002/anie.201809847}, volume = {57}, year = {2018}, } @inproceedings{5978, abstract = {We consider the MAP-inference 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 Sherali-Adams 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 non-relaxed NP-hard problem.The relaxations we consider decompose the original probleminto two non-overlapping parts: an easy LP-tight part and adifficult one. For the latter part a combinatorial solver must beused. As we show in our experiments, in a number of applica-tions 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.}, author = {Haller, Stefan and Swoboda, Paul and Savchynskyy, Bogdan}, booktitle = {Proceedings of the 32st AAAI Conference on Artificial Intelligence}, location = {New Orleans, LU, United States}, pages = {6581--6588}, publisher = {AAAI Press}, title = {{Exact MAP-inference by confining combinatorial search with LP relaxation}}, year = {2018}, } @article{5990, abstract = {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.}, author = {Ridderbos, Joost and Brauns, Matthias and Shen, Jie and de Vries, Folkert K. and Li, Ang and Bakkers, Erik P. A. M. and Brinkman, Alexander and Zwanenburg, Floris A.}, issn = {0935-9648}, journal = {Advanced Materials}, number = {44}, publisher = {Wiley}, title = {{Josephson effect in a few-hole quantum dot}}, doi = {10.1002/adma.201802257}, volume = {30}, year = {2018}, } @article{5980, abstract = {The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols.}, author = {Chatterjee, Sanjit and Kamath Hosdurg, Chethan and Kumar, Vikas}, journal = {American Institute of Mathematical Sciences}, number = {1}, pages = {17--47}, publisher = {AIMS}, title = {{Private set-intersection with common set-up}}, doi = {10.3934/amc.2018002}, volume = {12}, year = {2018}, } @article{5998, abstract = {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 genome-wide polyploidization, independent of mitotic cycles. DNA replication in these cells was analysed by a fluorescent cell-cycle 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 senescence-associated (SA) β-galactosidase activity, induction of a SA secretory phenotype as well as typical metabolic alterations. Furthermore, we show that the shift from endocycle-dependent 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 CHM-EVTs, accompanied by exacerbated endoreduplication and hyperploidy. We propose induction of cellular senescence as a ploidy-limiting mechanism during normal human placentation and unravel a link between excessive polyploidization and reduced senescence in CHM.}, author = {Velicky, Philipp and Meinhardt, Gudrun and Plessl, Kerstin and Vondra, Sigrid and Weiss, Tamara and Haslinger, Peter and Lendl, Thomas and Aumayr, Karin and Mairhofer, Mario and Zhu, Xiaowei and Schütz, Birgit and Hannibal, Roberta L. and Lindau, Robert and Weil, Beatrix and Ernerudh, Jan and Neesen, Jürgen and Egger, Gerda and Mikula, Mario and Röhrl, Clemens and Urban, Alexander E. and Baker, Julie and Knöfler, Martin and Pollheimer, Jürgen}, issn = {1553-7404}, journal = {PLOS Genetics}, number = {10}, publisher = {Public Library of Science}, title = {{Genome amplification and cellular senescence are hallmarks of human placenta development}}, doi = {10.1371/journal.pgen.1007698}, volume = {14}, year = {2018}, }