Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.     

Inconsistent heuristics in theory and practice

In the field of heuristic search it is usually assumed that admissible heuristics are consistent, implying that consistency is a desirable attribute. The term “inconsistent heuristic” has, at times, been portrayed negatively, as something to be avoided. Part of this is historical: early research discovered that inconsistency can lead to poor performance for A^? (nodes might be re-expanded many times). However, the issue has never been fully investigated, and was not re-considered after the invention of IDA^?.This paper shows that many of the preconceived notions about inconsistent heuristics are outdated. The worst-case exponential time of inconsistent heuristics is shown to only occur on contrived graphs with edge weights that are exponential in the size of the graph. Furthermore, the paper shows that rather than being something to be avoided, inconsistent heuristics often add a diversity of heuristic values into a search which can lead to a reduction in the number of node expansions. Inconsistent heuristics are easy to create, contrary to the common perception in the AI literature. To demonstrate this, a number of methods for achieving effective inconsistent heuristics are presented.Pathmax is a way of propagating inconsistent heuristic values in the search from parent to children. This technique is generalized into bidirectional pathmax (BPMX) which propagates values from a parent to a child node, and vice versa. BPMX can be integrated into IDA^? and A^?. When inconsistent heuristics are used with BPMX, experimental results show a large reduction in the search effort required by IDA^?. Positive results are also presented for A^? searches.     

Evolution of social learning when high expected payoffs are associated with high risk of failure

In an environment where the availability of resources sought by a forager varies greatly, individual foraging is likely to be associated with a high risk of failure. Foragers that learn where the best sources of food are located are likely to develop risk aversion, causing them to avoid the patches that are in fact the best; the result is sub-optimal behaviour. Yet, foragers living in a group may not only learn by themselves, but also by observing others. Using evolutionary agent-based computer simulations of a social foraging game, we show that in an environment where the most productive resources occur with the lowest probability, socially acquired information is strongly favoured over individual experience. While social learning is usually regarded as beneficial because it filters out maladaptive behaviours, the advantage of social learning in a risky environment stems from the fact that it allows risk aversion to be circumvented and the best food source to be revisited despite repeated failures. Our results demonstrate that the consequences of individual risk aversion may be better understood within a social context and suggest one possible explanation for the strong preference for social information over individual experience often observed in both humans and animals.     

Cycle time distribution in circulating systems

The cycle time distribution (CTD) within closed, continuously circulating systems is defined and related to the residence time distributions of flow regions which make up such systems. Examples of the application of the CTD are noted and experimental methods for determining CTDs for various systems are summarized.     

Ring-type plasmon resonance in metallic nanoshells

A simple, approximate theoretical model of surface plasmon resonance in two-dimensional metal nanoshells is developed. The model is based on the concept of short-range surface plasmons propagating around closed circular metal nanotubes. In this model, the plasmon resonance in a metal nanotube is treated as a propagating, self-interfering plasmonic wave, in a ring-type resonance, at plasmonic wavelengths matching an integer fraction of the nanotube's effective circumference. The model is validated by detailed computer simulations based on the finite-difference time-domain method and is shown to be in full agreement with the widely used plasmon hybridization model, which is based on the quasi-static approximation.     

The limiting residence time distribution of continuous recycle systems

The limiting residence time distribution (RTD) of continuous recycle systems as the recycle ratio approaches infinity is considered. It is shown that the RTD converges to the exponential distribution whenever the system does not consist of a “dead volume” at the limit. This limiting behavior is independent of the system configuration and flow patterns. Issues concerning the proper modeling approach and the mathematical formulation of the condition that the system has no “dead volume” are discussed in detail. Some examples illustrating the importance of selecting the proper modeling approach are also provided.     

Deterministic Resource Discovery in Distributed Networks

The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph that represents the vertices’ knowledge about the topology of the underlying communication network. The current paper proposes a deterministic algorithm for the problem in the same model, with improved time, message, and communication complexities. Each previous algorithm had a complexity that was higher at least in one of the measures. Specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity $O(n^3)$ (with message complexity $O(n^2)$), or message complexity $O(|E_0| \log n)$ (where $E_0$ is the arc set of the initial graph $G_0$). Compared with the main randomized algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced from $O(\log^2n)$ to\pagebreak[4] $O(\log n )$, the message complexity from $O(n \log^2 n)$ to $O(n \log n )$, and the communication complexity from $O(n^2 \log^3 n)$ to $O(|E_0|\log ^2 n )$. \par Our work significantly extends the connectivity algorithm of Shiloach and Vishkin which was originally given for a parallel model of computation. Our result also confirms a conjecture of Harchol-Balter, Leighton, and Lewin, and addresses an open question due to Lipton.     

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.Richard Cole was supported in part by NSF Grants DCR-84-01633 and CCR-8702271, ONR Grant N00014-85-K-0046 and by an IBM faculty development award. Uzi Vishkin was supported in part by NSF Grants NSF-CCR-8615337 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046, by the Applied Mathematical Science subprogram of the office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077 and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities.     

Duality in permutation state spaces and the dual search algorithm

Geometrical symmetries are commonly exploited to improve the efficiency of search algorithms. A new type of symmetry in permutation state spaces, duality, is introduced. Each state has a dual state. Both states share important attributes such as their distance to the goal. Given a state S, it is shown that an admissible heuristic of the dual state of S is an admissible heuristic for S. This provides opportunities for additional heuristic evaluations. An exact definition of the class of problems where duality exists is provided. A new search algorithm, dual search, is presented which switches between the original state and the dual state when it seems likely that the switch will improve the chance of reaching the goal faster. The decision of when to switch is very important and several policies for doing this are investigated. Experimental results show significant improvements for a number of applications, for using the dual state's heuristic evaluation and/or dual search.     

On the fringing-field effect in liquid-crystal beam-steering devices

A detailed simulation of the fringing-field effect in liquid-crystal (LC)-based blazed-grating structures has been carried out. These studies are aimed at clarifying the relationship between the width of the fringing-field-broadened phase profile of the blazed grating and the LC cell thickness. This fringing-field broadening of the blazed grating's phase profile is shown to affect mostly the 2pi phase-step zone (fly-back zone) of the blazed grating. The results of the simulations carried out on the blazed-grating structure indicate two main effects of the fringing field: (1) reduction in the attainable diffraction efficiency and (2) limitation of the maximum deflection angle of the device. Both effects are shown to be directly linked to the broadening of the fly-back zone, which is shown to be proportional to the LC cell thickness.