TY - CONF AB - While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge. Given an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Nanongkai, Danupon AU - Tsourakakis, Charalampos ID - 11869 SN - 0737-8017 T2 - 47th Annual ACM Symposium on Theory of Computing TI - Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams ER - TY - CONF AB - Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1-1/e). (2) On the positive side we present (i) an O(sqrt n)-approximation algorithm for general concave externality functions, (ii) an O(\log m)-approximation algorithm for linear externality functions, and (iii) an (1-1/e)\frac{1}{6}-approximation algorithm for 2-hop step function externalities. We also improve the result from [6] for 1-hop step function externalities by giving a (1-1/e)/2-approximation algorithm. AU - Bhattacharya, Sayan AU - Dvorák, Wolfgang AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11837 SN - 1868-8969 T2 - 32nd International Symposium on Theoretical Aspects of Computer Science TI - Welfare maximization with friends-of-friends network externalities VL - 30 ER - TY - JOUR AB - We consider auctions of indivisible items to unit-demand bidders with budgets. This setting was suggested as an expressive model for single sponsored search auctions. Prior work presented mechanisms that compute bidder-optimal outcomes and are truthful for a restricted set of inputs, i.e., inputs in so-called general position. This condition is easily violated. We provide the first mechanism that is truthful in expectation for all inputs and achieves for each bidder no worse utility than the bidder-optimal outcome. Additionally we give a complete characterization for which inputs mechanisms that compute bidder-optimal outcomes are truthful. AU - Henzinger, Monika H AU - Loitzenbauer, Veronika ID - 11901 JF - Theoretical Computer Science SN - 0304-3975 TI - Truthful unit-demand auctions with budgets revisited VL - 573 ER - TY - JOUR AB - We show that the simplest building blocks of origami-based materials - rigid, degree-four vertices - are generically multistable. The existence of two distinct branches of folding motion emerging from the flat state suggests at least bistability, but we show how nonlinearities in the folding motions allow generic vertex geometries to have as many as five stable states. In special geometries with collinear folds and symmetry, more branches emerge leading to as many as six stable states. Tuning the fold energy parameters, we show how monostability is also possible. Finally, we show how to program the stability features of a single vertex into a periodic fold tessellation. The resulting metasheets provide a previously unanticipated functionality - tunable and switchable shape and size via multistability. AU - Waitukaitis, Scott R AU - Menaut, Rémi AU - Chen, Bryan AU - Van Hecke, Martin ID - 121 IS - 5 JF - APS Physics, Physical Review Letters TI - Origami multistability: From single vertices to metasheets VL - 114 ER - TY - JOUR AB - In plants, vacuolar H+-ATPase (V-ATPase) activity acidifies both the trans-Golgi network/early endosome (TGN/EE) and the vacuole. This dual V-ATPase function has impeded our understanding of how the pH homeostasis within the plant TGN/EE controls exo- and endocytosis. Here, we show that the weak V-ATPase mutant deetiolated3 (det3) displayed a pH increase in the TGN/EE, but not in the vacuole, strongly impairing secretion and recycling of the brassinosteroid receptor and the cellulose synthase complexes to the plasma membrane, in contrast to mutants lacking tonoplast-localized V-ATPase activity only. The brassinosteroid insensitivity and the cellulose deficiency defects in det3 were tightly correlated with reduced Golgi and TGN/EE motility. Thus, our results provide strong evidence that acidification of the TGN/EE, but not of the vacuole, is indispensable for functional secretion and recycling in plants. AU - Yu, Luo AU - Scholl, Stefan AU - Doering, Anett AU - Yi, Zhang AU - Irani, Niloufer AU - Di Rubbo, Simone AU - Neumetzler, Lutz AU - Krishnamoorthy, Praveen AU - Van Houtte, Isabelle AU - Mylle, Evelien AU - Bischoff, Volker AU - Vernhettes, Samantha AU - Winne, Johan AU - Friml, Jirí AU - Stierhof, York AU - Schumacher, Karin AU - Persson, Staffan AU - Russinova, Eugenia ID - 1383 IS - 7 JF - Nature Plants TI - V-ATPase activity in the TGN/EE is required for exocytosis and recycling in Arabidopsis VL - 1 ER - TY - CONF AB - In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm. AU - Pentina, Anastasia AU - Lampert, Christoph ID - 1425 TI - Lifelong learning with non-i.i.d. tasks VL - 2015 ER - TY - CONF AB - We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel enabling a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in twosample hypothesis testing on synthetic as well as real-world data. AU - Kwitt, Roland AU - Huber, Stefan AU - Niethammer, Marc AU - Lin, Weili AU - Bauer, Ulrich ID - 1424 TI - Statistical topological data analysis-A kernel perspective VL - 28 ER - TY - CONF AB - Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient. AU - Paixao, Tiago AU - Sudholt, Dirk AU - Heredia, Jorge AU - Trubenova, Barbora ID - 1430 T2 - Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation TI - First steps towards a runtime comparison of natural and artificial evolution ER - TY - CONF AB - Cryptographic access control offers selective access to encrypted data via a combination of key management and functionality-rich cryptographic schemes, such as attribute-based encryption. Using this approach, publicly available meta-data may inadvertently leak information on the access policy that is enforced by cryptography, which renders cryptographic access control unusable in settings where this information is highly sensitive. We begin to address this problem by presenting rigorous definitions for policy privacy in cryptographic access control. For concreteness we set our results in the model of Role-Based Access Control (RBAC), where we identify and formalize several different flavors of privacy, however, our framework should serve as inspiration for other models of access control. Based on our insights we propose a new system which significantly improves on the privacy properties of state-of-the-art constructions. Our design is based on a novel type of privacy-preserving attribute-based encryption, which we introduce and show how to instantiate. We present our results in the context of a cryptographic RBAC system by Ferrara et al. (CSF'13), which uses cryptography to control read access to files, while write access is still delegated to trusted monitors. We give an extension of the construction that permits cryptographic control over write access. Our construction assumes that key management uses out-of-band channels between the policy enforcer and the users but eliminates completely the need for monitoring read/write access to the data. AU - Ferrara, Anna AU - Fuchsbauer, Georg AU - Liu, Bin AU - Warinschi, Bogdan ID - 1474 TI - Policy privacy in cryptographic access control ER - TY - GEN AB - In this paper we survey geometric and arithmetic techniques to study the cohomology of semiprojective hyperkähler manifolds including toric hyperkähler varieties, Nakajima quiver varieties and moduli spaces of Higgs bundles on Riemann surfaces. The resulting formulae for their Poincaré polynomials are combinatorial and representation theoretical in nature. In particular we will look at their Betti numbers and will establish some results and state some expectations on their asymptotic shape. AU - Tamas Hausel AU - Rodríguez Villegas, Fernando ID - 1473 IS - 370 T2 - Asterisque TI - Cohomology of large semiprojective hyperkähler varieties VL - 2015 ER - TY - CONF AB - Topological data analysis offers a rich source of valuable information to study vision problems. Yet, so far we lack a theoretically sound connection to popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a connection by designing a multi-scale kernel for persistence diagrams, a stable summary representation of topological features in data. We show that this kernel is positive definite and prove its stability with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets for 3D shape classification/retrieval and texture recognition show considerable performance gains of the proposed method compared to an alternative approach that is based on the recently introduced persistence landscapes. AU - Reininghaus, Jan AU - Huber, Stefan AU - Bauer, Ulrich AU - Kwitt, Roland ID - 1483 TI - A stable multi-scale kernel for topological machine learning ER - TY - CONF AB - Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea. AU - Dragoi, Cezara AU - Henzinger, Thomas A AU - Zufferey, Damien ID - 1498 SN - 978-3-939897-80-4 TI - The need for language support for fault-tolerant distributed systems VL - 32 ER - TY - JOUR AB - Detecting allelic biases from high-throughput sequencing data requires an approach that maximises sensitivity while minimizing false positives. Here, we present Allelome.PRO, an automated user-friendly bioinformatics pipeline, which uses high-throughput sequencing data from reciprocal crosses of two genetically distinct mouse strains to detect allele-specific expression and chromatin modifications. Allelome.PRO extends approaches used in previous studies that exclusively analyzed imprinted expression to give a complete picture of the ‘allelome’ by automatically categorising the allelic expression of all genes in a given cell type into imprinted, strain-biased, biallelic or non-informative. Allelome.PRO offers increased sensitivity to analyze lowly expressed transcripts, together with a robust false discovery rate empirically calculated from variation in the sequencing data. We used RNA-seq data from mouse embryonic fibroblasts from F1 reciprocal crosses to determine a biologically relevant allelic ratio cutoff, and define for the first time an entire allelome. Furthermore, we show that Allelome.PRO detects differential enrichment of H3K4me3 over promoters from ChIP-seq data validating the RNA-seq results. This approach can be easily extended to analyze histone marks of active enhancers, or transcription factor binding sites and therefore provides a powerful tool to identify candidate cis regulatory elements genome wide. AU - Andergassen, Daniel AU - Dotter, Christoph AU - Kulinski, Tomasz AU - Guenzl, Philipp AU - Bammer, Philipp AU - Barlow, Denise AU - Pauler, Florian AU - Hudson, Quanah ID - 1497 IS - 21 JF - Nucleic Acids Research TI - Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data VL - 43 ER - TY - CONF AB - We consider weighted automata with both positive and negative integer weights on edges and study the problem of synchronization using adaptive strategies that may only observe whether the current weight-level is negative or nonnegative. We show that the synchronization problem is decidable in polynomial time for deterministic weighted automata. AU - Kretinsky, Jan AU - Larsen, Kim AU - Laursen, Simon AU - Srba, Jiří ID - 1499 TI - Polynomial time decidability of weighted synchronization under partial observability VL - 42 ER - TY - CONF AB - Motivated by biological questions, we study configurations of equal-sized disks in the Euclidean plane that neither pack nor cover. Measuring the quality by the probability that a random point lies in exactly one disk, we show that the regular hexagonal grid gives the maximum among lattice configurations. AU - Edelsbrunner, Herbert AU - Iglesias Ham, Mabel AU - Kurlin, Vitaliy ID - 1495 T2 - Proceedings of the 27th Canadian Conference on Computational Geometry TI - Relaxed disk packing VL - 2015-August ER - TY - JOUR AB - Let Q = (Q1, . . . , Qn) be a random vector drawn from the uniform distribution on the set of all n! permutations of {1, 2, . . . , n}. Let Z = (Z1, . . . , Zn), where Zj is the mean zero variance one random variable obtained by centralizing and normalizing Qj , j = 1, . . . , n. Assume that Xi , i = 1, . . . ,p are i.i.d. copies of 1/√ p Z and X = Xp,n is the p × n random matrix with Xi as its ith row. Then Sn = XX is called the p × n Spearman's rank correlation matrix which can be regarded as a high dimensional extension of the classical nonparametric statistic Spearman's rank correlation coefficient between two independent random variables. In this paper, we establish a CLT for the linear spectral statistics of this nonparametric random matrix model in the scenario of high dimension, namely, p = p(n) and p/n→c ∈ (0,∞) as n→∞.We propose a novel evaluation scheme to estimate the core quantity in Anderson and Zeitouni's cumulant method in [Ann. Statist. 36 (2008) 2553-2576] to bypass the so-called joint cumulant summability. In addition, we raise a two-step comparison approach to obtain the explicit formulae for the mean and covariance functions in the CLT. Relying on this CLT, we then construct a distribution-free statistic to test complete independence for components of random vectors. Owing to the nonparametric property, we can use this test on generally distributed random variables including the heavy-tailed ones. AU - Bao, Zhigang AU - Lin, Liang AU - Pan, Guangming AU - Zhou, Wang ID - 1504 IS - 6 JF - Annals of Statistics TI - Spectral statistics of large dimensional spearman s rank correlation matrix and its application VL - 43 ER - TY - JOUR AB - A Herman-Avila-Bochi type formula is obtained for the average sum of the top d Lyapunov exponents over a one-parameter family of double-struck G-cocycles, where double-struck G is the group that leaves a certain, non-degenerate Hermitian form of signature (c, d) invariant. The generic example of such a group is the pseudo-unitary group U(c, d) or, in the case c = d, the Hermitian-symplectic group HSp(2d) which naturally appears for cocycles related to Schrödinger operators. In the case d = 1, the formula for HSp(2d) cocycles reduces to the Herman-Avila-Bochi formula for SL(2, ℝ) cocycles. AU - Sadel, Christian ID - 1503 IS - 5 JF - Ergodic Theory and Dynamical Systems TI - A Herman-Avila-Bochi formula for higher-dimensional pseudo-unitary and Hermitian-symplectic-cocycles VL - 35 ER - TY - CONF AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. AU - Franek, Peter AU - Krcál, Marek ID - 1510 TI - On computability and triviality of well groups VL - 34 ER - TY - JOUR AB - This paper is aimed at deriving the universality of the largest eigenvalue of a class of high-dimensional real or complex sample covariance matrices of the form W N =Σ 1/2XX∗Σ 1/2 . Here, X = (xij )M,N is an M× N random matrix with independent entries xij , 1 ≤ i M,≤ 1 ≤ j ≤ N such that Exij = 0, E|xij |2 = 1/N . On dimensionality, we assume that M = M(N) and N/M → d ε (0, ∞) as N ∞→. For a class of general deterministic positive-definite M × M matrices Σ , under some additional assumptions on the distribution of xij 's, we show that the limiting behavior of the largest eigenvalue of W N is universal, via pursuing a Green function comparison strategy raised in [Probab. Theory Related Fields 154 (2012) 341-407, Adv. Math. 229 (2012) 1435-1515] by Erd″os, Yau and Yin for Wigner matrices and extended by Pillai and Yin [Ann. Appl. Probab. 24 (2014) 935-1001] to sample covariance matrices in the null case (&Epsi = I ). Consequently, in the standard complex case (Ex2 ij = 0), combing this universality property and the results known for Gaussian matrices obtained by El Karoui in [Ann. Probab. 35 (2007) 663-714] (nonsingular case) and Onatski in [Ann. Appl. Probab. 18 (2008) 470-490] (singular case), we show that after an appropriate normalization the largest eigenvalue of W N converges weakly to the type 2 Tracy-Widom distribution TW2 . Moreover, in the real case, we show that whenΣ is spiked with a fixed number of subcritical spikes, the type 1 Tracy-Widom limit TW1 holds for the normalized largest eigenvalue of W N , which extends a result of Féral and Péché in [J. Math. Phys. 50 (2009) 073302] to the scenario of nondiagonal Σ and more generally distributed X . In summary, we establish the Tracy-Widom type universality for the largest eigenvalue of generally distributed sample covariance matrices under quite light assumptions on &Sigma . Applications of these limiting results to statistical signal detection and structure recognition of separable covariance matrices are also discussed. AU - Bao, Zhigang AU - Pan, Guangming AU - Zhou, Wang ID - 1505 IS - 1 JF - Annals of Statistics TI - Universality for the largest eigenvalue of sample covariance matrices with general population VL - 43 ER - TY - JOUR AB - We consider generalized Wigner ensembles and general β-ensembles with analytic potentials for any β ≥ 1. The recent universality results in particular assert that the local averages of consecutive eigenvalue gaps in the bulk of the spectrum are universal in the sense that they coincide with those of the corresponding Gaussian β-ensembles. In this article, we show that local averaging is not necessary for this result, i.e. we prove that the single gap distributions in the bulk are universal. In fact, with an additional step, our result can be extended to any C4(ℝ) potential. AU - Erdös, László AU - Yau, Horng ID - 1508 IS - 8 JF - Journal of the European Mathematical Society TI - Gap universality of generalized Wigner and β ensembles VL - 17 ER - TY - JOUR AB - Consider the square random matrix An = (aij)n,n, where {aij:= a(n)ij , i, j = 1, . . . , n} is a collection of independent real random variables with means zero and variances one. Under the additional moment condition supn max1≤i,j ≤n Ea4ij <∞, we prove Girko's logarithmic law of det An in the sense that as n→∞ log | detAn| ? (1/2) log(n-1)! d/→√(1/2) log n N(0, 1). AU - Bao, Zhigang AU - Pan, Guangming AU - Zhou, Wang ID - 1506 IS - 3 JF - Bernoulli TI - The logarithmic law of random determinant VL - 21 ER - TY - JOUR AB - Insects of the order Hemiptera (true bugs) use a wide range of mechanisms of sex determination, including genetic sex determination, paternal genome elimination, and haplodiploidy. Genetic sex determination, the prevalent mode, is generally controlled by a pair of XY sex chromosomes or by an XX/X0 system, but different configurations that include additional sex chromosomes are also present. Although this diversity of sex determining systems has been extensively studied at the cytogenetic level, only the X chromosome of the model pea aphid Acyrthosiphon pisum has been analyzed at the genomic level, and little is known about X chromosome biology in the rest of the order. In this study, we take advantage of published DNA- and RNA-seq data from three additional Hemiptera species to perform a comparative analysis of the gene content and expression of the X chromosome throughout this clade. We find that, despite showing evidence of dosage compensation, the X chromosomes of these species show female-biased expression, and a deficit of male-biased genes, in direct contrast to the pea aphid X. We further detect an excess of shared gene content between these very distant species, suggesting that despite the diversity of sex determining systems, the same chromosomal element is used as the X throughout a large portion of the order. AU - Pal, Arka AU - Vicoso, Beatriz ID - 1513 IS - 12 JF - Genome Biology and Evolution TI - The X chromosome of hemipteran insects: Conservation, dosage compensation and sex-biased expression VL - 7 ER - TY - JOUR AB - We study the large deviation rate functional for the empirical distribution of independent Brownian particles with drift. In one dimension, it has been shown by Adams, Dirr, Peletier and Zimmer that this functional is asymptotically equivalent (in the sense of Γ-convergence) to the Jordan-Kinderlehrer-Otto functional arising in the Wasserstein gradient flow structure of the Fokker-Planck equation. In higher dimensions, part of this statement (the lower bound) has been recently proved by Duong, Laschos and Renger, but the upper bound remained open, since the proof of Duong et al relies on regularity properties of optimal transport maps that are restricted to one dimension. In this note we present a new proof of the upper bound, thereby generalising the result of Adams et al to arbitrary dimensions. AU - Erbar, Matthias AU - Maas, Jan AU - Renger, Michiel ID - 1517 JF - Electronic Communications in Probability TI - From large deviations to Wasserstein gradient flows in multiple dimensions VL - 20 ER - TY - JOUR AB - Evolutionary biologists have an array of powerful theoretical techniques that can accurately predict changes in the genetic composition of populations. Changes in gene frequencies and genetic associations between loci can be tracked as they respond to a wide variety of evolutionary forces. However, it is often less clear how to decompose these various forces into components that accurately reflect the underlying biology. Here, we present several issues that arise in the definition and interpretation of selection and selection coefficients, focusing on insights gained through the examination of selection coefficients in multilocus notation. Using this notation, we discuss how its flexibility-which allows different biological units to be identified as targets of selection-is reflected in the interpretation of the coefficients that the notation generates. In many situations, it can be difficult to agree on whether loci can be considered to be under "direct" versus "indirect" selection, or to quantify this selection. We present arguments for what the terms direct and indirect selection might best encompass, considering a range of issues, from viability and sexual selection to kin selection. We show how multilocus notation can discriminate between direct and indirect selection, and describe when it can do so. AU - Barton, Nicholas H AU - Servedio, Maria ID - 1519 IS - 5 JF - Evolution TI - The interpretation of selection coefficients VL - 69 ER - TY - JOUR AB - Based on 16 recommendations, efforts should be made to achieve the following goal: By 2025, all scholarly publication activity in Austria should be Open Access. In other words, the final versions of all scholarly publications resulting from the support of public resources must be freely accessible on the Internet without delay (Gold Open Access). The resources required to meet this obligation shall be provided to the authors, or the cost of the publication venues shall be borne directly by the research organisations. AU - Bauer, Bruno AU - Blechl, Guido AU - Bock, Christoph AU - Danowski, Patrick AU - Ferus, Andreas AU - Graschopf, Anton AU - König, Thomas AU - Mayer, Katja AU - Reckling, Falk AU - Rieck, Katharina AU - Seitz, Peter AU - Stöger, Herwig AU - Welzig, Elvira ID - 1525 IS - 3 JF - VÖB Mitteilungen TI - Arbeitsgruppe „Nationale Strategie“ des Open Access Network Austria OANA VL - 68 ER - TY - JOUR AB - Many stochastic models of biochemical reaction networks contain some chemical species for which the number of molecules that are present in the system can only be finite (for instance due to conservation laws), but also other species that can be present in arbitrarily large amounts. The prime example of such networks are models of gene expression, which typically contain a small and finite number of possible states for the promoter but an infinite number of possible states for the amount of mRNA and protein. One of the main approaches to analyze such models is through the use of equations for the time evolution of moments of the chemical species. Recently, a new approach based on conditional moments of the species with infinite state space given all the different possible states of the finite species has been proposed. It was argued that this approach allows one to capture more details about the full underlying probability distribution with a smaller number of equations. Here, I show that the result that less moments provide more information can only stem from an unnecessarily complicated description of the system in the classical formulation. The foundation of this argument will be the derivation of moment equations that describe the complete probability distribution over the finite state space but only low-order moments over the infinite state space. I will show that the number of equations that is needed is always less than what was previously claimed and always less than the number of conditional moment equations up to the same order. To support these arguments, a symbolic algorithm is provided that can be used to derive minimal systems of unconditional moment equations for models with partially finite state space. AU - Ruess, Jakob ID - 1539 IS - 24 JF - Journal of Chemical Physics TI - Minimal moment equations for stochastic models of biochemical reaction networks with partially finite state space VL - 143 ER - TY - JOUR AB - PIN proteins are auxin export carriers that direct intercellular auxin flow and in turn regulate many aspects of plant growth and development including responses to environmental changes. The Arabidopsis R2R3-MYB transcription factor FOUR LIPS (FLP) and its paralogue MYB88 regulate terminal divisions during stomatal development, as well as female reproductive development and stress responses. Here we show that FLP and MYB88 act redundantly but differentially in regulating the transcription of PIN3 and PIN7 in gravity-sensing cells of primary and lateral roots. On the one hand, FLP is involved in responses to gravity stimulation in primary roots, whereas on the other, FLP and MYB88 function complementarily in establishing the gravitropic set-point angles of lateral roots. Our results support a model in which FLP and MYB88 expression specifically determines the temporal-spatial patterns of PIN3 and PIN7 transcription that are closely associated with their preferential functions during root responses to gravity. AU - Wang, Hongzhe AU - Yang, Kezhen AU - Zou, Junjie AU - Zhu, Lingling AU - Xie, Zidian AU - Morita, Miyoterao AU - Tasaka, Masao AU - Friml, Jirí AU - Grotewold, Erich AU - Beeckman, Tom AU - Vanneste, Steffen AU - Sack, Fred AU - Le, Jie ID - 1534 JF - Nature Communications TI - Transcriptional regulation of PIN genes by FOUR LIPS and MYB88 during Arabidopsis root gravitropism VL - 6 ER - TY - JOUR AB - Systems biology rests on the idea that biological complexity can be better unraveled through the interplay of modeling and experimentation. However, the success of this approach depends critically on the informativeness of the chosen experiments, which is usually unknown a priori. Here, we propose a systematic scheme based on iterations of optimal experiment design, flow cytometry experiments, and Bayesian parameter inference to guide the discovery process in the case of stochastic biochemical reaction networks. To illustrate the benefit of our methodology, we apply it to the characterization of an engineered light-inducible gene expression circuit in yeast and compare the performance of the resulting model with models identified from nonoptimal experiments. In particular, we compare the parameter posterior distributions and the precision to which the outcome of future experiments can be predicted. Moreover, we illustrate how the identified stochastic model can be used to determine light induction patterns that make either the average amount of protein or the variability in a population of cells follow a desired profile. Our results show that optimal experiment design allows one to derive models that are accurate enough to precisely predict and regulate the protein expression in heterogeneous cell populations over extended periods of time. AU - Ruess, Jakob AU - Parise, Francesca AU - Milias Argeitis, Andreas AU - Khammash, Mustafa AU - Lygeros, John ID - 1538 IS - 26 JF - PNAS TI - Iterative experiment design guides the characterization of a light-inducible gene expression circuit VL - 112 ER - TY - JOUR AB - Neuronal and neuroendocrine L-type calcium channels (Cav1.2, Cav1.3) open readily at relatively low membrane potentials and allow Ca2+ to enter the cells near resting potentials. In this way, Cav1.2 and Cav1.3 shape the action potential waveform, contribute to gene expression, synaptic plasticity, neuronal differentiation, hormone secretion and pacemaker activity. In the chromaffin cells (CCs) of the adrenal medulla, Cav1.3 is highly expressed and is shown to support most of the pacemaking current that sustains action potential (AP) firings and part of the catecholamine secretion. Cav1.3 forms Ca2+-nanodomains with the fast inactivating BK channels and drives the resting SK currents. These latter set the inter-spike interval duration between consecutive spikes during spontaneous firing and the rate of spike adaptation during sustained depolarizations. Cav1.3 plays also a primary role in the switch from “tonic” to “burst” firing that occurs in mouse CCs when either the availability of voltage-gated Na channels (Nav) is reduced or the β2 subunit featuring the fast inactivating BK channels is deleted. Here, we discuss the functional role of these “neuronlike” firing modes in CCs and how Cav1.3 contributes to them. The open issue is to understand how these novel firing patterns are adapted to regulate the quantity of circulating catecholamines during resting condition or in response to acute and chronic stress. AU - Vandael, David H AU - Marcantoni, Andrea AU - Carbone, Emilio ID - 1535 IS - 2 JF - Current Molecular Pharmacology TI - Cav1.3 channels as key regulators of neuron-like firings and catecholamine release in chromaffin cells VL - 8 ER - TY - JOUR AB - The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields. AU - Paixao, Tiago AU - Badkobeh, Golnaz AU - Barton, Nicholas H AU - Çörüş, Doğan AU - Dang, Duccuong AU - Friedrich, Tobias AU - Lehre, Per AU - Sudholt, Dirk AU - Sutton, Andrew AU - Trubenova, Barbora ID - 1542 JF - Journal of Theoretical Biology TI - Toward a unifying framework for evolutionary processes VL - 383 ER - TY - JOUR AB - Synaptic efficacy and precision are influenced by the coupling of voltage-gated Ca2+ channels (VGCCs) to vesicles. But because the topography of VGCCs and their proximity to vesicles is unknown, a quantitative understanding of the determinants of vesicular release at nanometer scale is lacking. To investigate this, we combined freeze-fracture replica immunogold labeling of Cav2.1 channels, local [Ca2+] imaging, and patch pipette perfusion of EGTA at the calyx of Held. Between postnatal day 7 and 21, VGCCs formed variable sized clusters and vesicular release became less sensitive to EGTA, whereas fixed Ca2+ buffer properties remained constant. Experimentally constrained reaction-diffusion simulations suggest that Ca2+ sensors for vesicular release are located at the perimeter of VGCC clusters (<30nm) and predict that VGCC number per cluster determines vesicular release probability without altering release time course. This "perimeter release model" provides a unifying framework accounting for developmental changes in both synaptic efficacy and time course. AU - Nakamura, Yukihiro AU - Harada, Harumi AU - Kamasawa, Naomi AU - Matsui, Ko AU - Rothman, Jason AU - Shigemoto, Ryuichi AU - Silver, R Angus AU - Digregorio, David AU - Takahashi, Tomoyuki ID - 1546 IS - 1 JF - Neuron TI - Nanoscale distribution of presynaptic Ca2+ channels and its impact on vesicular release during development VL - 85 ER - TY - CHAP AB - Cell division in prokaryotes and eukaryotes is commonly initiated by the well-controlled binding of proteins to the cytoplasmic side of the cell membrane. However, a precise characterization of the spatiotemporal dynamics of membrane-bound proteins is often difficult to achieve in vivo. Here, we present protocols for the use of supported lipid bilayers to rebuild the cytokinetic machineries of cells with greatly different dimensions: the bacterium Escherichia coli and eggs of the vertebrate Xenopus laevis. Combined with total internal reflection fluorescence microscopy, these experimental setups allow for precise quantitative analyses of membrane-bound proteins. The protocols described to obtain glass-supported membranes from bacterial and vertebrate lipids can be used as starting points for other reconstitution experiments. We believe that similar biochemical assays will be instrumental to study the biochemistry and biophysics underlying a variety of complex cellular tasks, such as signaling, vesicle trafficking, and cell motility. AU - Nguyen, Phuong AU - Field, Christine AU - Groen, Aaron AU - Mitchison, Timothy AU - Loose, Martin ID - 1544 T2 - Building a Cell from its Components Parts TI - Using supported bilayers to study the spatiotemporal organization of membrane-bound proteins VL - 128 ER - TY - JOUR AB - Reciprocal coevolution between host and pathogen is widely seen as a major driver of evolution and biological innovation. Yet, to date, the underlying genetic mechanisms and associated trait functions that are unique to rapid coevolutionary change are generally unknown. We here combined experimental evolution of the bacterial biocontrol agent Bacillus thuringiensis and its nematode host Caenorhabditis elegans with large-scale phenotyping, whole genome analysis, and functional genetics to demonstrate the selective benefit of pathogen virulence and the underlying toxin genes during the adaptation process. We show that: (i) high virulence was specifically favoured during pathogen–host coevolution rather than pathogen one-sided adaptation to a nonchanging host or to an environment without host; (ii) the pathogen genotype BT-679 with known nematocidal toxin genes and high virulence specifically swept to fixation in all of the independent replicate populations under coevolution but only some under one-sided adaptation; (iii) high virulence in the BT-679-dominated populations correlated with elevated copy numbers of the plasmid containing the nematocidal toxin genes; (iv) loss of virulence in a toxin-plasmid lacking BT-679 isolate was reconstituted by genetic reintroduction or external addition of the toxins.We conclude that sustained coevolution is distinct from unidirectional selection in shaping the pathogen's genome and life history characteristics. To our knowledge, this study is the first to characterize the pathogen genes involved in coevolutionary adaptation in an animal host–pathogen interaction system. AU - El Masri, Leila AU - Branca, Antoine AU - Sheppard, Anna AU - Papkou, Andrei AU - Laehnemann, David AU - Guenther, Patrick AU - Prahl, Swantje AU - Saebelfeld, Manja AU - Hollensteiner, Jacqueline AU - Liesegang, Heiko AU - Brzuszkiewicz, Elzbieta AU - Daniel, Rolf AU - Michiels, Nico AU - Schulte, Rebecca AU - Kurtz, Joachim AU - Rosenstiel, Philip AU - Telschow, Arndt AU - Bornberg Bauer, Erich AU - Schulenburg, Hinrich ID - 1551 IS - 6 JF - PLoS Biology TI - Host–pathogen coevolution: The selective advantage of Bacillus thuringiensis virulence and its cry toxin genes VL - 13 ER - TY - CHAP AB - Nature has incorporated small photochromic molecules, colloquially termed 'photoswitches', in photoreceptor proteins to sense optical cues in photo-taxis and vision. While Nature's ability to employ light-responsive functionalities has long been recognized, it was not until recently that scientists designed, synthesized and applied synthetic photochromes to manipulate many of which open rapidly and locally in their native cell types, biological processes with the temporal and spatial resolution of light. Ion channels in particular have come to the forefront of proteins that can be put under the designer control of synthetic photochromes. Photochromic ion channel controllers are comprised of three classes, photochromic soluble ligands (PCLs), photochromic tethered ligands (PTLs) and photochromic crosslinkers (PXs), and in each class ion channel functionality is controlled through reversible changes in photochrome structure. By acting as light-dependent ion channel agonists, antagonist or modulators, photochromic controllers effectively converted a wide range of ion channels, including voltage-gated ion channels, 'leak channels', tri-, tetra- and pentameric ligand-gated ion channels, and temperaturesensitive ion channels, into man-made photoreceptors. Control by photochromes can be reversible, unlike in the case of 'caged' compounds, and non-invasive with high spatial precision, unlike pharmacology and electrical manipulation. Here, we introduce design principles of emerging photochromic molecules that act on ion channels and discuss the impact that these molecules are beginning to have on ion channel biophysics and neuronal physiology. AU - Mckenzie, Catherine AU - Sanchez Romero, Inmaculada AU - Janovjak, Harald L ID - 1549 SN - 978-1-4939-2844-6 T2 - Novel chemical tools to study ion channel biology TI - Flipping the photoswitch: Ion channels under light control VL - 869 ER - TY - JOUR AB - Reproduction within a host and transmission to the next host are crucial for the virulence and fitness of pathogens. Nevertheless, basic knowledge about such parameters is often missing from the literature, even for well-studied bacteria, such as Bacillus thuringiensis, an endospore-forming insect pathogen, which infects its hosts via the oral route. To characterize bacterial replication success, we made use of an experimental oral infection system for the red flour beetle Tribolium castaneum and developed a flow cytometric assay for the quantification of both spore ingestion by the individual beetle larvae and the resulting spore load after bacterial replication and resporulation within cadavers. On average, spore numbers increased 460-fold, showing that Bacillus thuringiensis grows and replicates successfully in insect cadavers. By inoculating cadaver-derived spores and spores from bacterial stock cultures into nutrient medium, we next investigated outgrowth characteristics of vegetative cells and found that cadaver- derived bacteria showed reduced growth compared to bacteria from the stock cultures. Interestingly, this reduced growth was a consequence of inhibited spore germination, probably originating from the host and resulting in reduced host mortality in subsequent infections by cadaver-derived spores. Nevertheless, we further showed that Bacillus thuringiensis transmission was possible via larval cannibalism when no other food was offered. These results contribute to our understanding of the ecology of Bacillus thuringiensis as an insect pathogen. AU - Milutinovic, Barbara AU - Höfling, Christina AU - Futo, Momir AU - Scharsack, Jörn AU - Kurtz, Joachim ID - 1548 IS - 23 JF - Applied and Environmental Microbiology TI - Infection of Tribolium castaneum with Bacillus thuringiensis: Quantification of bacterial replication within cadavers, transmission via cannibalism, and inhibition of spore germination VL - 81 ER - TY - JOUR AB - The medial ganglionic eminence (MGE) gives rise to the majority of mouse forebrain interneurons. Here, we examine the lineage relationship among MGE-derived interneurons using a replication-defective retroviral library containing a highly diverse set of DNA barcodes. Recovering the barcodes from the mature progeny of infected progenitor cells enabled us to unambiguously determine their respective lineal relationship. We found that clonal dispersion occurs across large areas of the brain and is not restricted by anatomical divisions. As such, sibling interneurons can populate the cortex, hippocampus striatum, and globus pallidus. The majority of interneurons appeared to be generated from asymmetric divisions of MGE progenitor cells, followed by symmetric divisions within the subventricular zone. Altogether, our findings uncover that lineage relationships do not appear to determine interneuron allocation to particular regions. As such, it is likely that clonally related interneurons have considerable flexibility as to the particular forebrain circuits to which they can contribute. AU - Mayer, Christian AU - Jaglin, Xavier AU - Cobbs, Lucy AU - Bandler, Rachel AU - Streicher, Carmen AU - Cepko, Constance AU - Hippenmeyer, Simon AU - Fishell, Gord ID - 1550 IS - 5 JF - Neuron TI - Clonally related forebrain interneurons disperse broadly across both functional areas and structural boundaries VL - 87 ER - TY - JOUR AB - Let G be a graph on the vertex set V(G) = {x1,…,xn} with the edge set E(G), and let R = K[x1,…, xn] be the polynomial ring over a field K. Two monomial ideals are associated to G, the edge ideal I(G) generated by all monomials xixj with {xi,xj} ∈ E(G), and the vertex cover ideal IG generated by monomials ∏xi∈Cxi for all minimal vertex covers C of G. A minimal vertex cover of G is a subset C ⊂ V(G) such that each edge has at least one vertex in C and no proper subset of C has the same property. Indeed, the vertex cover ideal of G is the Alexander dual of the edge ideal of G. In this paper, for an unmixed bipartite graph G we consider the lattice of vertex covers LG and we explicitly describe the minimal free resolution of the ideal associated to LG which is exactly the vertex cover ideal of G. Then we compute depth, projective dimension, regularity and extremal Betti numbers of R/I(G) in terms of the associated lattice. AU - Mohammadi, Fatemeh AU - Moradi, Somayeh ID - 1547 IS - 3 JF - Bulletin of the Korean Mathematical Society TI - Resolution of unmixed bipartite graphs VL - 52 ER - TY - JOUR AB - The elongator complex subunit 2 (ELP2) protein, one subunit of an evolutionarily conserved histone acetyltransferase complex, has been shown to participate in leaf patterning, plant immune and abiotic stress responses in Arabidopsis thaliana. Here, its role in root development was explored. Compared to the wild type, the elp2 mutant exhibited an accelerated differentiation of its root stem cells and cell division was more active in its quiescent centre (QC). The key transcription factors responsible for maintaining root stem cell and QC identity, such as AP2 transcription factors PLT1 (PLETHORA1) and PLT2 (PLETHORA2), GRAS transcription factors such as SCR (SCARECROW) and SHR (SHORT ROOT) and WUSCHEL-RELATED HOMEOBOX5 transcription factor WOX5, were all strongly down-regulated in the mutant. On the other hand, expression of the G2/M transition activator CYCB1 was substantially induced in elp2. The auxin efflux transporters PIN1 and PIN2 showed decreased protein levels and PIN1 also displayed mild polarity alterations in elp2, which resulted in a reduced auxin content in the root tip. Either the acetylation or methylation level of each of these genes differed between the mutant and the wild type, suggesting that the ELP2 regulation of root development involves the epigenetic modification of a range of transcription factors and other developmental regulators. AU - Jia, Yuebin AU - Tian, Huiyu AU - Li, Hongjiang AU - Yu, Qianqian AU - Wang, Lei AU - Friml, Jirí AU - Ding, Zhaojun ID - 1556 IS - 15 JF - Journal of Experimental Botany TI - The Arabidopsis thaliana elongator complex subunit 2 epigenetically affects root development VL - 66 ER - TY - JOUR AB - We show that incorporating spatial dispersal of individuals into a simple vaccination epidemic model may give rise to a model that exhibits rich dynamical behavior. Using an SIVS (susceptible-infected-vaccinated-susceptible) model as a basis, we describe the spread of an infectious disease in a population split into two regions. In each subpopulation, both forward and backward bifurcations can occur. This implies that for disconnected regions the two-patch system may admit several steady states. We consider traveling between the regions and investigate the impact of spatial dispersal of individuals on the model dynamics. We establish conditions for the existence of multiple nontrivial steady states in the system, and we study the structure of the equilibria. The mathematical analysis reveals an unusually rich dynamical behavior, not normally found in the simple epidemic models. In addition to the disease-free equilibrium, eight endemic equilibria emerge from backward transcritical and saddle-node bifurcation points, forming an interesting bifurcation diagram. Stability of steady states, their bifurcations, and the global dynamics are investigated with analytical tools, numerical simulations, and rigorous set-oriented numerical computations. AU - Knipl, Diána AU - Pilarczyk, Pawel AU - Röst, Gergely ID - 1555 IS - 2 JF - SIAM Journal on Applied Dynamical Systems TI - Rich bifurcation structure in a two patch vaccination model VL - 14 ER - TY - JOUR AB - There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant)will take over a resident population?We derive precise complexity results for a variety of scenarios. We therefore show that some fundamental questions in this area cannot be answered by simple equations (assuming that P is not equal to NP). AU - Ibsen-Jensen, Rasmus AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 1559 IS - 51 JF - PNAS TI - Computational complexity of ecological and evolutionary spatial dynamics VL - 112 ER - TY - JOUR AB - The visualization of hormonal signaling input and output is key to understanding how multicellular development is regulated. The plant signaling molecule auxin triggers many growth and developmental responses, but current tools lack the sensitivity or precision to visualize these. We developed a set of fluorescent reporters that allow sensitive and semiquantitative readout of auxin responses at cellular resolution in Arabidopsis thaliana. These generic tools are suitable for any transformable plant species. AU - Liao, Cheyang AU - Smet, Wouter AU - Brunoud, Géraldine AU - Yoshida, Saiko AU - Vernoux, Teva AU - Weijers, Dolf ID - 1554 IS - 3 JF - Nature Methods TI - Reporters for sensitive and quantitative measurement of auxin response VL - 12 ER - TY - JOUR AB - Leptin is an adipokine produced by the adipose tissue regulating body weight through its appetite-suppressing effect. Besides being expressed in the hypothalamus and hippocampus, leptin receptors (ObRs) are also present in chromaffin cells of the adrenal medulla. In the present study, we report the effect of leptin on mouse chromaffin cell (MCC) functionality, focusing on cell excitability and catecholamine secretion. Acute application of leptin (1 nm) on spontaneously firing MCCs caused a slowly developing membrane hyperpolarization followed by complete blockade of action potential (AP) firing. This inhibitory effect at rest was abolished by the BK channel blocker paxilline (1 μm), suggesting the involvement of BK potassium channels. Single-channel recordings in 'perforated microvesicles' confirmed that leptin increased BK channel open probability without altering its unitary conductance. BK channel up-regulation was associated with the phosphoinositide 3-kinase (PI3K) signalling cascade because the PI3K specific inhibitor wortmannin (100 nm) fully prevented BK current increase. We also tested the effect of leptin on evoked AP firing and Ca2+-driven exocytosis. Although leptin preserves well-adapted AP trains of lower frequency, APs are broader and depolarization-evoked exocytosis is increased as a result of the larger size of the ready-releasable pool and higher frequency of vesicle release. The kinetics and quantal size of single secretory events remained unaltered. Leptin had no effect on firing and secretion in db-/db- mice lacking the ObR gene, confirming its specificity. In conclusion, leptin exhibits a dual action on MCC activity. It dampens AP firing at rest but preserves AP firing and increases catecholamine secretion during sustained stimulation, highlighting the importance of the adipo-adrenal axis in the leptin-mediated increase of sympathetic tone and catecholamine release. AU - Gavello, Daniela AU - Vandael, David H AU - Gosso, Sara AU - Carbone, Emilio AU - Carabelli, Valentina ID - 1565 IS - 22 JF - Journal of Physiology TI - Dual action of leptin on rest-firing and stimulated catecholamine release via phosphoinositide 3-kinase-riven BK channel up-regulation in mouse chromaffin cells VL - 593 ER - TY - JOUR AU - Gilson, Matthieu AU - Savin, Cristina AU - Zenke, Friedemann ID - 1564 IS - 11 JF - Frontiers in Computational Neuroscience TI - Editorial: Emergent neural computation from the interaction of different forms of plasticity VL - 9 ER - TY - JOUR AB - Multiple plant developmental processes, such as lateral root development, depend on auxin distribution patterns that are in part generated by the PIN-formed family of auxin-efflux transporters. Here we propose that AUXIN RESPONSE FACTOR7 (ARF7) and the ARF7-regulated FOUR LIPS/MYB124 (FLP) transcription factors jointly form a coherent feed-forward motif that mediates the auxin-responsive PIN3 transcription in planta to steer the early steps of lateral root formation. This regulatory mechanism might endow the PIN3 circuitry with a temporal 'memory' of auxin stimuli, potentially maintaining and enhancing the robustness of the auxin flux directionality during lateral root development. The cooperative action between canonical auxin signalling and other transcription factors might constitute a general mechanism by which transcriptional auxin-sensitivity can be regulated at a tissue-specific level. AU - Chen, Qian AU - Liu, Yang AU - Maere, Steven AU - Lee, Eunkyoung AU - Van Isterdael, Gert AU - Xie, Zidian AU - Xuan, Wei AU - Lucas, Jessica AU - Vassileva, Valya AU - Kitakura, Saeko AU - Marhavy, Peter AU - Wabnik, Krzysztof T AU - Geldner, Niko AU - Benková, Eva AU - Le, Jie AU - Fukaki, Hidehiro AU - Grotewold, Erich AU - Li, Chuanyou AU - Friml, Jirí AU - Sack, Fred AU - Beeckman, Tom AU - Vanneste, Steffen ID - 1574 JF - Nature Communications TI - A coherent transcriptional feed-forward motif model for mediating auxin-sensitive PIN3 expression during lateral root development VL - 6 ER - TY - JOUR AB - The immune response relies on the migration of leukocytes and on their ability to stop in precise anatomical locations to fulfil their task. How leukocyte migration and function are coordinated is unknown. Here we show that in immature dendritic cells, which patrol their environment by engulfing extracellular material, cell migration and antigen capture are antagonistic. This antagonism results from transient enrichment of myosin IIA at the cell front, which disrupts the back-to-front gradient of the motor protein, slowing down locomotion but promoting antigen capture. We further highlight that myosin IIA enrichment at the cell front requires the MHC class II-associated invariant chain (Ii). Thus, by controlling myosin IIA localization, Ii imposes on dendritic cells an intermittent antigen capture behaviour that might facilitate environment patrolling. We propose that the requirement for myosin II in both cell migration and specific cell functions may provide a general mechanism for their coordination in time and space. AU - Chabaud, Mélanie AU - Heuzé, Mélina AU - Bretou, Marine AU - Vargas, Pablo AU - Maiuri, Paolo AU - Solanes, Paola AU - Maurin, Mathieu AU - Terriac, Emmanuel AU - Le Berre, Maël AU - Lankar, Danielle AU - Piolot, Tristan AU - Adelstein, Robert AU - Zhang, Yingfan AU - Sixt, Michael K AU - Jacobelli, Jordan AU - Bénichou, Olivier AU - Voituriez, Raphaël AU - Piel, Matthieu AU - Lennon Duménil, Ana ID - 1575 JF - Nature Communications TI - Cell migration and antigen capture are antagonistic processes coupled by myosin II in dendritic cells VL - 6 ER - TY - JOUR AB - Spatial regulation of the plant hormone indole-3-acetic acid (IAA, or auxin) is essential for plant development. Auxin gradient establishment is mediated by polarly localized auxin transporters, including PIN-FORMED (PIN) proteins. Their localization and abundance at the plasma membrane are tightly regulated by endomembrane machinery, especially the endocytic and recycling pathways mediated by the ADP ribosylation factor guanine nucleotide exchange factor (ARF-GEF) GNOM. We assessed the role of the early secretory pathway in establishing PIN1 polarity in Arabidopsis thaliana by pharmacological and genetic approaches. We identified the compound endosidin 8 (ES8), which selectively interferes with PIN1 basal polarity without altering the polarity of apical proteins. ES8 alters the auxin distribution pattern in the root and induces a strong developmental phenotype, including reduced root length. The ARF-GEF- defective mutants gnom-like 1 ( gnl1-1) and gnom ( van7) are significantly resistant to ES8. The compound does not affect recycling or vacuolar trafficking of PIN1 but leads to its intracellular accumulation, resulting in loss of PIN1 basal polarity at the plasma membrane. Our data confirm a role for GNOM in endoplasmic reticulum (ER) - Golgi trafficking and reveal that a GNL1/GNOM-mediated early secretory pathway selectively regulates PIN1 basal polarity establishment in a manner essential for normal plant development. AU - Doyle, Siamsa AU - Haegera, Ash AU - Vain, Thomas AU - Rigala, Adeline AU - Viotti, Corrado AU - Łangowskaa, Małgorzata AU - Maa, Qian AU - Friml, Jirí AU - Raikhel, Natasha AU - Hickse, Glenn AU - Robert, Stéphanie ID - 1569 IS - 7 JF - PNAS TI - An early secretory pathway mediated by gnom-like 1 and gnom is essential for basal polarity establishment in Arabidopsis thaliana VL - 112 ER - TY - JOUR AB - Grounding autonomous behavior in the nervous system is a fundamental challenge for neuroscience. In particular, self-organized behavioral development provides more questions than answers. Are there special functional units for curiosity, motivation, and creativity? This paper argues that these features can be grounded in synaptic plasticity itself, without requiring any higher-level constructs. We propose differential extrinsic plasticity (DEP) as a new synaptic rule for self-learning systems and apply it to a number of complex robotic systems as a test case. Without specifying any purpose or goal, seemingly purposeful and adaptive rhythmic behavior is developed, displaying a certain level of sensorimotor intelligence. These surprising results require no systemspecific modifications of the DEP rule. They rather arise from the underlying mechanism of spontaneous symmetry breaking,which is due to the tight brain body environment coupling. The new synaptic rule is biologically plausible and would be an interesting target for neurobiological investigation. We also argue that this neuronal mechanism may have been a catalyst in natural evolution. AU - Der, Ralf AU - Martius, Georg S ID - 1570 IS - 45 JF - PNAS TI - Novel plasticity rule can explain the development of sensorimotor intelligence VL - 112 ER - TY - JOUR AB - We consider the quantum ferromagnetic Heisenberg model in three dimensions, for all spins S ≥ 1/2. We rigorously prove the validity of the spin-wave approximation for the excitation spectrum, at the level of the first non-trivial contribution to the free energy at low temperatures. Our proof comes with explicit, constructive upper and lower bounds on the error term. It uses in an essential way the bosonic formulation of the model in terms of the Holstein-Primakoff representation. In this language, the model describes interacting bosons with a hard-core on-site repulsion and a nearest-neighbor attraction. This attractive interaction makes the lower bound on the free energy particularly tricky: the key idea there is to prove a differential inequality for the two-particle density, which is thereby shown to be smaller than the probability density of a suitably weighted two-particle random process on the lattice. AU - Correggi, Michele AU - Giuliani, Alessandro AU - Seiringer, Robert ID - 1572 IS - 1 JF - Communications in Mathematical Physics TI - Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet VL - 339 ER - TY - JOUR AB - We present a new, simpler proof of the unconditional uniqueness of solutions to the cubic Gross-Pitaevskii hierarchy in ℝ3. One of the main tools in our analysis is the quantum de Finetti theorem. Our uniqueness result is equivalent to the one established in the celebrated works of Erdos, Schlein, and Yau. AU - Chen, Thomas AU - Hainzl, Christian AU - Pavlović, Nataša AU - Seiringer, Robert ID - 1573 IS - 10 JF - Communications on Pure and Applied Mathematics TI - Unconditional uniqueness for the cubic gross pitaevskii hierarchy via quantum de finetti VL - 68 ER - TY - JOUR AB - Synapsins (Syns) are an evolutionarily conserved family of presynaptic proteins crucial for the fine-tuning of synaptic function. A large amount of experimental evidences has shown that Syns are involved in the development of epileptic phenotypes and several mutations in Syn genes have been associated with epilepsy in humans and animal models. Syn mutations induce alterations in circuitry and neurotransmitter release, differentially affecting excitatory and inhibitory synapses, thus causing an excitation/inhibition imbalance in network excitability toward hyperexcitability that may be a determinant with regard to the development of epilepsy. Another approach to investigate epileptogenic mechanisms is to understand how silencing Syn affects the cellular behavior of single neurons and is associated with the hyperexcitable phenotypes observed in epilepsy. Here, we examined the functional effects of antisense-RNA inhibition of Syn expression on individually identified and isolated serotonergic cells of the Helix land snail. We found that Helix synapsin silencing increases cell excitability characterized by a slightly depolarized resting membrane potential, decreases the rheobase, reduces the threshold for action potential (AP) firing and increases the mean and instantaneous firing rates, with respect to control cells. The observed increase of Ca2+ and BK currents in Syn-silenced cells seems to be related to changes in the shape of the AP waveform. These currents sustain the faster spiking in Syn-deficient cells by increasing the after hyperpolarization and limiting the Na+ and Ca2+ channel inactivation during repetitive firing. This in turn speeds up the depolarization phase by reaching the AP threshold faster. Our results provide evidence that Syn silencing increases intrinsic cell excitability associated with increased Ca2+ and Ca2+-dependent BK currents in the absence of excitatory or inhibitory inputs. AU - Brenes, Oscar AU - Vandael, David H AU - Carbone, Emilio AU - Montarolo, Pier AU - Ghirardi, Mirella ID - 1580 JF - Neuroscience TI - Knock-down of synapsin alters cell excitability and action potential waveform by potentiating BK and voltage gated Ca2 currents in Helix serotonergic neurons VL - 311 ER - TY - JOUR AB - Contrary to the pattern seen in mammalian sex chromosomes, where most Y-linked genes have X-linked homologs, the Drosophila X and Y chromosomes appear to be unrelated. Most of the Y-linked genes have autosomal paralogs, so autosome-to-Y transposition must be the main source of Drosophila Y-linked genes. Here we show how these genes were acquired. We found a previously unidentified gene (flagrante delicto Y, FDY) that originated from a recent duplication of the autosomal gene vig2 to the Y chromosome of Drosophila melanogaster. Four contiguous genes were duplicated along with vig2, but they became pseudogenes through the accumulation of deletions and transposable element insertions, whereas FDY remained functional, acquired testis-specific expression, and now accounts for ∼20% of the vig2-like mRNA in testis. FDY is absent in the closest relatives of D. melanogaster, and DNA sequence divergence indicates that the duplication to the Y chromosome occurred ∼2 million years ago. Thus, FDY provides a snapshot of the early stages of the establishment of a Y-linked gene and demonstrates how the Drosophila Y has been accumulating autosomal genes. AU - Carvalho, Antonio AU - Vicoso, Beatriz AU - Russo, Claudia AU - Swenor, Bonnielin AU - Clark, Andrew ID - 1577 IS - 40 JF - PNAS TI - Birth of a new gene on the Y chromosome of Drosophila melanogaster VL - 112 ER - TY - JOUR AB - We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. This constitutes the largest family of enumerative problems whose Galois groups have been largely determined. Using a criterion of Vakil and a special position argument due to Schubert, our result follows from a particular inequality among Kostka numbers of two-rowed tableaux. In most cases, a combinatorial injection proves the inequality. For the remaining cases, we use the Weyl integral formulas to obtain an integral formula for these Kostka numbers. This rewrites the inequality as an integral, which we estimate to establish the inequality. AU - Brooks, Christopher AU - Martin Del Campo Sanchez, Abraham AU - Sottile, Frank ID - 1579 IS - 6 JF - Transactions of the American Mathematical Society TI - Galois groups of Schubert problems of lines are at least alternating VL - 367 ER - TY - JOUR AB - We investigate the dynamics of ferrofluidic wavy vortex flows in the counter-rotating Taylor-Couette system, with a focus on wavy flows with a mixture of the dominant azimuthal modes. Without external magnetic field flows are stable and pro-grade with respect to the rotation of the inner cylinder. More complex behaviors can arise when an axial or a transverse magnetic field is applied. Depending on the direction and strength of the field, multi-stable wavy states and bifurcations can occur. We uncover the phenomenon of flow pattern reversal as the strength of the magnetic field is increased through a critical value. In between the regimes of pro-grade and retrograde flow rotations, standing waves with zero angular velocities can emerge. A striking finding is that, under a transverse magnetic field, a second reversal in the flow pattern direction can occur, where the flow pattern evolves into pro-grade rotation again from a retrograde state. Flow reversal is relevant to intriguing phenomena in nature such as geomagnetic reversal. Our results suggest that, in ferrofluids, flow pattern reversal can be induced by varying a magnetic field in a controlled manner, which can be realized in laboratory experiments with potential applications in the development of modern fluid devices. AU - Altmeyer, Sebastian AU - Do, Younghae AU - Lai, Ying ID - 1589 JF - Scientific Reports TI - Magnetic field induced flow pattern reversal in a ferrofluidic Taylor-Couette system VL - 5 ER - TY - JOUR AB - We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights. AU - Biedl, Therese AU - Held, Martin AU - Huber, Stefan AU - Kaaser, Dominik AU - Palfrader, Peter ID - 1584 IS - 5 JF - Computational Geometry: Theory and Applications TI - Reprint of: Weighted straight skeletons in the plane VL - 48 ER - TY - JOUR AB - We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights. AU - Biedl, Therese AU - Held, Martin AU - Huber, Stefan AU - Kaaser, Dominik AU - Palfrader, Peter ID - 1582 IS - 2 JF - Computational Geometry: Theory and Applications TI - Weighted straight skeletons in the plane VL - 48 ER - TY - JOUR AB - We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in O(nlogn) time and O(n) space, where n denotes the number of vertices of the polygon. AU - Biedl, Therese AU - Held, Martin AU - Huber, Stefan AU - Kaaser, Dominik AU - Palfrader, Peter ID - 1583 IS - 2 JF - Information Processing Letters TI - A simple algorithm for computing positively weighted straight skeletons of monotone polygons VL - 115 ER - TY - JOUR AB - We investigate the quantum interference shifts between energetically close states, where the state structure is observed by laser spectroscopy. We report a compact and analytical expression that models the quantum interference induced shift for any admixture of circular polarization of the incident laser and angle of observation. An experimental scenario free of quantum interference can thus be predicted with this formula. Although this study is exemplified here for muonic deuterium, it can be applied to any other laser spectroscopy measurement of ns-n′p frequencies of a nonrelativistic atomic system, via an ns→n′p→n′′s scheme. AU - Amaro, Pedro AU - Fratini, Filippo AU - Safari, Laleh AU - Antognini, Aldo AU - Indelicato, Paul AU - Pohl, Randolf AU - Santos, José ID - 1587 IS - 6 JF - Physical Review A - Atomic, Molecular, and Optical Physics TI - Quantum interference shifts in laser spectroscopy with elliptical polarization VL - 92 ER - TY - JOUR AB - Plants are sessile organisms that are permanently restricted to their site of germination. To compensate for their lack of mobility, plants evolved unique mechanisms enabling them to rapidly react to ever changing environmental conditions and flexibly adapt their postembryonic developmental program. A prominent demonstration of this developmental plasticity is their ability to bend organs in order to reach the position most optimal for growth and utilization of light, nutrients, and other resources. Shortly after germination, dicotyledonous seedlings form a bended structure, the so-called apical hook, to protect the delicate shoot meristem and cotyledons from damage when penetrating through the soil. Upon perception of a light stimulus, the apical hook rapidly opens and the photomorphogenic developmental program is activated. After germination, plant organs are able to align their growth with the light source and adopt the most favorable orientation through bending, in a process named phototropism. On the other hand, when roots and shoots are diverted from their upright orientation, they immediately detect a change in the gravity vector and bend to maintain a vertical growth direction. Noteworthy, despite the diversity of external stimuli perceived by different plant organs, all plant tropic movements share a common mechanistic basis: differential cell growth. In our review, we will discuss the molecular principles underlying various tropic responses with the focus on mechanisms mediating the perception of external signals, transduction cascades and downstream responses that regulate differential cell growth and consequently, organ bending. In particular, we highlight common and specific features of regulatory pathways in control of the bending of organs and a role for the plant hormone auxin as a key regulatory component. AU - Žádníková, Petra AU - Smet, Dajo AU - Zhu, Qiang AU - Van Der Straeten, Dominique AU - Benková, Eva ID - 1593 IS - 4 JF - Frontiers in Plant Science TI - Strategies of seedlings to overcome their sessile nature: Auxin in mobility control VL - 6 ER - TY - CONF AB - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, . . . , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing- free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth. AU - Fulek, Radoslav AU - Pelsmajer, Michael AU - Schaefer, Marcus ID - 1595 TI - Hanani-Tutte for radial planarity VL - 9411 ER - TY - CHAP AB - The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed. AU - Aichholzer, Oswin AU - Biedl, Therese AU - Hackl, Thomas AU - Held, Martin AU - Huber, Stefan AU - Palfrader, Peter AU - Vogtenhuber, Birgit ID - 1590 SN - 978-3-319-27260-3 T2 - Graph Drawing and Network Visualization TI - Representing directed trees as straight skeletons VL - 9411 ER - TY - CHAP AB - Let C={C1,...,Cn} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for everyi < j the intersection Ci and (Ci ∩ Cj)\⋃i<l<jCl =∅.elements that are stacked between them, i.e., We show that if C forms a visibility clique its size is bounded from above by O(k4) thereby improving the upper bound of 22k from the aforementioned paper. We also obtain an upper bound of 22(k/2)+2 on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon. AU - Fulek, Radoslav AU - Radoičić, Radoš ID - 1596 SN - 978-3-319-27260-3 T2 - Graph Drawing and Network Visualization TI - Vertical visibility among parallel polygons in three dimensions VL - 9411 ER - TY - CONF AB - We propose a flexible exchange format for ω-automata, as typically used in formal verification, and implement support for it in a range of established tools. Our aim is to simplify the interaction of tools, helping the research community to build upon other people’s work. A key feature of the format is the use of very generic acceptance conditions, specified by Boolean combinations of acceptance primitives, rather than being limited to common cases such as Büchi, Streett, or Rabin. Such flexibility in the choice of acceptance conditions can be exploited in applications, for example in probabilistic model checking, and furthermore encourages the development of acceptance-agnostic tools for automata manipulations. The format allows acceptance conditions that are either state-based or transition-based, and also supports alternating automata. AU - Babiak, Tomáš AU - Blahoudek, František AU - Duret Lutz, Alexandre AU - Klein, Joachim AU - Kretinsky, Jan AU - Mueller, Daniel AU - Parker, David AU - Strejček, Jan ID - 1601 TI - The Hanoi omega-automata format VL - 9206 ER - TY - CONF AB - Multiaffine hybrid automata (MHA) represent a powerful formalism to model complex dynamical systems. This formalism is particularly suited for the representation of biological systems which often exhibit highly non-linear behavior. In this paper, we consider the problem of parameter identification for MHA. We present an abstraction of MHA based on linear hybrid automata, which can be analyzed by the SpaceEx model checker. This abstraction enables a precise handling of time-dependent properties. We demonstrate the potential of our approach on a model of a genetic regulatory network and a myocyte model. AU - Bogomolov, Sergiy AU - Schilling, Christian AU - Bartocci, Ezio AU - Batt, Grégory AU - Kong, Hui AU - Grosu, Radu ID - 1605 TI - Abstraction-based parameter synthesis for multiaffine systems VL - 9434 ER - TY - CONF AB - The synthesis problem asks for the automatic construction of a system from its specification. In the traditional setting, the system is “constructed from scratch” rather than composed from reusable components. However, this is rare in practice, and almost every non-trivial software system relies heavily on the use of libraries of reusable components. Recently, Lustig and Vardi introduced dataflow and controlflow synthesis from libraries of reusable components. They proved that dataflow synthesis is undecidable, while controlflow synthesis is decidable. The problem of controlflow synthesis from libraries of probabilistic components was considered by Nain, Lustig and Vardi, and was shown to be decidable for qualitative analysis (that asks that the specification be satisfied with probability 1). Our main contribution for controlflow synthesis from probabilistic components is to establish better complexity bounds for the qualitative analysis problem, and to show that the more general quantitative problem is undecidable. For the qualitative analysis, we show that the problem (i) is EXPTIME-complete when the specification is given as a deterministic parity word automaton, improving the previously known 2EXPTIME upper bound; and (ii) belongs to UP ∩ coUP and is parity-games hard, when the specification is given directly as a parity condition on the components, improving the previously known EXPTIME upper bound. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Vardi, Moshe ID - 1609 SN - 978-3-662-47665-9 T2 - 42nd International Colloquium TI - The complexity of synthesis from probabilistic components VL - 9135 ER - TY - JOUR AB - Loss-of-function mutations in the synaptic adhesion protein Neuroligin-4 are among the most common genetic abnormalities associated with autism spectrum disorders, but little is known about the function of Neuroligin-4 and the consequences of its loss. We assessed synaptic and network characteristics in Neuroligin-4 knockout mice, focusing on the hippocampus as a model brain region with a critical role in cognition and memory, and found that Neuroligin-4 deletion causes subtle defects of the protein composition and function of GABAergic synapses in the hippocampal CA3 region. Interestingly, these subtle synaptic changes are accompanied by pronounced perturbations of γ-oscillatory network activity, which has been implicated in cognitive function and is altered in multiple psychiatric and neurodevelopmental disorders. Our data provide important insights into the mechanisms by which Neuroligin-4-dependent GABAergic synapses may contribute to autism phenotypes and indicate new strategies for therapeutic approaches. AU - Hammer, Matthieu AU - Krueger Burg, Dilja AU - Tuffy, Liam AU - Cooper, Benjamin AU - Taschenberger, Holger AU - Goswami, Sarit AU - Ehrenreich, Hannelore AU - Jonas, Peter M AU - Varoqueaux, Frederique AU - Rhee, Jeong AU - Brose, Nils ID - 1615 IS - 3 JF - Cell Reports TI - Perturbed hippocampal synaptic inhibition and γ-oscillations in a neuroligin-4 knockout mouse model of autism VL - 13 ER - TY - JOUR AB - GABAergic perisoma-inhibiting fast-spiking interneurons (PIIs) effectively control the activity of large neuron populations by their wide axonal arborizations. It is generally assumed that the output of one PII to its target cells is strong and rapid. Here, we show that, unexpectedly, both strength and time course of PII-mediated perisomatic inhibition change with distance between synaptically connected partners in the rodent hippocampus. Synaptic signals become weaker due to lower contact numbers and decay more slowly with distance, very likely resulting from changes in GABAA receptor subunit composition. When distance-dependent synaptic inhibition is introduced to a rhythmically active neuronal network model, randomly driven principal cell assemblies are strongly synchronized by the PIIs, leading to higher precision in principal cell spike times than in a network with uniform synaptic inhibition. AU - Strüber, Michael AU - Jonas, Peter M AU - Bartos, Marlene ID - 1614 IS - 4 JF - PNAS TI - Strength and duration of perisomatic GABAergic inhibition depend on distance between synaptically connected cells VL - 112 ER - TY - JOUR AB - Biosensors for signaling molecules allow the study of physiological processes by bringing together the fields of protein engineering, fluorescence imaging, and cell biology. Construction of genetically encoded biosensors generally relies on the availability of a binding "core" that is both specific and stable, which can then be combined with fluorescent molecules to create a sensor. However, binding proteins with the desired properties are often not available in nature and substantial improvement to sensors can be required, particularly with regard to their durability. Ancestral protein reconstruction is a powerful protein-engineering tool able to generate highly stable and functional proteins. In this work, we sought to establish the utility of ancestral protein reconstruction to biosensor development, beginning with the construction of an l-arginine biosensor. l-arginine, as the immediate precursor to nitric oxide, is an important molecule in many physiological contexts including brain function. Using a combination of ancestral reconstruction and circular permutation, we constructed a Förster resonance energy transfer (FRET) biosensor for l-arginine (cpFLIPR). cpFLIPR displays high sensitivity and specificity, with a Kd of ∼14 μM and a maximal dynamic range of 35%. Importantly, cpFLIPR was highly robust, enabling accurate l-arginine measurement at physiological temperatures. We established that cpFLIPR is compatible with two-photon excitation fluorescence microscopy and report l-arginine concentrations in brain tissue. AU - Whitfield, Jason AU - Zhang, William AU - Herde, Michel AU - Clifton, Ben AU - Radziejewski, Johanna AU - Janovjak, Harald L AU - Henneberger, Christian AU - Jackson, Colin ID - 1611 IS - 9 JF - Protein Science TI - Construction of a robust and sensitive arginine biosensor through ancestral protein reconstruction VL - 24 ER - TY - JOUR AB - Population structure can facilitate evolution of cooperation. In a structured population, cooperators can form clusters which resist exploitation by defectors. Recently, it was observed that a shift update rule is an extremely strong amplifier of cooperation in a one dimensional spatial model. For the shift update rule, an individual is chosen for reproduction proportional to fecundity; the offspring is placed next to the parent; a random individual dies. Subsequently, the population is rearranged (shifted) until all individual cells are again evenly spaced out. For large population size and a one dimensional population structure, the shift update rule favors cooperation for any benefit-to-cost ratio greater than one. But every attempt to generalize shift updating to higher dimensions while maintaining its strong effect has failed. The reason is that in two dimensions the clusters are fragmented by the movements caused by rearranging the cells. Here we introduce the natural phenomenon of a repulsive force between cells of different types. After a birth and death event, the cells are being rearranged minimizing the overall energy expenditure. If the repulsive force is sufficiently high, shift becomes a strong promoter of cooperation in two dimensions. AU - Pavlogiannis, Andreas AU - Chatterjee, Krishnendu AU - Adlam, Ben AU - Nowak, Martin ID - 1624 JF - Scientific Reports TI - Cellular cooperation with shift updating and repulsion VL - 5 ER - TY - JOUR AB - Background Photosynthetic cyanobacteria are attractive for a range of biotechnological applications including biofuel production. However, due to slow growth, screening of mutant libraries using microtiter plates is not feasible. Results We present a method for high-throughput, single-cell analysis and sorting of genetically engineered l-lactate-producing strains of Synechocystis sp. PCC6803. A microfluidic device is used to encapsulate single cells in picoliter droplets, assay the droplets for l-lactate production, and sort strains with high productivity. We demonstrate the separation of low- and high-producing reference strains, as well as enrichment of a more productive l-lactate-synthesizing population after UV-induced mutagenesis. The droplet platform also revealed population heterogeneity in photosynthetic growth and lactate production, as well as the presence of metabolically stalled cells. Conclusions The workflow will facilitate metabolic engineering and directed evolution studies and will be useful in studies of cyanobacteria biochemistry and physiology. AU - Hammar, Petter AU - Angermayr, Andreas AU - Sjostrom, Staffan AU - Van Der Meer, Josefin AU - Hellingwerf, Klaas AU - Hudson, Elton AU - Joensson, Hakaan ID - 1623 IS - 1 JF - Biotechnology for Biofuels TI - Single-cell screening of photosynthetic growth and lactate production by cyanobacteria VL - 8 ER - TY - CONF AB - We propose a method for fabricating deformable objects with spatially varying elasticity using 3D printing. Using a single, relatively stiff printer material, our method designs an assembly of smallscale microstructures that have the effect of a softer material at the object scale, with properties depending on the microstructure used in each part of the object. We build on work in the area of metamaterials, using numerical optimization to design tiled microstructures with desired properties, but with the key difference that our method designs families of related structures that can be interpolated to smoothly vary the material properties over a wide range. To create an object with spatially varying elastic properties, we tile the object's interior with microstructures drawn from these families, generating a different microstructure for each cell using an efficient algorithm to select compatible structures for neighboring cells. We show results computed for both 2D and 3D objects, validating several 2D and 3D printed structures using standard material tests as well as demonstrating various example applications. AU - Schumacher, Christian AU - Bickel, Bernd AU - Rys, Jan AU - Marschner, Steve AU - Daraio, Chiara AU - Gross, Markus ID - 1628 IS - 4 TI - Microstructures to control elasticity in 3D printing VL - 34 ER - TY - CONF AB - Simulating the delightful dynamics of soap films, bubbles, and foams has traditionally required the use of a fully three-dimensional many-phase Navier-Stokes solver, even though their visual appearance is completely dominated by the thin liquid surface. We depart from earlier work on soap bubbles and foams by noting that their dynamics are naturally described by a Lagrangian vortex sheet model in which circulation is the primary variable. This leads us to derive a novel circulation-preserving surface-only discretization of foam dynamics driven by surface tension on a non-manifold triangle mesh. We represent the surface using a mesh-based multimaterial surface tracker which supports complex bubble topology changes, and evolve the surface according to the ambient air flow induced by a scalar circulation field stored on the mesh. Surface tension forces give rise to a simple update rule for circulation, even at non-manifold Plateau borders, based on a discrete measure of signed scalar mean curvature. We further incorporate vertex constraints to enable the interaction of soap films with wires. The result is a method that is at once simple, robust, and efficient, yet able to capture an array of soap films behaviors including foam rearrangement, catenoid collapse, blowing bubbles, and double bubbles being pulled apart. AU - Da, Fang AU - Batty, Christopher AU - Wojtan, Christopher J AU - Grinspun, Eitan ID - 1634 IS - 4 TI - Double bubbles sans toil and trouble: discrete circulation-preserving vortex sheets for soap films and foams VL - 34 ER - TY - CONF AB - Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism R→ΓΓ between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side ΓΓ is fixed and the left side R is unconstrained. Far fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that R belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template ΓΓ (from a certain class of languages) for which the problem is tractable when R is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph. As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs. AU - Kolmogorov, Vladimir AU - Rolinek, Michal AU - Takhanov, Rustem ID - 1636 SN - 978-3-662-48970-3 T2 - 26th International Symposium TI - Effectiveness of structural restrictions for hybrid CSPs VL - 9472 ER - TY - CONF AB - This paper presents a liquid simulation technique that enforces the incompressibility condition using a stream function solve instead of a pressure projection. Previous methods have used stream function techniques for the simulation of detailed single-phase flows, but a formulation for liquid simulation has proved elusive in part due to the free surface boundary conditions. In this paper, we introduce a stream function approach to liquid simulations with novel boundary conditions for free surfaces, solid obstacles, and solid-fluid coupling. Although our approach increases the dimension of the linear system necessary to enforce incompressibility, it provides interesting and surprising benefits. First, the resulting flow is guaranteed to be divergence-free regardless of the accuracy of the solve. Second, our free-surface boundary conditions guarantee divergence-free motion even in the un-simulated air phase, which enables two-phase flow simulation by only computing a single phase. We implemented this method using a variant of FLIP simulation which only samples particles within a narrow band of the liquid surface, and we illustrate the effectiveness of our method for detailed two-phase flow simulations with complex boundaries, detailed bubble interactions, and two-way solid-fluid coupling. AU - Ando, Ryoichi AU - Thuerey, Nils AU - Wojtan, Christopher J ID - 1632 IS - 4 TI - A stream function solver for liquid simulations VL - 34 ER - TY - CONF AB - We present a method to learn and propagate shape placements in 2D polygonal scenes from a few examples provided by a user. The placement of a shape is modeled as an oriented bounding box. Simple geometric relationships between this bounding box and nearby scene polygons define a feature set for the placement. The feature sets of all example placements are then used to learn a probabilistic model over all possible placements and scenes. With this model, we can generate a new set of placements with similar geometric relationships in any given scene. We introduce extensions that enable propagation and generation of shapes in 3D scenes, as well as the application of a learned modeling session to large scenes without additional user interaction. These concepts allow us to generate complex scenes with thousands of objects with relatively little user interaction. AU - Guerrero, Paul AU - Jeschke, Stefan AU - Wimmer, Michael AU - Wonka, Peter ID - 1630 IS - 4 TI - Learning shape placements by example VL - 34 ER - TY - JOUR AB - Auxin and cytokinin are key endogenous regulators of plant development. Although cytokinin-mediated modulation of auxin distribution is a developmentally crucial hormonal interaction, its molecular basis is largely unknown. Here we show a direct regulatory link between cytokinin signalling and the auxin transport machinery uncovering a mechanistic framework for cytokinin-auxin cross-talk. We show that the CYTOKININ RESPONSE FACTORS (CRFs), transcription factors downstream of cytokinin perception, transcriptionally control genes encoding PIN-FORMED (PIN) auxin transporters at a specific PIN CYTOKININ RESPONSE ELEMENT (PCRE) domain. Removal of this cis-regulatory element effectively uncouples PIN transcription from the CRF-mediated cytokinin regulation and attenuates plant cytokinin sensitivity. We propose that CRFs represent a missing cross-talk component that fine-tunes auxin transport capacity downstream of cytokinin signalling to control plant development. AU - Šimášková, Mária AU - O'Brien, José AU - Khan-Djamei, Mamoona AU - Van Noorden, Giel AU - Ötvös, Krisztina AU - Vieten, Anne AU - De Clercq, Inge AU - Van Haperen, Johanna AU - Cuesta, Candela AU - Hoyerová, Klára AU - Vanneste, Steffen AU - Marhavy, Peter AU - Wabnik, Krzysztof T AU - Van Breusegem, Frank AU - Nowack, Moritz AU - Murphy, Angus AU - Friml, Jiřĺ AU - Weijers, Dolf AU - Beeckman, Tom AU - Benková, Eva ID - 1640 JF - Nature Communications TI - Cytokinin response factors regulate PIN-FORMED auxin transporters VL - 6 ER - TY - JOUR AB - The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident to at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm. AU - Fulek, Radoslav AU - Kynčl, Jan AU - Malinovič, Igor AU - Pálvölgyi, Dömötör ID - 1642 IS - 4 JF - Electronic Journal of Combinatorics TI - Clustered planarity testing revisited VL - 22 ER - TY - JOUR AB - In this paper the optimal transport and the metamorphosis perspectives are combined. For a pair of given input images geodesic paths in the space of images are defined as minimizers of a resulting path energy. To this end, the underlying Riemannian metric measures the rate of transport cost and the rate of viscous dissipation. Furthermore, the model is capable to deal with strongly varying image contrast and explicitly allows for sources and sinks in the transport equations which are incorporated in the metric related to the metamorphosis approach by Trouvé and Younes. In the non-viscous case with source term existence of geodesic paths is proven in the space of measures. The proposed model is explored on the range from merely optimal transport to strongly dissipative dynamics. For this model a robust and effective variational time discretization of geodesic paths is proposed. This requires to minimize a discrete path energy consisting of a sum of consecutive image matching functionals. These functionals are defined on corresponding pairs of intensity functions and on associated pairwise matching deformations. Existence of time discrete geodesics is demonstrated. Furthermore, a finite element implementation is proposed and applied to instructive test cases and to real images. In the non-viscous case this is compared to the algorithm proposed by Benamou and Brenier including a discretization of the source term. Finally, the model is generalized to define discrete weighted barycentres with applications to textures and objects. AU - Maas, Jan AU - Rumpf, Martin AU - Schönlieb, Carola AU - Simon, Stefan ID - 1639 IS - 6 JF - ESAIM: Mathematical Modelling and Numerical Analysis TI - A generalized model for optimal transport of images including dissipation and density modulation VL - 49 ER - TY - CONF AB - A pseudorandom function (PRF) is a keyed function F : K × X → Y where, for a random key k ∈ K, the function F(k, ·) is indistinguishable from a uniformly random function, given black-box access. A key-homomorphic PRF has the additional feature that for any keys k, k' and any input x, we have F(k+k', x) = F(k, x)⊕F(k', x) for some group operations +,⊕ on K and Y, respectively. A constrained PRF for a family of setsS ⊆ P(X) has the property that, given any key k and set S ∈ S, one can efficiently compute a “constrained” key kS that enables evaluation of F(k, x) on all inputs x ∈ S, while the values F(k, x) for x /∈ S remain pseudorandom even given kS. In this paper we construct PRFs that are simultaneously constrained and key homomorphic, where the homomorphic property holds even for constrained keys. We first show that the multilinear map-based bit-fixing and circuit-constrained PRFs of Boneh and Waters (Asiacrypt 2013) can be modified to also be keyhomomorphic. We then show that the LWE-based key-homomorphic PRFs of Banerjee and Peikert (Crypto 2014) are essentially already prefix-constrained PRFs, using a (non-obvious) definition of constrained keys and associated group operation. Moreover, the constrained keys themselves are pseudorandom, and the constraining and evaluation functions can all be computed in low depth. As an application of key-homomorphic constrained PRFs,we construct a proxy re-encryption schemewith fine-grained access control. This scheme allows storing encrypted data on an untrusted server, where each file can be encrypted relative to some attributes, so that only parties whose constrained keys match the attributes can decrypt. Moreover, the server can re-key (arbitrary subsets of) the ciphertexts without learning anything about the plaintexts, thus permitting efficient and finegrained revocation. AU - Banerjee, Abishek AU - Fuchsbauer, Georg AU - Peikert, Chris AU - Pietrzak, Krzysztof Z AU - Stevens, Sophie ID - 1646 SN - 978-3-662-46496-0 T2 - 12th Theory of Cryptography Conference TI - Key-homomorphic constrained pseudorandom functions VL - 9015 ER - TY - CONF AB - Generalized Selective Decryption (GSD), introduced by Panjwani [TCC’07], is a game for a symmetric encryption scheme Enc that captures the difficulty of proving adaptive security of certain protocols, most notably the Logical Key Hierarchy (LKH) multicast encryption protocol. In the GSD game there are n keys k1,..., kn, which the adversary may adaptively corrupt (learn); moreover, it can ask for encryptions Encki (kj) of keys under other keys. The adversary’s task is to distinguish keys (which it cannot trivially compute) from random. Proving the hardness of GSD assuming only IND-CPA security of Enc is surprisingly hard. Using “complexity leveraging” loses a factor exponential in n, which makes the proof practically meaningless. We can think of the GSD game as building a graph on n vertices, where we add an edge i → j when the adversary asks for an encryption of kj under ki. If restricted to graphs of depth ℓ, Panjwani gave a reduction that loses only a factor exponential in ℓ (not n). To date, this is the only non-trivial result known for GSD. In this paper we give almost-polynomial reductions for large classes of graphs. Most importantly, we prove the security of the GSD game restricted to trees losing only a quasi-polynomial factor n3 log n+5. Trees are an important special case capturing real-world protocols like the LKH protocol. Our new bound improves upon Panjwani’s on some LKH variants proposed in the literature where the underlying tree is not balanced. Our proof builds on ideas from the “nested hybrids” technique recently introduced by Fuchsbauer et al. [Asiacrypt’14] for proving the adaptive security of constrained PRFs. AU - Fuchsbauer, Georg AU - Jafargholi, Zahra AU - Pietrzak, Krzysztof Z ID - 1648 TI - A quasipolynomial reduction for generalized selective decryption on trees VL - 9215 ER - TY - CONF AB - We extend a commitment scheme based on the learning with errors over rings (RLWE) problem, and present efficient companion zeroknowledge proofs of knowledge. Our scheme maps elements from the ring (or equivalently, n elements from AU - Benhamouda, Fabrice AU - Krenn, Stephan AU - Lyubashevsky, Vadim AU - Pietrzak, Krzysztof Z ID - 1649 TI - Efficient zero-knowledge proofs for commitments from learning with errors over rings VL - 9326 ER - TY - CONF AB - Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it c times, for some parameter c, in the hope that any query to the scheme requires c evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem. This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing R queries (for the adversary) into one provably allowing only r < R queries. Turned around, this means that making r queries to the scheme requires at least R queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve c-fold QCA for both the honest parties and the adversary, for any fixed parameter c. AU - Demay, Grégory AU - Gazi, Peter AU - Maurer, Ueli AU - Tackmann, Björn ID - 1644 TI - Query-complexity amplification for random oracles VL - 9063 ER - TY - CONF AB - Round-optimal blind signatures are notoriously hard to construct in the standard model, especially in the malicious-signer model, where blindness must hold under adversarially chosen keys. This is substantiated by several impossibility results. The only construction that can be termed theoretically efficient, by Garg and Gupta (Eurocrypt’14), requires complexity leveraging, inducing an exponential security loss. We present a construction of practically efficient round-optimal blind signatures in the standard model. It is conceptually simple and builds on the recent structure-preserving signatures on equivalence classes (SPSEQ) from Asiacrypt’14. While the traditional notion of blindness follows from standard assumptions, we prove blindness under adversarially chosen keys under an interactive variant of DDH. However, we neither require non-uniform assumptions nor complexity leveraging. We then show how to extend our construction to partially blind signatures and to blind signatures on message vectors, which yield a construction of one-show anonymous credentials à la “anonymous credentials light” (CCS’13) in the standard model. Furthermore, we give the first SPS-EQ construction under noninteractive assumptions and show how SPS-EQ schemes imply conventional structure-preserving signatures, which allows us to apply optimality results for the latter to SPS-EQ. AU - Fuchsbauer, Georg AU - Hanser, Christian AU - Slamanig, Daniel ID - 1647 TI - Practical round-optimal blind signatures in the standard model VL - 9216 ER - TY - CONF AB - HMAC and its variant NMAC are the most popular approaches to deriving a MAC (and more generally, a PRF) from a cryptographic hash function. Despite nearly two decades of research, their exact security still remains far from understood in many different contexts. Indeed, recent works have re-surfaced interest for {\em generic} attacks, i.e., attacks that treat the compression function of the underlying hash function as a black box. Generic security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question. In this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing. While our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions. AU - Gazi, Peter AU - Pietrzak, Krzysztof Z AU - Tessaro, Stefano ID - 1654 TI - Generic security of NMAC and HMAC with input whitening VL - 9453 ER - TY - CONF AB - We consider the task of deriving a key with high HILL entropy (i.e., being computationally indistinguishable from a key with high min-entropy) from an unpredictable source. Previous to this work, the only known way to transform unpredictability into a key that was ϵ indistinguishable from having min-entropy was via pseudorandomness, for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent limitation that from a source with k bits of unpredictability entropy one can derive a key of length (and thus HILL entropy) at most k−2log(1/ϵ) bits. In many settings, e.g. when dealing with biometric data, such a 2log(1/ϵ) bit entropy loss in not an option. Our main technical contribution is a theorem that states that in the high entropy regime, unpredictability implies HILL entropy. Concretely, any variable K with |K|−d bits of unpredictability entropy has the same amount of so called metric entropy (against real-valued, deterministic distinguishers), which is known to imply the same amount of HILL entropy. The loss in circuit size in this argument is exponential in the entropy gap d, and thus this result only applies for small d (i.e., where the size of distinguishers considered is exponential in d). To overcome the above restriction, we investigate if it’s possible to first “condense” unpredictability entropy and make the entropy gap small. We show that any source with k bits of unpredictability can be condensed into a source of length k with k−3 bits of unpredictability entropy. Our condenser simply “abuses" the GL construction and derives a k bit key from a source with k bits of unpredicatibily. The original GL theorem implies nothing when extracting that many bits, but we show that in this regime, GL still behaves like a “condenser" for unpredictability. This result comes with two caveats (1) the loss in circuit size is exponential in k and (2) we require that the source we start with has no HILL entropy (equivalently, one can efficiently check if a guess is correct). We leave it as an intriguing open problem to overcome these restrictions or to prove they’re inherent. AU - Skórski, Maciej AU - Golovnev, Alexander AU - Pietrzak, Krzysztof Z ID - 1650 TI - Condensed unpredictability VL - 9134 ER - TY - CONF AB - Cryptographic e-cash allows off-line electronic transactions between a bank, users and merchants in a secure and anonymous fashion. A plethora of e-cash constructions has been proposed in the literature; however, these traditional e-cash schemes only allow coins to be transferred once between users and merchants. Ideally, we would like users to be able to transfer coins between each other multiple times before deposit, as happens with physical cash. “Transferable” e-cash schemes are the solution to this problem. Unfortunately, the currently proposed schemes are either completely impractical or do not achieve the desirable anonymity properties without compromises, such as assuming the existence of a trusted “judge” who can trace all coins and users in the system. This paper presents the first efficient and fully anonymous transferable e-cash scheme without any trusted third parties. We start by revising the security and anonymity properties of transferable e-cash to capture issues that were previously overlooked. For our construction we use the recently proposed malleable signatures by Chase et al. to allow the secure and anonymous transfer of coins, combined with a new efficient double-spending detection mechanism. Finally, we discuss an instantiation of our construction. AU - Baldimtsi, Foteini AU - Chase, Melissa AU - Fuchsbauer, Georg AU - Kohlweiss, Markulf ID - 1651 SN - 978-3-662-46446-5 T2 - Public-Key Cryptography - PKC 2015 TI - Anonymous transferable e-cash VL - 9020 ER - TY - CONF AB - We develop new theoretical tools for proving lower-bounds on the (amortized) complexity of certain functions in models of parallel computation. We apply the tools to construct a class of functions with high amortized memory complexity in the parallel Random Oracle Model (pROM); a variant of the standard ROM allowing for batches of simultaneous queries. In particular we obtain a new, more robust, type of Memory-Hard Functions (MHF); a security primitive which has recently been gaining acceptance in practice as an effective means of countering brute-force attacks on security relevant functions. Along the way we also demonstrate an important shortcoming of previous definitions of MHFs and give a new definition addressing the problem. The tools we develop represent an adaptation of the powerful pebbling paradigm (initially introduced by Hewitt and Paterson [HP70] and Cook [Coo73]) to a simple and intuitive parallel setting. We define a simple pebbling game Gp over graphs which aims to abstract parallel computation in an intuitive way. As a conceptual contribution we define a measure of pebbling complexity for graphs called cumulative complexity (CC) and show how it overcomes a crucial shortcoming (in the parallel setting) exhibited by more traditional complexity measures used in the past. As a main technical contribution we give an explicit construction of a constant in-degree family of graphs whose CC in Gp approaches maximality to within a polylogarithmic factor for any graph of equal size (analogous to the graphs of Tarjan et. al. [PTC76, LT82] for sequential pebbling games). Finally, for a given graph G and related function fG, we derive a lower-bound on the amortized memory complexity of fG in the pROM in terms of the CC of G in the game Gp. AU - Alwen, Joel F AU - Serbinenko, Vladimir ID - 1652 T2 - Proceedings of the 47th annual ACM symposium on Theory of computing TI - High parallel complexity graphs and memory-hard functions ER - TY - CONF AB - We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of finitely many patterns, and every run can thus be seen as an infinite sequence of these patterns. The pattern frequency vector assigns to each run the limit of pattern frequencies computed for longer and longer prefixes of the run. If the limit does not exist, then the vector is undefined. We show that for one-counter pVASS, the pattern frequency vector is defined and takes one of finitely many values for almost all runs. Further, these values and their associated probabilities can be approximated up to an arbitrarily small relative error in polynomial time. For stable two-counter pVASS, we show the same result, but we do not provide any upper complexity bound. As a byproduct of our study, we discover counterexamples falsifying some classical results about stochastic Petri nets published in the 80s. AU - Brázdil, Tomáš AU - Kiefer, Stefan AU - Kučera, Antonín AU - Novotny, Petr ID - 1660 TI - Long-run average behaviour of probabilistic vector addition systems ER - TY - JOUR AB - Which genetic alterations drive tumorigenesis and how they evolve over the course of disease and therapy are central questions in cancer biology. Here we identify 44 recurrently mutated genes and 11 recurrent somatic copy number variations through whole-exome sequencing of 538 chronic lymphocytic leukaemia (CLL) and matched germline DNA samples, 278 of which were collected in a prospective clinical trial. These include previously unrecognized putative cancer drivers (RPS15, IKZF3), and collectively identify RNA processing and export, MYC activity, and MAPK signalling as central pathways involved in CLL. Clonality analysis of this large data set further enabled reconstruction of temporal relationships between driver events. Direct comparison between matched pre-treatment and relapse samples from 59 patients demonstrated highly frequent clonal evolution. Thus, large sequencing data sets of clinically informative samples enable the discovery of novel genes associated with cancer, the network of relationships between the driver events, and their impact on disease relapse and clinical outcome. AU - Landau, Dan AU - Tausch, Eugen AU - Taylor Weiner, Amaro AU - Stewart, Chip AU - Reiter, Johannes AU - Bahlo, Jasmin AU - Kluth, Sandra AU - Božić, Ivana AU - Lawrence, Michael AU - Böttcher, Sebastian AU - Carter, Scott AU - Cibulskis, Kristian AU - Mertens, Daniel AU - Sougnez, Carrie AU - Rosenberg, Mara AU - Hess, Julian AU - Edelmann, Jennifer AU - Kless, Sabrina AU - Kneba, Michael AU - Ritgen, Matthias AU - Fink, Anna AU - Fischer, Kirsten AU - Gabriel, Stacey AU - Lander, Eric AU - Nowak, Martin AU - Döhner, Hartmut AU - Hallek, Michael AU - Neuberg, Donna AU - Getz, Gad AU - Stilgenbauer, Stephan AU - Wu, Catherine ID - 1665 IS - 7574 JF - Nature TI - Mutations driving CLL and their evolution in progression and relapse VL - 526 ER - TY - CONF AB - We consider parametric version of fixed-delay continuoustime Markov chains (or equivalently deterministic and stochastic Petri nets, DSPN) where fixed-delay transitions are specified by parameters, rather than concrete values. Our goal is to synthesize values of these parameters that, for a given cost function, minimise expected total cost incurred before reaching a given set of target states. We show that under mild assumptions, optimal values of parameters can be effectively approximated using translation to a Markov decision process (MDP) whose actions correspond to discretized values of these parameters. To this end we identify and overcome several interesting phenomena arising in systems with fixed delays. AU - Brázdil, Tomáš AU - Korenčiak, L'Uboš AU - Krčál, Jan AU - Novotny, Petr AU - Řehák, Vojtěch ID - 1667 TI - Optimizing performance of continuous-time stochastic systems using timeout synthesis VL - 9259 ER - TY - JOUR AB - Over a century of research into the origin of turbulence in wall-bounded shear flows has resulted in a puzzling picture in which turbulence appears in a variety of different states competing with laminar background flow. At moderate flow speeds, turbulence is confined to localized patches; it is only at higher speeds that the entire flow becomes turbulent. The origin of the different states encountered during this transition, the front dynamics of the turbulent regions and the transformation to full turbulence have yet to be explained. By combining experiments, theory and computer simulations, here we uncover a bifurcation scenario that explains the transformation to fully turbulent pipe flow and describe the front dynamics of the different states encountered in the process. Key to resolving this problem is the interpretation of the flow as a bistable system with nonlinear propagation (advection) of turbulent fronts. These findings bridge the gap between our understanding of the onset of turbulence and fully turbulent flows. AU - Barkley, Dwight AU - Song, Baofang AU - Vasudevan, Mukund AU - Lemoult, Grégoire M AU - Avila, Marc AU - Hof, Björn ID - 1664 IS - 7574 JF - Nature TI - The rise of fully turbulent flow VL - 526 ER - TY - CONF AB - Composable notions of incoercibility aim to forbid a coercer from using anything beyond the coerced parties’ inputs and outputs to catch them when they try to deceive him. Existing definitions are restricted to weak coercion types, and/or are not universally composable. Furthermore, they often make too strong assumptions on the knowledge of coerced parties—e.g., they assume they known the identities and/or the strategies of other coerced parties, or those of corrupted parties— which makes them unsuitable for applications of incoercibility such as e-voting, where colluding adversarial parties may attempt to coerce honest voters, e.g., by offering them money for a promised vote, and use their own view to check that the voter keeps his end of the bargain. In this work we put forward the first universally composable notion of incoercible multi-party computation, which satisfies the above intuition and does not assume collusions among coerced parties or knowledge of the corrupted set. We define natural notions of UC incoercibility corresponding to standard coercion-types, i.e., receipt-freeness and resistance to full-active coercion. Importantly, our suggested notion has the unique property that it builds on top of the well studied UC framework by Canetti instead of modifying it. This guarantees backwards compatibility, and allows us to inherit results from the rich UC literature. We then present MPC protocols which realize our notions of UC incoercibility given access to an arguably minimal setup—namely honestly generate tamper-proof hardware performing a very simple cryptographic operation—e.g., a smart card. This is, to our knowledge, the first proposed construction of an MPC protocol (for more than two parties) that is incoercibly secure and universally composable, and therefore the first construction of a universally composable receipt-free e-voting protocol. AU - Alwen, Joel F AU - Ostrovsky, Rafail AU - Zhou, Hongsheng AU - Zikas, Vassilis ID - 1672 SN - 978-3-662-47999-5 T2 - Advances in Cryptology - CRYPTO 2015 TI - Incoercible multi-party computation and universally composable receipt-free voting VL - 9216 ER - TY - CONF AB - Computational notions of entropy (a.k.a. pseudoentropy) have found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The most important tools to argue about pseudoentropy are chain rules, which quantify by how much (in terms of quantity and quality) the pseudoentropy of a given random variable X decreases when conditioned on some other variable Z (think for example of X as a secret key and Z as information leaked by a side-channel). In this paper we give a very simple and modular proof of the chain rule for HILL pseudoentropy, improving best known parameters. Our version allows for increasing the acceptable length of leakage in applications up to a constant factor compared to the best previous bounds. As a contribution of independent interest, we provide a comprehensive study of all known versions of the chain rule, comparing their worst-case strength and limitations. AU - Pietrzak, Krzysztof Z AU - Skórski, Maciej ID - 1669 TI - The chain rule for HILL pseudoentropy, revisited VL - 9230 ER - TY - CONF AB - This paper studies the concrete security of PRFs and MACs obtained by keying hash functions based on the sponge paradigm. One such hash function is KECCAK, selected as NIST’s new SHA-3 standard. In contrast to other approaches like HMAC, the exact security of keyed sponges is not well understood. Indeed, recent security analyses delivered concrete security bounds which are far from existing attacks. This paper aims to close this gap. We prove (nearly) exact bounds on the concrete PRF security of keyed sponges using a random permutation. These bounds are tight for the most relevant ranges of parameters, i.e., for messages of length (roughly) l ≤ min{2n/4, 2r} blocks, where n is the state size and r is the desired output length; and for l ≤ q queries (to the construction or the underlying permutation). Moreover, we also improve standard-model bounds. As an intermediate step of independent interest, we prove tight bounds on the PRF security of the truncated CBC-MAC construction, which operates as plain CBC-MAC, but only returns a prefix of the output. AU - Gazi, Peter AU - Pietrzak, Krzysztof Z AU - Tessaro, Stefano ID - 1671 TI - The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC VL - 9215 ER - TY - JOUR AB - When a new mutant arises in a population, there is a probability it outcompetes the residents and fixes. The structure of the population can affect this fixation probability. Suppressing population structures reduce the difference between two competing variants, while amplifying population structures enhance the difference. Suppressors are ubiquitous and easy to construct, but amplifiers for the large population limit are more elusive and only a few examples have been discovered. Whether or not a population structure is an amplifier of selection depends on the probability distribution for the placement of the invading mutant. First, we prove that there exist only bounded amplifiers for adversarial placement-that is, for arbitrary initial conditions. Next, we show that the Star population structure, which is known to amplify for mutants placed uniformly at random, does not amplify for mutants that arise through reproduction and are therefore placed proportional to the temperatures of the vertices. Finally, we construct population structures that amplify for all mutational events that arise through reproduction, uniformly at random, or through some combination of the two. AU - Adlam, Ben AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 1673 IS - 2181 JF - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences TI - Amplifiers of selection VL - 471 ER - TY - CONF AB - We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number qe of queries to the underlying ideal block cipher, representing adversary’s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number qc of plaintext/ciphertext pairs that is less than the entire codebook. For any such qc, we aim to determine the highest number of block-cipher queries qe the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation. More concretely, we show the following results for key-length extension schemes using a block cipher with n-bit blocks and κ-bit keys: Plain cascades of length ℓ=2r+1 are secure whenever qcqre≪2r(κ+n), qc≪2κ and qe≪22κ. The bound for r=1 also applies to two-key triple encryption (as used within Triple DES). The r-round XOR-cascade is secure as long as qcqre≪2r(κ+n), matching an attack by Gaži (CRYPTO 2013). We fully characterize the security of Gaži and Tessaro’s two-call AU - Gazi, Peter AU - Lee, Jooyoung AU - Seurin, Yannick AU - Steinberger, John AU - Tessaro, Stefano ID - 1668 TI - Relaxing full-codebook security: A refined analysis of key-length extension schemes VL - 9054 ER - TY - JOUR AB - We consider N × N random matrices of the form H = W + V where W is a real symmetric Wigner matrix and V a random or deterministic, real, diagonal matrix whose entries are independent of W. We assume subexponential decay for the matrix entries of W and we choose V so that the eigenvalues of W and V are typically of the same order. For a large class of diagonal matrices V, we show that the rescaled distribution of the extremal eigenvalues is given by the Tracy-Widom distribution F1 in the limit of large N. Our proofs also apply to the complex Hermitian setting, i.e. when W is a complex Hermitian Wigner matrix. AU - Lee, Jioon AU - Schnelli, Kevin ID - 1674 IS - 8 JF - Reviews in Mathematical Physics TI - Edge universality for deformed Wigner matrices VL - 27 ER - TY - JOUR AU - Lemoult, Grégoire M AU - Maier, Philipp AU - Hof, Björn ID - 1679 IS - 9 JF - Physics of Fluids TI - Taylor's Forest VL - 27 ER - TY - JOUR AB - Many species groups, including mammals and many insects, determine sex using heteromorphic sex chromosomes. Diptera flies, which include the model Drosophila melanogaster, generally have XY sex chromosomes and a conserved karyotype consisting of six chromosomal arms (five large rods and a small dot), but superficially similar karyotypes may conceal the true extent of sex chromosome variation. Here, we use whole-genome analysis in 37 fly species belonging to 22 different families of Diptera and uncover tremendous hidden diversity in sex chromosome karyotypes among flies. We identify over a dozen different sex chromosome configurations, and the small dot chromosome is repeatedly used as the sex chromosome, which presumably reflects the ancestral karyotype of higher Diptera. However, we identify species with undifferentiated sex chromosomes, others in which a different chromosome replaced the dot as a sex chromosome or in which up to three chromosomal elements became incorporated into the sex chromosomes, and others yet with female heterogamety (ZW sex chromosomes). Transcriptome analysis shows that dosage compensation has evolved multiple times in flies, consistently through up-regulation of the single X in males. However, X chromosomes generally show a deficiency of genes with male-biased expression, possibly reflecting sex-specific selective pressures. These species thus provide a rich resource to study sex chromosome biology in a comparative manner and show that similar selective forces have shaped the unique evolution of sex chromosomes in diverse fly taxa. AU - Vicoso, Beatriz AU - Bachtrog, Doris ID - 1684 IS - 4 JF - PLoS Biology TI - Numerous transitions of sex chromosomes in Diptera VL - 13 ER - TY - JOUR AB - Guided cell movement is essential for development and integrity of animals and crucially involved in cellular immune responses. Leukocytes are professional migratory cells that can navigate through most types of tissues and sense a wide range of directional cues. The responses of these cells to attractants have been mainly explored in tissue culture settings. How leukocytes make directional decisions in situ, within the challenging environment of a tissue maze, is less understood. Here we review recent advances in how leukocytes sense chemical cues in complex tissue settings and make links with paradigms of directed migration in development and Dictyostelium discoideum amoebae. AU - Sarris, Milka AU - Sixt, Michael K ID - 1687 IS - 10 JF - Current Opinion in Cell Biology TI - Navigating in tissue mazes: Chemoattractant interpretation in complex environments VL - 36 ER - TY - CONF AB - Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3. Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest. AU - Cohen Addad, Vincent AU - De Mesmay, Arnaud N ID - 1685 TI - A fixed parameter tractable approximation scheme for the optimal cut graph of a surface VL - 9294 ER -