TY - JOUR AB - Consider a fully-connected 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 C-counting 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 self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty 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 not-too-distant 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 self-stabilising 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 - Near-optimal self-stabilising counting and firing squads ER - TY - JOUR AB - Inclusion–exclusion is an effective method for computing the volume of a union of measurable sets. We extend it to multiple coverings, proving short inclusion–exclusion formulas for the subset of Rn covered by at least k balls in a finite set. We implement two of the formulas in dimension n=3 and report on results obtained with our software. AU - Edelsbrunner, Herbert AU - Iglesias Ham, Mabel ID - 530 JF - Computational Geometry: Theory and Applications TI - Multiple covers with balls I: Inclusion–exclusion VL - 68 ER - TY - JOUR AB - Spontaneous emission spectra of two initially excited closely spaced identical atoms are very sensitive to the strength and the direction of the applied magnetic field. We consider the relevant schemes that ensure the determination of the mutual spatial orientation of the atoms and the distance between them by entirely optical means. A corresponding theoretical description is given accounting for the dipole-dipole interaction between the two atoms in the presence of a magnetic field and for polarizations of the quantum field interacting with magnetic sublevels of the two-atom system. AU - Redchenko, Elena AU - Makarov, Alexander AU - Yudson, Vladimir ID - 307 IS - 4 JF - Physical Review A - Atomic, Molecular, and Optical Physics TI - Nanoscopy of pairs of atoms by fluorescence in a magnetic field VL - 97 ER - TY - JOUR AB - Background: Natural selection shapes cancer genomes. Previous studies used signatures of positive selection to identify genes driving malignant transformation. However, the contribution of negative selection against somatic mutations that affect essential tumor functions or specific domains remains a controversial topic. Results: Here, we analyze 7546 individual exomes from 26 tumor types from TCGA data to explore the portion of the cancer exome under negative selection. Although we find most of the genes neutrally evolving in a pan-cancer framework, we identify essential cancer genes and immune-exposed protein regions under significant negative selection. Moreover, our simulations suggest that the amount of negative selection is underestimated. We therefore choose an empirical approach to identify genes, functions, and protein regions under negative selection. We find that expression and mutation status of negatively selected genes is indicative of patient survival. Processes that are most strongly conserved are those that play fundamental cellular roles such as protein synthesis, glucose metabolism, and molecular transport. Intriguingly, we observe strong signals of selection in the immunopeptidome and proteins controlling peptide exposition, highlighting the importance of immune surveillance evasion. Additionally, tumor type-specific immune activity correlates with the strength of negative selection on human epitopes. Conclusions: In summary, our results show that negative selection is a hallmark of cell essentiality and immune response in cancer. The functional domains identified could be exploited therapeutically, ultimately allowing for the development of novel cancer treatments. AU - Zapata, Luis AU - Pich, Oriol AU - Serrano, Luis AU - Kondrashov, Fyodor AU - Ossowski, Stephan AU - Schaefer, Martin ID - 279 JF - Genome Biology TI - Negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome VL - 19 ER - TY - JOUR AB - Aged proteins can become hazardous to cellular function, by accumulating molecular damage. This implies that cells should preferentially rely on newly produced ones. We tested this hypothesis in cultured hippocampal neurons, focusing on synaptic transmission. We found that newly synthesized vesicle proteins were incorporated in the actively recycling pool of vesicles responsible for all neurotransmitter release during physiological activity. We observed this for the calcium sensor Synaptotagmin 1, for the neurotransmitter transporter VGAT, and for the fusion protein VAMP2 (Synaptobrevin 2). Metabolic labeling of proteins and visualization by secondary ion mass spectrometry enabled us to query the entire protein makeup of the actively recycling vesicles, which we found to be younger than that of non-recycling vesicles. The young vesicle proteins remained in use for up to ~ 24 h, during which they participated in recycling a few hundred times. They were afterward reluctant to release and were degraded after an additional ~ 24–48 h. We suggest that the recycling pool of synaptic vesicles relies on newly synthesized proteins, while the inactive reserve pool contains older proteins. AU - Truckenbrodt, Sven M AU - Viplav, Abhiyan AU - Jähne, Sebsatian AU - Vogts, Angela AU - Denker, Annette AU - Wildhagen, Hanna AU - Fornasiero, Eugenio AU - Rizzoli, Silvio ID - 145 IS - 15 JF - The EMBO Journal SN - 0261-4189 TI - Newly produced synaptic vesicle proteins are preferentially used in synaptic transmission VL - 37 ER - TY - JOUR AB - AtNHX5 and AtNHX6 are endosomal Na+,K+/H+ antiporters that are critical for growth and development in Arabidopsis, but the mechanism behind their action remains unknown. Here, we report that AtNHX5 and AtNHX6, functioning as H+ leak, control auxin homeostasis and auxin-mediated development. We found that nhx5 nhx6 exhibited growth variations of auxin-related defects. We further showed that nhx5 nhx6 was affected in auxin homeostasis. Genetic analysis showed that AtNHX5 and AtNHX6 were required for the function of the ER-localized auxin transporter PIN5. Although AtNHX5 and AtNHX6 were co-localized with PIN5 at ER, they did not interact directly. Instead, the conserved acidic residues in AtNHX5 and AtNHX6, which are essential for exchange activity, were required for PIN5 function. AtNHX5 and AtNHX6 regulated the pH in ER. Overall, AtNHX5 and AtNHX6 may regulate auxin transport across the ER via the pH gradient created by their transport activity. H+-leak pathway provides a fine-tuning mechanism that controls cellular auxin fluxes. AU - Fan, Ligang AU - Zhao, Lei AU - Hu, Wei AU - Li, Weina AU - Novák, Ondřej AU - Strnad, Miroslav AU - Simon, Sibu AU - Friml, Jirí AU - Shen, Jinbo AU - Jiang, Liwen AU - Qiu, Quan ID - 462 JF - Plant, Cell and Environment TI - NHX antiporters regulate the pH of endoplasmic reticulum and auxin-mediated development VL - 41 ER - TY - JOUR AB - This study treats with the influence of a symmetry-breaking transversal magnetic field on the nonlinear dynamics of ferrofluidic Taylor-Couette flow – flow confined between two concentric independently rotating cylinders. We detected alternating ‘flip’ solutions which are flow states featuring typical characteristics of slow-fast-dynamics in dynamical systems. The flip corresponds to a temporal change in the axial wavenumber and we find them to appear either as pure 2-fold axisymmetric (due to the symmetry-breaking nature of the applied transversal magnetic field) or involving non-axisymmetric, helical modes in its interim solution. The latter ones show features of typical ribbon solutions. In any case the flip solutions have a preferential first axial wavenumber which corresponds to the more stable state (slow dynamics) and second axial wavenumber, corresponding to the short appearing more unstable state (fast dynamics). However, in both cases the flip time grows exponential with increasing the magnetic field strength before the flip solutions, living on 2-tori invariant manifolds, cease to exist, with lifetime going to infinity. Further we show that ferrofluidic flow turbulence differ from the classical, ordinary (usually at high Reynolds number) turbulence. The applied magnetic field hinders the free motion of ferrofluid partials and therefore smoothen typical turbulent quantities and features so that speaking of mildly chaotic dynamics seems to be a more appropriate expression for the observed motion. AU - Altmeyer, Sebastian ID - 519 JF - Journal of Magnetism and Magnetic Materials TI - Non-linear dynamics and alternating ‘flip’ solutions in ferrofluidic Taylor-Couette flow VL - 452 ER - TY - CONF AB - We study the almost-sure termination problem for probabilistic programs. First, we show that supermartingales with lower bounds on conditional absolute difference provide a sound approach for the almost-sure termination problem. Moreover, using this approach we can obtain explicit optimal bounds on tail probabilities of non-termination within a given number of steps. Second, we present a new approach based on Central Limit Theorem for the almost-sure termination problem, and show that this approach can establish almost-sure 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 almost-sure termination of probabilistic programs. AU - Huang, Mingzhang AU - Fu, Hongfei AU - Chatterjee, Krishnendu ED - Ryu, Sukyoung ID - 5679 SN - 03029743 TI - New approaches for almost-sure termination of probabilistic programs VL - 11275 ER - TY - JOUR AB - The precise control of neural stem cell (NSC) proliferation and differentiation is crucial for the development and function of the human brain. Here, we review the emerging links between the alteration of embryonic and adult neurogenesis and the etiology of neuropsychiatric disorders (NPDs) such as autism spectrum disorders (ASDs) and schizophrenia (SCZ), as well as the advances in stem cell-based modeling and the novel therapeutic targets derived from these studies. AU - Sacco, Roberto AU - Cacci, Emanuele AU - Novarino, Gaia ID - 546 IS - 2 JF - Current Opinion in Neurobiology TI - Neural stem cells in neuropsychiatric disorders VL - 48 ER - TY - GEN AB - This document contains the full list of genes with their respective significance and dN/dS values. (TXT 4499Â kb) AU - Zapata, Luis AU - Pich, Oriol AU - Serrano, Luis AU - Kondrashov, Fyodor AU - Ossowski, Stephan AU - Schaefer, Martin ID - 9812 TI - Additional file 2: Of negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome ER - TY - GEN AB - This document contains additional supporting evidence presented as supplemental tables. (XLSX 50Â kb) AU - Zapata, Luis AU - Pich, Oriol AU - Serrano, Luis AU - Kondrashov, Fyodor AU - Ossowski, Stephan AU - Schaefer, Martin ID - 9811 TI - Additional file 1: Of negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome ER - TY - JOUR AB - Background: Norepinephrine (NE) signaling has a key role in white adipose tissue (WAT) functions, including lipolysis, free fatty acid liberation and, under certain conditions, conversion of white into brite (brown-in-white) adipocytes. However, acute effects of NE stimulation have not been described at the transcriptional network level. Results: We used RNA-seq to uncover a broad transcriptional response. The inference of protein-protein and protein-DNA interaction networks allowed us to identify a set of immediate-early genes (IEGs) with high betweenness, validating our approach and suggesting a hierarchical control of transcriptional regulation. In addition, we identified a transcriptional regulatory network with IEGs as master regulators, including HSF1 and NFIL3 as novel NE-induced IEG candidates. Moreover, a functional enrichment analysis and gene clustering into functional modules suggest a crosstalk between metabolic, signaling, and immune responses. Conclusions: Altogether, our network biology approach explores for the first time the immediate-early systems level response of human adipocytes to acute sympathetic activation, thereby providing a first network basis of early cell fate programs and crosstalks between metabolic and transcriptional networks required for proper WAT function. AU - Higareda Almaraz, Juan AU - Karbiener, Michael AU - Giroud, Maude AU - Pauler, Florian AU - Gerhalter, Teresa AU - Herzig, Stephan AU - Scheideler, Marcel ID - 20 IS - 1 JF - BMC Genomics SN - 1471-2164 TI - Norepinephrine triggers an immediate-early regulatory network response in primary human white adipocytes VL - 19 ER - TY - JOUR AB - We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable 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, non-malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable 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 non-malleable 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 non-malleable codes in the random-oracle 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 non-malleable 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 non-malleable 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 non-malleable 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 - Non-malleable codes VL - 65 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 wound-closure 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, Carl-Philipp 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 - GEN AB - Table S1. Genes with highest betweenness. Table S2. Local and Master regulators up-regulated. Table S3. Local and Master regulators down-regulated (XLSX 23 kb). AU - Higareda Almaraz, Juan AU - Karbiener, Michael AU - Giroud, Maude AU - Pauler, Florian AU - Gerhalter, Teresa AU - Herzig, Stephan AU - Scheideler, Marcel ID - 9807 TI - Additional file 1: Of Norepinephrine triggers an immediate-early regulatory network response in primary human white adipocytes ER - TY - GEN AB - Table S4. Counts per Gene per Million Reads Mapped. (XLSX 2751 kb). AU - Higareda Almaraz, Juan AU - Karbiener, Michael AU - Giroud, Maude AU - Pauler, Florian AU - Gerhalter, Teresa AU - Herzig, Stephan AU - Scheideler, Marcel ID - 9808 TI - Additional file 3: Of Norepinephrine triggers an immediate-early regulatory network response in primary human white adipocytes ER - TY - CONF AB - We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF. AU - Alwen, Joel F AU - Gazi, Peter AU - Kamath Hosdurg, Chethan AU - Klein, Karen AU - Osang, Georg F AU - Pietrzak, Krzysztof Z AU - Reyzin, Lenoid AU - Rolinek, Michal AU - Rybar, Michal ID - 193 T2 - Proceedings of the 2018 on Asia Conference on Computer and Communication Security TI - On the memory hardness of data independent password hashing functions ER - TY - CONF AB - We introduce a formal quantitative notion of “bit security” for a general type of cryptographic games (capturing both decision and search problems), aimed at capturing the intuition that a cryptographic primitive with k-bit security is as hard to break as an ideal cryptographic function requiring a brute force attack on a k-bit key space. Our new definition matches the notion of bit security commonly used by cryptographers and cryptanalysts when studying search (e.g., key recovery) problems, where the use of the traditional definition is well established. However, it produces a quantitatively different metric in the case of decision (indistinguishability) problems, where the use of (a straightforward generalization of) the traditional definition is more problematic and leads to a number of paradoxical situations or mismatches between theoretical/provable security and practical/common sense intuition. Key to our new definition is to consider adversaries that may explicitly declare failure of the attack. We support and justify the new definition by proving a number of technical results, including tight reductions between several standard cryptographic problems, a new hybrid theorem that preserves bit security, and an application to the security analysis of indistinguishability primitives making use of (approximate) floating point numbers. This is the first result showing that (standard precision) 53-bit floating point numbers can be used to achieve 100-bit security in the context of cryptographic primitives with general indistinguishability-based security definitions. Previous results of this type applied only to search problems, or special types of decision problems. AU - Micciancio, Daniele AU - Walter, Michael ID - 300 TI - On the bit security of cryptographic primitives VL - 10820 ER - TY - JOUR AB - Motivated by biological questions, we study configurations of equal spheres that neither pack nor cover. Placing their centers on a lattice, we define the soft density of the configuration by penalizing multiple overlaps. Considering the 1-parameter family of diagonally distorted 3-dimensional integer lattices, we show that the soft density is maximized at the FCC lattice. AU - Edelsbrunner, Herbert AU - Iglesias Ham, Mabel ID - 312 IS - 1 JF - SIAM J Discrete Math SN - 08954801 TI - On the optimality of the FCC lattice for soft sphere packing VL - 32 ER - TY - JOUR AB - We give a simple proof of T. Stehling's result [4], whereby in any normal tiling of the plane with convex polygons with number of sides not less than six, all tiles except a finite number are hexagons. AU - Akopyan, Arseniy ID - 409 IS - 4 JF - Comptes Rendus Mathematique SN - 1631073X TI - On the number of non-hexagons in a planar tiling VL - 356 ER -