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 Impact of AIDS on Government Service Delivery: The Case of the Zambia Wildlife Authority

Background: The loss of working-aged adults to HIV/AIDS has been shown to increase the costs of labor to the private sector in Africa. There is little corresponding evidence for the public sector. This study evaluated the impact of AIDS on the capacity of a government agency, the Zambia Wildlife Authority (ZAWA), to patrol Zambia’s national parks. Methods: Data were collected from ZAWA on workforce characteristics, recent mortality, costs, and the number of days spent on patrol between 2003 and 2005 by a sample of 76 current patrol officers (reference subjects) and 11 patrol officers who died of AIDS or suspected AIDS (index subjects). An estimate was made of the impact of AIDS on service delivery capacity and labor costs and the potential net benefits of providing treatment. Results: Reference subjects spent an average of 197.4 days on patrol per year. After adjusting for age, years of service, and worksite, index subjects spent 62.8 days on patrol in their last year of service (68% decrease, p<0.0001), 96.8 days on patrol in their second to last year of service (51% decrease, p<0.0001), and 123.7 days on patrol in their third to last year of service (37% decrease, p<0.0001). For each employee who died, ZAWA lost an additional 111 person-days for management, funeral attendance, vacancy, and recruitment and training of a replacement, resulting in a total productivity loss per death of 2.0 person-years. Each AIDS-related death also imposed budgetary costs for care, benefits, recruitment, and training equivalent to 3.3 years’ annual compensation. In 2005, AIDS reduced service delivery capacity by 6.2% and increased labor costs by 9.7%. If antiretroviral therapy could be provided for $500/patient/year, net savings to ZAWA would approach $285,000/year. Conclusion: AIDS is constraining ZAWA’s ability to protect Zambia’s wildlife and parks. Impacts on this government agency are substantially larger than have been observed in the private sector. Provision of ART would result in net budgetary savings to ZAWA and greatly increase its service delivery capacity.

Christian Witness on the Plateau Vivarais-Lignon: Narrative, Nonviolence, and the Formation of Character

This dissertation analyzes the theological and ethical convictions that led the people of the Plateau Vivarais-Lignon to shelter thousands of refugees between 1939 and 1945. It does so by examining the themes of narrative identity, hospitality, character formation, nonviolence, and the contextual witness of church tradition. Though a number of studies have been published about the rescue activity in this region of France during World War II, none have thoroughly analyzed the theological nature of this activity. Using the Plateau Vivarais-Lignon as a case study in theological ethics, the dissertation draws on historical sources as well as the work of contemporary theologians and ethicists to understand, interpret, and analyze the witness of this community. After situating its rescue and resistance work within the Huguenot narrative of persecution and exile, I examine the theological convictions of the Reformed pastor of Le Chambon-sur-Lignon, André Trocmé, who played a key role in making the Plateau a place of refuge during the Holocaust. The study highlights the importance of narrative in the actions of this community and discusses the relationship between narrative, character, and ethics. It then examines the nonviolent commitments of key leaders of the rescue effort, using this analysis as a springboard to engage in broader theological reflection about the ethics of nonviolence. After examining the radical hospitality practiced on the Plateau in light of biblical narratives and Reformed history, I investigate the counter-cultural nature of Christian hospitality. The study concludes by analyzing the nature and witness of the church in light of the legacy of the Plateau Vivarais-Lignon. The dissertation suggests that increased academic and ecclesial attention be given to the relationship between narrative and character, the counter-cultural shape of Christian hospitality, and the active nature of nonviolence. It presents an in-depth analysis of the theological and ethical convictions of the people of the Plateau Vivarais-Lignon, arguing that their witness has ongoing significance for communities of faith as they grapple with how to form disciples, relate to the wider society, welcome strangers, and communicate God's shalom in a world of violence.

On the Efficiency and Fairness of Transmission Control Loops: A Case for Exogenous Losses

We postulate that exogenous losses-which are typically regarded as introducing undesirable "noise" that needs to be filtered out or hidden from end points-can be surprisingly beneficial. In this paper we evaluate the effects of exogenous losses on transmission control loops, focusing primarily on efficiency and convergence to fairness properties. By analytically capturing the effects of exogenous losses, we are able to characterize the transient behavior of TCP. Our numerical results suggest that "noise" resulting from exogenous losses should not be filtered out blindly, and that a careful examination of the parameter space leads to better strategies regarding the treatment of exogenous losses inside the network. Specifically, we show that while low levels of exogenous losses do help connections converge to their fair share, higher levels of losses lead to inefficient network utilization. We draw the line between these two cases by determining whether or not it is advantageous to hide, or more interestingly introduce, exogenous losses. Our proposed approach is based on classifying the effects of exogenous losses into long-term and short-term effects. Such classification informs the extent to which we control exogenous losses, so as to operate in an efficient and fair region. We validate our results through simulations.