More Like this

1. Evolvability and Macroevolution: Overview and Synthesis

   https://doi.org/10.1007/s11692-022-09570-4  

   Jablonski, David (September 2022, Evolutionary Biology)

   Abstract Evolvability is best addressed from a multi-level, macroevolutionary perspective through a comparative approach that tests for among-clade differences in phenotypic diversification in response to an opportunity, such as encountered after a mass extinction, entering a new adaptive zone, or entering a new geographic area. Analyzing the dynamics of clades under similar environmental conditions can (partially) factor out shared external drivers to recognize intrinsic differences in evolvability, aiming for a macroevolutionary analog of a common-garden experiment. Analyses will be most powerful when integrating neontological and paleontological data: determining differences among extant populations that can be hypothesized to generate large-scale, long-term contrasts in evolvability among clades; or observing large-scale differences among clade histories that can by hypothesized to reflect contrasts in genetics and development observed directly in extant populations. However, many comparative analyses can be informative on their own, as explored in this overview. Differences in clade-level evolvability can be visualized in diversity-disparity plots, which can quantify positive and negative departures of phenotypic productivity from stochastic expectations scaled to taxonomic diversification. Factors that evidently can promote evolvability include modularity—when selection aligns with modular structure or with morphological integration patterns; pronounced ontogenetic changes in morphology, as in allometry or multiphase life cycles; genome size; and a variety of evolutionary novelties, which can also be evaluated using macroevolutionary lags between the acquisition of a trait and phenotypic diversification, and dead-clade-walking patterns that may signal a loss of evolvability when extrinsic factors can be excluded. High speciation rates may indirectly foster phenotypic evolvability, and vice versa. Mechanisms are controversial, but clade evolvability may be higher in the Cambrian, and possibly early in the history of clades at other times; in the tropics; and, for marine organisms, in shallow-water disturbed habitats. 

   more » « less
2. AND testing and robust judgement aggregation

   https://doi.org/10.1145/3357713.3384254  

   Filmus, Y; Lifshitz, N; Minzer, D; Mossel, E. (June 2020, STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing)

   A function f∶{0,1}n→ {0,1} is called an approximate AND-homomorphism if choosing x,y∈n uniformly at random, we have that f(x∧ y) = f(x)∧ f(y) with probability at least 1−ε, where x∧ y = (x1∧ y1,…,xn∧ yn). We prove that if f∶ {0,1}n → {0,1} is an approximate AND-homomorphism, then f is δ-close to either a constant function or an AND function, where δ(ε) → 0 as ε→ 0. This improves on a result of Nehama, who proved a similar statement in which δ depends on n. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is ε-close to satisfying judgement aggregation, then it is δ(ε)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama’s result, in which δ decays polynomially with n. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation f = λ g, where is the downwards noise operator f(x) = y[f(x ∧ y)], f is [0,1]-valued, and g is {0,1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which f and λ g are close is close to an exact solution. 

   more » « less
3. Blockchains and Databases: Opportunities and Challenges for the Permissioned and the Permissionless

   https://doi.org/10.1007/978-3-030-54832-2_1  

   Agrawal, D.; El Abbadi, A.; Amiri, M.J.; Maiyya, S.; Zakhary, V. (August 2020, Advances in Databases and Information Systems)

   Darmont, J; Novikov, B.; Wrembel, R. (Ed.)

   Bitcoin [12] is a successful and interesting example of a global scale peer-to-peer cryptocurrency that integrates many techniques and protocols from cryptography, distributed systems, and databases. The main underlying data structure is blockchain, a scalable fully replicated structure that is shared among all participants and guarantees a consistent view of all user transactions by all participants in the system. In a blockchain, nodes agree on their shared states across a large network of untrusted participants. Although originally devised for cryptocurrencies, recent systems exploit its many unique features such as transparency, provenance, fault tolerance, and authenticity to support a wide range of distributed applications. Bitcoin and other cryptocurrencies use permissionless blockchains. In a permissionless blockchain, the network is public, and anyone can participate without a specific identity. Many other distributed applications, such as supply chain management and healthcare, are deployed on permissioned blockchains consisting of a set of known, identified nodes that still might not fully trust each other. This paper illustrates some of the main challenges and opportunities from a database perspective in the many novel and interesting application domains of blockchains. These opportunities are illustrated using various examples from recent research in both permissionless and permissioned blockchains. Two main themes unite the various examples: (1) the important role of distribution and consensus in managing large scale systems and (2) the need to tolerate malicious failures. The advent of cloud computing and large data centers shifted large scale data management infrastructures from centralized databases to distributed systems. One of the main challenges in designing distributed systems is the need for fault-tolerance. Cloud-based systems typically assume trusted infrastructures, since data centers are owned by the enterprises managing the data, and hence the design typically only assumes and tolerates crash failures. The advent of blockchain and the underlying premise that copies of the blockchain are distributed among untrusted entities has shifted the focus of fault-tolerance from tolerating crash failures to tolerating malicious failures. These interesting and challenging settings pose great opportunities for database researchers. 

   more » « less
4. Log-rank and lifting for AND-functions

   https://doi.org/10.1145/3406325.3450999  

   Knop, Alexander; Lovett, Shachar; McGuire, Sam; Yuan, Weiqiang (June 2021, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing)

   Let f: {0, 1}n → {0, 1} be a boolean function, and let f∧(x, y) = f(x ∧ y) denote the AND-function of f, where x ∧ y denotes bit-wise AND. We study the deterministic communication complexity of f∧ and show that, up to a logn factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f∧. This comes within a logn factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F2-degree. Our techniques can also be used to prove (within a logn factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f∧ is polynomially related to the AND-decision tree complexity of f. The results rely on a new structural result regarding boolean functions f: {0, 1}n → {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f: {0, 1}n → with a larger range. 

   more » « less
5. Tooth and consequences: Heterodonty and dental replacement in piranhas and pacus (Serrasalmidae)

   https://doi.org/10.1111/ede.12306  

   Kolmann, Matthew A.; Cohen, Karly E.; Bemis, Katherine E.; Summers, Adam P.; Irish, Frances J.; Hernandez, L. Patricia (August 2019, Evolution & Development)

   Abstract Tooth replacement in piranhas is unusual: all teeth on one side of the head are lost as a unit, then replaced simultaneously. We used histology and microCT to examine tooth‐replacement modes across carnivorous piranhas and their herbivorous pacu cousins (Serrasalmidae) and then mapped replacement patterns onto a molecular phylogeny. Pacu teeth develop and are replaced in a manner like piranhas. For serrasalmids, unilateral tooth replacement is not an “all or nothing” phenomenon; we demonstrate that both sides of the jaws have developing tooth rows within them, albeit with one side more mineralized than the other. All serrasalmids (except one) share unilateral tooth replacement, so this is not an adaptation for carnivory. All serrasalmids have interlocking teeth; piranhas interdigitate lateral tooth cusps with adjacent teeth, forming a singular saw‐like blade, whereas lateral cusps in pacus clasp together. For serrasalmids to have an interlocking dentition, their teeth need to develop and erupt at the same time. We propose that interlocking mechanisms prevent tooth loss and ensure continued functionality of the feeding apparatus. Serrasalmid dentitions are ubiquitously heterodont, having incisiform and molariform dentitions reminiscent of mammals. Finally, we propose that simultaneous tooth replacement be considered as a synapomorphy for the family. 

   more » « less