A Short History of Computational Complexity

National Science Foundation (CCR-998310); Army Research Office (DAAD19-02-1-0058)

On the Complexity of Quantum ACC

For any q > 1, let MOD_q be a quantum gate that determines if the number of 1's in the input is divisible by q. We show that for any q,t > 1, MOD_q is equivalent to MOD_t (up to constant depth). Based on the case q=2, Moore has shown that quantum analogs of AC^(0), ACC[q], and ACC, denoted QAC^(0)_wf, QACC[2], QACC respectively, define the same class of operators, leaving q > 2 as an open question. Our result resolves this question, implying that QAC^(0)_wf = QACC[q] = QACC for all q. We also prove the first upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC (both for arbitrary complex amplitudes) and BQACC (for rational number amplitudes) and show that they are all contained in TC^(0). To do this, we show that a TC^(0) circuit can keep track of the amplitudes of the state resulting from the application of a QACC operator using a constant width polynomial size tensor sum. In order to accomplish this, we also show that TC^(0) can perform iterated addition and multiplication in certain field extensions.

The importance of interaction strength for food web dynamics and ecosystem functioning

Global biodiversity is eroding at an alarming rate, through a combination of anthropogenic disturbance and environmental change. Ecological communities are bewildering in their complexity. Experimental ecologists strive to understand the mechanisms that drive the stability and structure of these complex communities in a bid to inform nature conservation and management. Two fields of research have had high profile success at developing theories related to these stabilising structures and testing them through controlled experimentation. Biodiversity-ecosystem functioning (BEF) research has explored the likely consequences of biodiversity loss on the functioning of natural systems and the provision of important ecosystem services. Empirical tests of BEF theory often consist of simplified laboratory and field experiments, carried out on subsets of ecological communities. Such experiments often overlook key information relating to patterns of interactions, important relationships, and fundamental ecosystem properties. The study of multi-species predator-prey interactions has also contributed much to our understanding of how complex systems are structured, particularly through the importance of indirect effects and predator suppression of prey populations. A growing number of studies describe these complex interactions in detailed food webs, which encompass all the interactions in a community. This has led to recent calls for an integration of BEF research with the comprehensive study of food web properties and patterns, to help elucidate the mechanisms that allow complex communities to persist in nature. This thesis adopts such an approach, through experimentation at Lough Hyne marine reserve, in southwest Ireland. Complex communities were allowed to develop naturally in exclusion cages, with only the diversity of top trophic levels controlled. Species removals were carried out and the resulting changes to predator-prey interactions, ecosystem functioning, food web properties, and stability were studied in detail. The findings of these experiments contribute greatly to our understanding of the stability and structure of complex natural communities.

The politics of hazard: imminent critique and deconstruction of ecological modernisation in Ireland

This dissertation sets out to provide immanent critique and deconstruction of ecological modernisation or ecomodernism.It does so, from a critical social theory approach, in order to correctly address the essential issues at the heart of the environmental crisis that ecomodernism purports to address. This critical approach argues that the solution to the environmental crisis can only be concretely achieved by recognising its root cause as being foremost the issue of material interaction between classes in society, and not simply between society and nature in any structurally meaningful way. Based on a metaphysic of false dualism, ecological modernisation attributes a materiality of exchange value relations to issues of society, while simultaneously offering a non- material ontology to issues of nature. Thus ecomodernism serves asymmetrical relations of power whereby, as a polysemic policy discourse, it serves the material interests of those who have the power to impose abstract interpretations on the materiality of actual phenomena. The research of this dissertation is conducted by the critical evaluation of the empirical data from two exemplary Irish case studies. Discovery of the causal processes of the various public issues in the case studies and thereafter the revelation of the meaning structures under- pinning such causal processes, is a theoretically- driven task requiring analysis of those social practices found in the cognitive, cultural and structural constitutions respectively of actors, mediations and systems.Therefore, the imminent critique of the case study paradigms serves as a research strategy for comprehending Ireland’s nature- society relations as influenced essentially by a systems (techno- corporatist) ecomodernist discourse. Moreover, the deconstruction of this systems ideological discourse serves not only to demonstrate how weak ecomodernism practically undermines its declared ecological objectives, but also indicates how such objectives intervene as systemic contradictions at the cultural heart of Ireland’s late modernisation.

