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 - GEN AB - In this poster, we present methods for randomly generating hybrid automata with affine differential equations, invariants, guards, and assignments. Selecting an arbitrary affine function from the set of all affine functions results in a low likelihood of generating hybrid automata with diverse and interesting behaviors, as there are an uncountable number of elements in the set of all affine functions. Instead, we partition the set of all affine functions into potentially interesting classes and randomly select elements from these classes. For example, we partition the set of all affine differential equations by using restrictions on eigenvalues such as those that yield stable, unstable, etc. equilibrium points. We partition the components describing discrete behavior (guards, assignments, and invariants) to allow either time-dependent or state-dependent switching, and in particular provide the ability to generate subclasses of piecewise-affine hybrid automata. Our preliminary experimental results with a prototype tool called HyRG (Hybrid Random Generator) illustrate the feasibility of this generation method to automatically create standard hybrid automaton examples like the bouncing ball and thermostat. AU - Nguyen, Luan V AU - Christian Schilling AU - Sergiy Bogomolov AU - Johnson, Taylor T ID - 1500 T2 - HSCC: Hybrid Systems - Computation and Control TI - Poster: HyRG: A random generation tool for affine hybrid automata 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 - Type 1 metabotropic glutamate (mGlu1) receptors play a pivotal role in different forms of synaptic plasticity in the cerebellar cortex, e.g. long-term depression at glutamatergic synapses and rebound potentiation at GABAergic synapses. These various forms of plasticity might depend on the subsynaptic arrangement of the receptor in Purkinje cells that can be regulated by protein-protein interactions. This study investigated, by means of the freeze-fracture replica immunogold labelling method, the subcellular localization of mGlu1 receptors in the rodent cerebellum and whether Homer proteins regulate their subsynaptic distribution. We observed a widespread extrasynaptic localization of mGlu1 receptors and confirmed their peri-synaptic enrichment at glutamatergic synapses. Conversely, we detected mGlu1 receptors within the main body of GABAergic synapses onto Purkinje cell dendrites. Although Homer proteins are known to interact with the mGlu1 receptor C-terminus, we could not detect Homer3, the most abundant Homer protein in the cerebellar cortex, at GABAergic synapses by pre-embedding and post-embedding immunoelectron microscopy. We then hypothesized a critical role for Homer proteins in the peri-junctional localization of mGlu1 receptors at glutamatergic synapses. To disrupt Homer-associated protein complexes, mice were tail-vein injected with the membrane-permeable dominant-negative TAT-Homer1a. Freeze-fracture replica immunogold labelling analysis showed no significant alteration in the mGlu1 receptor distribution pattern at parallel fibre-Purkinje cell synapses, suggesting that other scaffolding proteins are involved in the peri-synaptic confinement. The identification of interactors that regulate the subsynaptic localization of the mGlu1 receptor at neurochemically distinct synapses may offer new insight into its trafficking and intracellular signalling. AU - Mansouri, Mahnaz AU - Kasugai, Yu AU - Fukazawa, Yugo AU - Bertaso, Federica AU - Raynaud, Fabrice AU - Perroy, Julie AU - Fagni, Laurent AU - Walter Kaufmann AU - Watanabe, Masahiko AU - Ryuichi Shigemoto AU - Ferraguti, Francesco ID - 1515 IS - 2 JF - European Journal of Neuroscience TI - Distinct subsynaptic localization of type 1 metabotropic glutamate receptors at glutamatergic and GABAergic synapses in the rodent cerebellar cortex VL - 41 ER - TY - JOUR AB - Endocannabinoids (eCBs) play key roles in brain function, acting as modulatory signals in synaptic transmission and plasticity. They are recognized as retrograde messengers that mediate long-term synaptic depression (LTD), but their ability to induce long-term potentiation (LTP) is poorly known. We show that eCBs induce the long-term enhancement of transmitter release at single hippocampal synapses through stimulation of astrocytes when coincident with postsynaptic activity. This LTP requires the coordinated activity of the 3 elements of the tripartite synapse: 1) eCB-evoked astrocyte calcium signal that stimulates glutamate release; 2) postsynaptic nitric oxide production; and 3) activation of protein kinase C and presynaptic group I metabotropic glutamate receptors, whose location at presynaptic sites was confirmed by immunoelectron microscopy. Hence, while eCBs act as retrograde signals to depress homoneuronal synapses, they serve as lateral messengers to induce LTP in distant heteroneuronal synapses through stimulation of astrocytes. Therefore, eCBs can trigger LTP through stimulation of astrocyte-neuron signaling, revealing novel cellular mechanisms of eCB effects on synaptic plasticity. AU - Gómez-Gonzalo, Marta AU - Navarrete, Marta AU - Perea, Gertrudis AU - Covelo, Ana AU - Martín-Fernández, Mario AU - Ryuichi Shigemoto AU - Luján, Rafael AU - Araque, Alfonso ID - 1514 IS - 10 JF - Cerebral Cortex TI - Endocannabinoids induce lateral long term potentiation of transmitter release by stimulation of gliotransmission VL - 25 ER -