A Lower-Bound Result on the Power of a Genetic Algorithm

This paper presents a lower-bound result on the computational power of a genetic algorithm in the context of combinatorial optimization. We describe a new genetic algorithm, the merged genetic algorithm, and prove that for the class of monotonic functions, the algorithm finds the optimal solution, and does so with an exponential convergence rate. The analysis pertains to the ideal behavior of the algorithm where the main task reduces to showing convergence of probability distributions over the search space of combinatorial structures to the optimal one. We take exponential convergence to be indicative of efficient solvability for the sample-bounded algorithm, although a sampling theory is needed to better relate the limit behavior to actual behavior. The paper concludes with a discussion of some immediate problems that lie ahead.

Geometric Generalizations of the Power of Two Choices

A well-known paradigm for load balancing in distributed systems is the``power of two choices,''whereby an item is stored at the less loaded of two (or more) random alternative servers. We investigate the power of two choices in natural settings for distributed computing where items and servers reside in a geometric space and each item is associated with the server that is its nearest neighbor. This is in fact the backdrop for distributed hash tables such as Chord, where the geometric space is determined by clockwise distance on a one-dimensional ring. Theoretically, we consider the following load balancing problem. Suppose that servers are initially hashed uniformly at random to points in the space. Sequentially, each item then considers d candidate insertion points also chosen uniformly at random from the space,and selects the insertion point whose associated server has the least load. For the one-dimensional ring, and for Euclidean distance on the two-dimensional torus, we demonstrate that when n data items are hashed to n servers,the maximum load at any server is log log n / log d + O(1) with high probability. While our results match the well-known bounds in the standard setting in which each server is selected equiprobably, our applications do not have this feature, since the sizes of the nearest-neighbor regions around servers are non-uniform. Therefore, the novelty in our methods lies in developing appropriate tail bounds on the distribution of nearest-neighbor region sizes and in adapting previous arguments to this more general setting. In addition, we provide simulation results demonstrating the load balance that results as the system size scales into the millions.

Bounds on the Power of Constant-Depth Quantum Circuits

We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 ⊆ P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo [?] to show that, for any family

PARAMETERS AFFECTING THE IMAGING AND DETECTION OF MICROBUBBLES IN BLOOD

Stabilized micron-sized bubbles, known as contrast agents, are often injected into the body to enhance ultrasound imaging of blood flow. The ability to detect such bubbles in blood depends on the relative magnitude of the acoustic power backscattered from the microbubbles (‘signal’) to the power backscattered from the red blood cells (‘noise’). Erythrocytes are acoustically small (Rayleigh regime), weak scatterers, and therefore the backscatter coefficient (BSC) of blood increases as the fourth power of frequency throughout the diagnostic frequency range. Microbubbles, on the other hand, are either resonant or super-resonant in the range 5-30 MHz. Above resonance, their total scattering cross-section remains constant with increasing frequency. In the present thesis, a theoretical model of the BSC of a suspension of red blood cells is presented and compared to the BSC of Optison® contrast agent microbubbles. It is predicted that, as the frequency increases, the BSC of red blood cell suspensions eventually exceeds the BSC of the strong scattering microbubbles, leading to a dramatic reduction in signal-to-noise ratio (SNR). This decrease in SNR with increasing frequency was also confirmed experimentally by use of an active cavitation detector for different concentrations of Optison® microbubbles in erythrocyte suspensions of different hematocrits. The magnitude of the observed decrease in SNR correlated well with theoretical predictions in most cases, except for very dense suspensions of red blood cells, where it is hypothesized that the close proximity of erythrocytes inhibits the acoustic response of the microbubbles.

Reading Between the Lines: The Potential of Popular Young Adult Fiction in Adolescent Spiritual Formation

