TY - JOUR
AB - We consider sample covariance matrices of the form Q = ( σ1/2X)(σ1/2X)∗, where the sample X is an M ×N random matrix whose entries are real independent random variables with variance 1/N and whereσ is an M × M positive-definite deterministic matrix. We analyze the asymptotic fluctuations of the largest rescaled eigenvalue of Q when both M and N tend to infinity with N/M →d ϵ (0,∞). For a large class of populations σ in the sub-critical regime, we show that the distribution of the largest rescaled eigenvalue of Q is given by the type-1 Tracy-Widom distribution under the additional assumptions that (1) either the entries of X are i.i.d. Gaussians or (2) that σ is diagonal and that the entries of X have a sub-exponential decay.
AU - Lee, Ji
AU - Schnelli, Kevin
ID - 1157
IS - 6
JF - Annals of Applied Probability
TI - Tracy-widom distribution for the largest eigenvalue of real sample covariance matrices with general population
VL - 26
ER -
TY - JOUR
AB - Speciation results from the progressive accumulation of mutations that decrease the probability of mating between parental populations or reduce the fitness of hybrids—the so-called species barriers. The speciation genomic literature, however, is mainly a collection of case studies, each with its own approach and specificities, such that a global view of the gradual process of evolution from one to two species is currently lacking. Of primary importance is the prevalence of gene flow between diverging entities, which is central in most species concepts and has been widely discussed in recent years. Here, we explore the continuum of speciation thanks to a comparative analysis of genomic data from 61 pairs of populations/species of animals with variable levels of divergence. Gene flow between diverging gene pools is assessed under an approximate Bayesian computation (ABC) framework. We show that the intermediate "grey zone" of speciation, in which taxonomy is often controversial, spans from 0.5% to 2% of net synonymous divergence, irrespective of species life history traits or ecology. Thanks to appropriate modeling of among-locus variation in genetic drift and introgression rate, we clarify the status of the majority of ambiguous cases and uncover a number of cryptic species. Our analysis also reveals the high incidence in animals of semi-isolated species (when some but not all loci are affected by barriers to gene flow) and highlights the intrinsic difficulty, both statistical and conceptual, of delineating species in the grey zone of speciation.
AU - Roux, Camille
AU - Fraisse, Christelle
AU - Romiguier, Jonathan
AU - Anciaux, Youann
AU - Galtier, Nicolas
AU - Bierne, Nicolas
ID - 1158
IS - 12
JF - PLoS Biology
TI - Shedding light on the grey zone of speciation along a continuum of genomic divergence
VL - 14
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. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.
AU - Fulek, Radoslav
AU - Pelsmajer, Michael
AU - Schaefer, Marcus
ID - 1164
TI - Hanani-Tutte for radial planarity II
VL - 9801
ER -
TY - CONF
AB - We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.
AU - Fulek, Radoslav
ID - 1165
TI - C-planarity of embedded cyclic c-graphs
VL - 9801
ER -
TY - JOUR
AB - Evolutionary pathways describe trajectories of biological evolution in the space of different variants of organisms (genotypes). The probability of existence and the number of evolutionary pathways that lead from a given genotype to a better-adapted genotype are important measures of accessibility of local fitness optima and the reproducibility of evolution. Both quantities have been studied in simple mathematical models where genotypes are represented as binary sequences of two types of basic units, and the network of permitted mutations between the genotypes is a hypercube graph. However, it is unclear how these results translate to the biologically relevant case in which genotypes are represented by sequences of more than two units, for example four nucleotides (DNA) or 20 amino acids (proteins), and the mutational graph is not the hypercube. Here we investigate accessibility of the best-adapted genotype in the general case of K > 2 units. Using computer generated and experimental fitness landscapes we show that accessibility of the global fitness maximum increases with K and can be much higher than for binary sequences. The increase in accessibility comes from the increase in the number of indirect trajectories exploited by evolution for higher K. As one of the consequences, the fraction of genotypes that are accessible increases by three orders of magnitude when the number of units K increases from 2 to 16 for landscapes of size N ∼ 106genotypes. This suggests that evolution can follow many different trajectories on such landscapes and the reconstruction of evolutionary pathways from experimental data might be an extremely difficult task.
AU - Zagórski, Marcin P
AU - Burda, Zdzisław
AU - Wacław, Bartłomiej
ID - 1167
IS - 12
JF - PLoS Computational Biology
TI - Beyond the hypercube evolutionary accessibility of fitness landscapes with realistic mutational networks
VL - 12
ER -
TY - JOUR
AB - A central issue in cell biology is the physico-chemical basis of organelle biogenesis in intracellular trafficking pathways, its most impressive manifestation being the biogenesis of Golgi cisternae. At a basic level, such morphologically and chemically distinct compartments should arise from an interplay between the molecular transport and chemical maturation. Here, we formulate analytically tractable, minimalist models, that incorporate this interplay between transport and chemical progression in physical space, and explore the conditions for de novo biogenesis of distinct cisternae. We propose new quantitative measures that can discriminate between the various models of transport in a qualitative manner-this includes measures of the dynamics in steady state and the dynamical response to perturbations of the kind amenable to live-cell imaging.
AU - Sachdeva, Himani
AU - Barma, Mustansir
AU - Rao, Madan
ID - 1172
JF - Scientific Reports
TI - Nonequilibrium description of de novo biogenesis and transport through Golgi-like cisternae
VL - 6
ER -
TY - JOUR
AB - Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of (Formula presented.) , where (Formula presented.) denotes the upper bound on the underlying random oracle calls and (Formula presented.) , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of ‘dependence’ and ‘independence’ conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of (Formula presented.). By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.
AU - Kamath Hosdurg, Chethan
AU - Chatterjee, Sanjit
ID - 1177
IS - 4
JF - Algorithmica
TI - A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound
VL - 74
ER -
TY - CONF
AB - Computational notions of entropy have recently found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The two main types of results which make computational notions so useful are (1) Chain rules, which quantify by how much the computational entropy of a variable decreases if conditioned on some other variable (2) Transformations, which quantify to which extend one type of entropy implies another.
Such chain rules and transformations typically lose a significant amount in quality of the entropy, and are the reason why applying these results one gets rather weak quantitative security bounds. In this paper we for the first time prove lower bounds in this context, showing that existing results for transformations are, unfortunately, basically optimal for non-adaptive black-box reductions (and it’s hard to imagine how non black-box reductions or adaptivity could be useful here.)
A variable X has k bits of HILL entropy of quality (ϵ,s)
if there exists a variable Y with k bits min-entropy which cannot be distinguished from X with advantage ϵ
by distinguishing circuits of size s. A weaker notion is Metric entropy, where we switch quantifiers, and only require that for every distinguisher of size s, such a Y exists.
We first describe our result concerning transformations. By definition, HILL implies Metric without any loss in quality. Metric entropy often comes up in applications, but must be transformed to HILL for meaningful security guarantees. The best known result states that if a variable X has k bits of Metric entropy of quality (ϵ,s)
, then it has k bits of HILL with quality (2ϵ,s⋅ϵ2). We show that this loss of a factor Ω(ϵ−2)
in circuit size is necessary. In fact, we show the stronger result that this loss is already necessary when transforming so called deterministic real valued Metric entropy to randomised boolean Metric (both these variants of Metric entropy are implied by HILL without loss in quality).
The chain rule for HILL entropy states that if X has k bits of HILL entropy of quality (ϵ,s)
, then for any variable Z of length m, X conditioned on Z has k−m bits of HILL entropy with quality (ϵ,s⋅ϵ2/2m). We show that a loss of Ω(2m/ϵ) in circuit size necessary here. Note that this still leaves a gap of ϵ between the known bound and our lower bound.
AU - Pietrzak, Krzysztof Z
AU - Maciej, Skorski
ID - 1179
TI - Pseudoentropy: Lower-bounds for chain rules and transformations
VL - 9985
ER -
TY - CONF
AB - Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decisionmaking and elections. The traditional computational question, that asks to compute a draw (optimal draw) that maximizes the winning probability for a distinguished player, has received a lot of attention. Previous works consider the problem where the pairwise winning probabilities are known precisely, while we study how robust is the winning probability with respect to small errors in the pairwise winning probabilities. First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Tkadlec, Josef
ID - 1182
TI - Robust draws in balanced knockout tournaments
VL - 2016-January
ER -
TY - JOUR
AB - Across multicellular organisms, the costs of reproduction and self-maintenance result in a life history trade-off between fecundity and longevity. Queens of perennial social Hymenoptera are both highly fertile and long-lived, and thus, this fundamental trade-off is lacking. Whether social insect males similarly evade the fecundity/longevity trade-off remains largely unstudied. Wingless males of the ant genus Cardiocondyla stay in their natal colonies throughout their relatively long lives and mate with multiple female sexuals. Here, we show that Cardiocondyla obscurior males that were allowed to mate with large numbers of female sexuals had a shortened life span compared to males that mated at a low frequency or virgin males. Although frequent mating negatively affects longevity, males clearly benefit from a “live fast, die young strategy” by inseminating as many female sexuals as possible at a cost to their own survival.
AU - Metzler, Sina
AU - Heinze, Jürgen
AU - Schrempf, Alexandra
ID - 1184
IS - 24
JF - Ecology and Evolution
TI - Mating and longevity in ant males
VL - 6
ER -