From respect for nature to agency as realisation in response to the ecological emergency

'The ecological emergency’ describes both our emergence into, and the way we relate within, a set of globally urgent circumstances, brought about through anthropogenic impact. I identify two phases to this emergency. Firstly, there is the anthropogenic impact itself, interpreted through various conceptual models. Secondly, however, is the increasingly entrenched commitment to divergent conceptual positions, that leads to a growing disparateness in attitudes, and a concurrent difficulty with finding any grounds for convergence in response. I begin by reviewing the environmental ethics literature in order to clarify which components of the implicit narratives and beliefs of different positions create the foundations for such disparateness of views. I identify the conceptual frameworks through which moral agency and human responsibility are viewed, and that justify an ethical response to the ecological emergency. In particular, I focus on Paul Taylor's thesis of 'respect for nature' as a framework for revising both the idea that we are ‘moral’ and the idea that we are ‘agents’ in this unique way, and I open to question the idea that any response to the ecological emergency need be couched in ethical terms. This revision leads me to formulate an alternative conceptual model that makes use of Timothy Morton’s idea of enmeshment. I propose that we dramatically revise our idea of moral agency using the idea of enmeshment as a starting point. I develop an alternative framework that locates our capacity for responsibility within our capacity for realisation, both in the sense of understanding, and of making real, sets of conditions within our enmeshment. I draw parallels between this idea of ‘realisation as agency’ and the work of Dōgen and other non-dualists. I then propose a revised understanding of ‘the good’ of systems from a biophysical perspective, and compare this with certain features of Asian traditions of thought. I consider the practical implications of these revisions, and I conclude that the act of paying close attention, or realising, contains our agency, as does the attitude, or manner, with which we focus. This gives us the basis for a convergent response to the ecological emergency: the way of our engagement that is the key to responding to the ecological emergency

Study abroad and complexity, accuracy and fluency (CAF) development: a longitudinal investigation of French and Chinese Learners of L2 English

This longitudinal study tracked third-level French (n=10) and Chinese (n=7) learners of English as a second language (L2) during an eight-month study abroad (SA) period at an Irish university. The investigation sought to determine whether there was a significant relationship between length of stay (LoS) abroad and gains in the learners' oral complexity, accuracy and fluency (CAF), what the relationship was between these three language constructs and whether the two learner groups would experience similar paths to development. Additionally, the study also investigated whether specific reported out-of-class contact with the L2 was implicated in oral CAF gains. Oral data were collected at three equidistant time points; at the beginning of SA (T1), midway through the SA sojourn (T2) and at the end (T3), allowing for a comparison of CAF gains arising during one semester abroad to those arising during a subsequent semester. Data were collected using Sociolinguistic Interviews (Labov, 1984) and adapted versions of the Language Contact Profile (Freed et al., 2004). Overall, the results point to LoS abroad as a highly influential variable in gains to be expected in oral CAF during SA. While one semester in the TL country was not enough to foster statistically significant improvement in any of the CAF measures employed, significant improvement was found during the second semester of SA. Significant differences were also revealed between the two learner groups. Finally, significant correlations, some positive, some negative, were found between gains in CAF and specific usage of the L2. All in all, the disaggregation of the group data clearly illustrates, in line with other recent enquiries (e.g. Wright and Cong, 2014) that each individual learner's path to CAF development was unique and highly individualised, thus providing strong evidence for the recent claim that SLA is "an individualized nonlinear endeavor" (Polat and Kim, 2014: 186).

Mapping the complexity of transcription control in higher eukaryotes.