Popular culture is a powerful, shaping force in the lives of teenagers between the ages of fourteen through eighteen in the United States today. This dissertation argues the importance of popular fiction for adolescent spiritual formation and it investigates that importance by exploring the significance of narrative for theology and moral formation. The dissertation employs mythic and archetypal criticism as a tool for informing the selection and critique of narratives for use in adolescent spiritual development and it also incorporates insights gained from developmental psychology to lay the groundwork for the development of a curriculum that uses young adult fiction in a program of spiritual formation for teenagers in a local church setting. The dissertation defends the power of narrative in Christian theology and concludes that narrative shapes the imagination in ways that alter perception and are important for the faith life of teenagers in particular. I go on to argue that not all narratives are created equal. In using literary myth criticism in concert with theology, I use the two disciplines’ different aims and methods to fully flesh out the potential of theologies intrinsic to works meant for a largely secular audience. The dissertation compares various works of young adult fiction (M.T. Anderson’s Feed and Terry Pratchett’s Nation in dialogue with a theology of creation; Marcus Zusak’s I am the Messenger and Jerry Spinelli’s Stargirl in dialogue with salvation and saviors; and the four novels of Stephanie Meyer’s Twilight saga in dialogue with a theology of hope (eschatology). The dissertation explores how each theme surfaces (even if only implicitly) from both literary and theological standpoints. The dissertation concludes with a sample four-week lesson plan that demonstrates one way the theological and literary critique can be formed into a practical curriculum for use in an adolescent spiritual development setting. Ultimately, this dissertation provides a framework for how practitioners of young adult formation can select, analyze, and develop materials for their teenagers using new works of popular young adult fiction. The dissertation comes to the conclusion that popular fiction contains a wealth of material that can challenge and shape young readers’ own emerging theology.

A Direct Algorithm for the Type Interference in the Rank 2 Fragment of the Second--Order λ-Calculus

We study the problem of type inference for a family of polymorphic type disciplines containing the power of Core-ML. This family comprises all levels of the stratification of the second-order lambda-calculus by "rank" of types. We show that typability is an undecidable problem at every rank k ≥ 3 of this stratification. While it was already known that typability is decidable at rank ≤ 2, no direct and easy-to-implement algorithm was available. To design such an algorithm, we develop a new notion of reduction and show how to use it to reduce the problem of typability at rank 2 to the problem of acyclic semi-unification. A by-product of our analysis is the publication of a simple solution procedure for acyclic semi-unification.

Characterization of Network-Wide Anomalies in Traffic Flows

Detecting and understanding anomalies in IP networks is an open and ill-defined problem. Toward this end, we have recently proposed the subspace method for anomaly diagnosis. In this paper we present the first large-scale exploration of the power of the subspace method when applied to flow traffic. An important aspect of this approach is that it fuses information from flow measurements taken throughout a network. We apply the subspace method to three different types of sampled flow traffic in a large academic network: multivariate timeseries of byte counts, packet counts, and IP-flow counts. We show that each traffic type brings into focus a different set of anomalies via the subspace method. We illustrate and classify the set of anomalies detected. We find that almost all of the anomalies detected represent events of interest to network operators. Furthermore, the anomalies span a remarkably wide spectrum of event types, including denial of service attacks (single-source and distributed), flash crowds, port scanning, downstream traffic engineering, high-rate flows, worm propagation, and network outage.

Principles of Safe Policy Routing Dynamics

We introduce the Dynamic Policy Routing (DPR) model that captures the propagation of route updates under arbitrary changes in topology or path preferences. DPR introduces the notion of causation chains where the route flap at one node causes a flap at the next node along the chain. Using DPR, we model the Gao-Rexford (economic) guidelines that guarantee the safety (i.e., convergence) of policy routing. We establish three principles of safe policy routing dynamics. The non-interference principle provides insight into which ASes can directly induce route changes in one another. The single cycle principle and the multi-tiered cycle principle provide insight into how cycles of routing updates can manifest in any network. We develop INTERFERENCEBEAT, a distributed algorithm that propagates a small token along causation chains to check adherence to these principles. To enhance the diagnosis power of INTERFERENCEBEAT, we model four violations of the Gao-Rexford guidelines (e.g., transiting between peers) and characterize the resulting dynamics.

Typed Abstraction of Complex Network Compositions

The heterogeneity and open nature of network systems make analysis of compositions of components quite challenging, making the design and implementation of robust network services largely inaccessible to the average programmer. We propose the development of a novel type system and practical type spaces which reflect simplified representations of the results and conclusions which can be derived from complex compositional theories in more accessible ways, essentially allowing the system architect or programmer to be exposed only to the inputs and output of compositional analysis without having to be familiar with the ins and outs of its internals. Toward this end we present the TRAFFIC (Typed Representation and Analysis of Flows For Interoperability Checks) framework, a simple flow-composition and typing language with corresponding type system. We then discuss and demonstrate the expressive power of a type space for TRAFFIC derived from the network calculus, allowing us to reason about and infer such properties as data arrival, transit, and loss rates in large composite network applications.