Recent genomic analyses suggest the importance of combinatorial regulation by broadly expressed transcription factors rather than expression domains characterized by highly specific factors.

Geography and Genetics of Ecological Speciation in Pea Aphids

During ecological speciation, divergent natural selection drives evolution of ecological specialization and genetic differentiation of populations on alternate environments. Populations diverging onto the same alternate environments may be geographically widespread, so that divergence may occur at an array of locations simultaneously. Spatial variation in the process of divergence may produce a pattern of differences in divergence among locations called the Geographic Mosaic of Divergence. Diverging populations may vary in their degree of genetic differentiation and ecological specialization among locations. My dissertation examines the pattern and evolutionary processes of divergence in pea aphids (Acyrthosiphon pisum) on alfalfa (Medicago sativa) and clover (Trifolium pretense). In Chapter One, I examined differences among North American aphid populations in genetic differentiation at nuclear, sequence-based markers and in ecological specialization, measured as aphid fecundity on each host plant. In the East, aphids showed high host-plant associated ecological specialization and high genetic differentiation. In the West, aphids from clover were genetically indistinguishable from aphids on alfalfa, and aphids from clover were less specialized. Thus, the pattern of divergence differed among locations, suggesting a Geographic Mosaic of Divergence. In Chapter Two, I examined genomic heterogeneity in divergence in aphids on alfalfa and clover across North America using amplified fragment length polymorphisms (AFLPs). The degree of genetic differentiation varied greatly among markers, suggesting that divergent natural selection drives aphid divergence in all geographic locations. Three of the same genetic markers were identified as evolving under divergent selection in the eastern and western regions, and additional divergent markers were identified in the East. In Chapter Three, I investigated population structure of aphids in North America, France, and Sweden using AFLPs. Aphids on the same host plant were genetically similar across many parts of their range, so the evolution of host plant specialization does not appear to have occurred independently in every location. While aphids on alfalfa and clover were genetically differentiated in most locations, aphids from alfalfa and clover were genetically similar in both western North America and Sweden. High gene flow from alfalfa onto clover may constrain divergence in these locations.

Bioenergetic and ecological consequences of diet variability in Atlantic croaker Micropogonias undulatus

Atlantic croaker Micropogonias undulatus is a commercially and ecologically important bottom-associated fish that occurs in marine and estuarine systems from Cape Cod, MA to Mexico. I documented the temporal and spatial variability in the diet of Atlantic croaker in Chesapeake Bay and found that in the summer fish, particularly bay anchovies Anchoa mitchilli, make up at least 20% of the diet of croaker by weight. The use of a pelagic food source seems unusual for a bottom-associated fish such as croaker, but appears to be a crepuscular feeding habit that has not been previously detected. Thus, I investigated the bioenergetic consequences of secondary piscivory to the distribution of croaker, to the condition of individuals within the population and to the ecosystem. Generalized additive models revealed that the biomass of anchovy explained some of the variability in croaker occurrence and abundance in Chesapeake Bay. However, physical factors, specifically temperature, salinity, and seasonal dynamics were stronger determinants of croaker distribution than potential prey availability. To better understand the bioenergetic consequences of diet variability at the individual level, I tested the hypothesis that croaker feeding on anchovies would be in better condition than those feeding on polychaetes using a variety of condition measures that operate on multiple time scales, including RNA:DNA, Fulton's condition factor (K), relative weight (Wr), energy density, hepatosomatic index (HSI), and gonadosomatic index (GSI). Of these condition measures, several morphometric measures were significantly positively correlated with each other and with the percentage (by weight) of anchovy in croaker diets, suggesting that the type of prey eaten is important in improving the overall condition of individual croaker. To estimate the bioenergetic consequences of diet variability on growth and consumption in croaker, I developed and validated a bioenergetic model for Atlantic croaker in the laboratory. The application of this model suggested that croaker could be an important competitor with weakfish and striped bass for food resources during the spring and summer when population abundances of these three fishes are high in Chesapeake Bay. Even though anchovies made up a relatively small portion of croaker diet and only at certain times of the year, croaker consumed more anchovy at the population level than striped bass in all simulated years and nearly as much anchovy as weakfish. This indicates that weak trophic interactions between species are important in understanding ecosystem processes and should be considered in ecosystem-based management.

Relative growth of the limbs and trunk in sifakas: heterochronic, ecological, and functional considerations.

Limb, trunk, and body weight measurements were obtained for growth series of Milne-Edwards's diademed sifaka, Propithecus diadema edwardsi, and the golden-crowned sifaka, Propithecus tattersalli. Similar measures were obtained also for primarily adults of two subspecies of the western sifaka: Propithecus verreauxi coquereli, Coquerel's sifaka, and Propithecus verreauxi verreauxi, Verreaux's sifaka. Ontogenetic series for the larger-bodied P. d. edwardsi and the smaller-bodied P. tattersalli were compared to evaluate whether species-level differences in body proportions result from the differential extension of common patterns of relative growth. In bivariate plots, both subspecies of P. verreauxi were included to examine whether these taxa also lie along a growth trajectory common to all sifakas. Analyses of the data indicate that postcranial proportions for sifakas are ontogenetically scaled, much as demonstrated previously with cranial dimensions for all three species (Ravosa, 1992). As such, P. d. edwardsi apparently develops larger overall size primarily by growing at a faster rate, but not for a longer duration of time, than P. tattersalli and P. verreauxi; this is similar to results based on cranial data. A consideration of Malagasy lemur ecology suggests that regional differences in forage quality and resource availability have strongly influenced the evolutionary development of body-size variation in sifakas. On one hand, the rainforest environment of P. d. edwardsi imposes greater selective pressures for larger body size than the dry-forest environment of P. tattersalli and P. v. coquereli, or the semi-arid climate of P. v. verreauxi. On the other hand, as progressively smaller-bodied adult sifakas are located in the east, west, and northwest, this apparently supports suggestions that adult body size is set by dry-season constraints on food quality and distribution (i.e., smaller taxa are located in more seasonal habitats such as the west and northeast). Moreover, the fact that body-size differentiation occurs primarily via differences in growth rate is also due apparently to differences in resource seasonality (and juvenile mortality risk in turn) between the eastern rainforest and the more temperate northeast and west. Most scaling coefficients for both arm and leg growth range from slight negative allometry to slight positive allometry. Given the low intermembral index for sifakas, which is also an adaptation for propulsive hindlimb-dominated jumping, this suggests that differences in adult limb proportions are largely set prenatally rather than being achieved via higher rates of postnatal hindlimb growth.(ABSTRACT TRUNCATED AT 400 WORDS)

Biological and ecological mechanisms supporting marine self-governance: The Seri Callo de Hacha Fishery in Mexico

My goal was to describe how biological and ecological factors give shape to fishing practices that can contribute to the successful self-governance of a small-scale fishing system in the Gulf of California, Mexico. The analysis was based on a comparison of the main ecological and biological indicators that fishers claim to use to govern their day-to-day decision making about fishing and data collected in situ. I found that certain indicators allow fishers to learn about differences and characteristics of the resource system and its units. Fishers use such information to guide their day-to-day fishing decisions. More importantly, these decisions appear unable to shape the reproductive viability of the fishery because no indicators were correlated to the reproductive cycle of the target species. As a result, the fishing practices constitute a number of mechanisms that might provide short-term buffering capacity against perturbations or stress factors that otherwise would threaten the overall sustainability and self-governance of the system. The particular biological circumstances that shape the harvesting practices might also act as a precursor of self-governance because they provide fishers with enough incentives to meet the costs of organizing the necessary rule structure that underlies a successful self-governance system.

Institutional and ecological interplay for successful self-governance of community-based fisheries

The goal of this paper is to improve our understanding of the role of institutional arrangements and ecological factors that facilitate the emergence and sustainability of successful collective action in small-scale fishing social-ecological systems. Using a modified logistic growth function, we simulate how ecological factors (i.e. carrying capacity) affect small-scale fishing communities with varying degrees of institutional development (i.e. timeliness to adopt new institutions and the degree to which harvesting effort is reduced), in their ability to avoid overexploitation. Our results show that strong and timely institutions are necessary but not sufficient to maintain sustainable harvests over time. The sooner communities adopt institutions, and the stronger the institutions they adopt, the more likely they are to sustain the resource stock. Exactly how timely the institutions must be adopted, and by what amount harvesting effort must be diminished, depends on the ecological carrying capacity of the species at the particular location. Small differences in the carrying capacity between fishing sites, even under scenarios of similar institutional development, greatly affects the likelihood of effective collective action. © 2009 Elsevier B.V. All rights reserved.

Eco-evolutionary feedbacks in community and ecosystem ecology: interactions between the ecological theatre and the evolutionary play.

Interactions between natural selection and environmental change are well recognized and sit at the core of ecology and evolutionary biology. Reciprocal interactions between ecology and evolution, eco-evolutionary feedbacks, are less well studied, even though they may be critical for understanding the evolution of biological diversity, the structure of communities and the function of ecosystems. Eco-evolutionary feedbacks require that populations alter their environment (niche construction) and that those changes in the environment feed back to influence the subsequent evolution of the population. There is strong evidence that organisms influence their environment through predation, nutrient excretion and habitat modification, and that populations evolve in response to changes in their environment at time-scales congruent with ecological change (contemporary evolution). Here, we outline how the niche construction and contemporary evolution interact to alter the direction of evolution and the structure and function of communities and ecosystems. We then present five empirical systems that highlight important characteristics of eco-evolutionary feedbacks: rotifer-algae chemostats; alewife-zooplankton interactions in lakes; guppy life-history evolution and nutrient cycling in streams; avian seed predators and plants; and tree leaf chemistry and soil processes. The alewife-zooplankton system provides the most complete evidence for eco-evolutionary feedbacks, but other systems highlight the potential for eco-evolutionary feedbacks in a wide variety of natural systems.

Eco-evolutionary dynamics: intertwining ecological and evolutionary processes in contemporary time.

Evolution occurring over contemporary time scales can have important effects on populations, communities, and ecosystems. Recent studies show that the magnitude of these effects can be large and can generate feedbacks that further shape evolution.

On the multiple ecological roles of water in river networks

The distribution and movement of water can influence the state and dynamics of terrestrial and aquatic ecosystems through a diversity of mechanisms. These mechanisms can be organized into three general categories wherein water acts as (1) a resource or habitat for biota, (2) a vector for connectivity and exchange of energy, materials, and organisms, and (3) as an agent of geomorphic change and disturbance. These latter two roles are highlighted in current models, which emphasize hydrologic connectivity and geomorphic change as determinants of the spatial and temporal distributions of species and processes in river systems. Water availability, on the other hand, has received less attention as a driver of ecological pattern, despite the prevalence of intermittent streams, and strong potential for environmental change to alter the spatial extent of drying in many regions. Here we summarize long-term research from a Sonoran Desert watershed to illustrate how spatial patterns of ecosystem structure and functioning reflect shifts in the relative importance of different 'roles of water' across scales of drainage size. These roles are distributed and interact hierarchically in the landscape, and for the bulk of the drainage network it is the duration of water availability that represents the primary determinant of ecological processes. Only for the largest catchments, with the most permanent flow regimes, do flood-associated disturbances and hydrologic exchange emerge as important drivers of local dynamics. While desert basins represent an extreme case, the diversity of mechanisms by which the availability and flow of water influence ecosystem structure and functioning are general. Predicting how river ecosystems may respond to future environmental pressures will require clear understanding of how changes in the spatial extent and relative overlap of these different roles of water shape ecological patterns. © 2013 Sponseller et al.