Physical Sciences and Mathematics Commons^™

The Complexity Of Computations By Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

We survey the current state of knowledge concerning the computation of Boolean functions by networks, with particular emphasis on the addition and multiplication of binary numbers.

A Theoretical Investigation Of Some Low-Lying Singlet States Of 1,3-Butadiene, Robert J. Cave, Ernest R. Davidson

All HMC Faculty Publications and Research

Results are presented from extensive ab initio calculations on several low-lying singlet states of cis- and trans-1,3-butadiene. The results indicate a qualitative difference between the cis and trans isomers for the lowest π → π* transition. For the cis isomer, the first excited singlet state of the same symmetry as the ground state is found to lie above the lowest π → π* transition, and we estimate that this is also the case for the trans isomer.

Sorting And Selecting In Rounds, Nicholas Pippenger

All HMC Faculty Publications and Research

We present upper bounds for sorting and selecting the median in a fixed number of rounds. These bounds match the known lower bounds to within logarithmic factors. They also have the merit of being “explicit modulo expansion”; that is, probabilistic arguments are used only to obtain expanding graphs, and when explicit constructions for such graphs are found, explicit algorithms for sorting and selecting will follow. Using the best currently available explicit constructions for expanding graphs, we present the best currently known explicit algorithms for sorting and selecting in rounds.

The Gradient Model Load Balancing Method, Frank C. H. Lin, Robert M. Keller

All HMC Faculty Publications and Research

A dynamic load balancing method is proposed for a class of large-diameter multiprocessor systems. The method is based on the "gradient model," which entails transferring backlogged tasks to nearby idle processors according to a pressure gradient indirectly established by requests from idle processors. The algorithm is fully distributed and asynchronous. Global balance is achieved by successive refinements of many localized balances. The gradient model is formulated so as to be independent of system topology.

Rigid And Nonrigid Achirality, Erica Flapan

Pomona Faculty Publications and Research

In order to completely characterize a molecule it is useful to understand the symmetries of its molecular bond graph in 3-space. For many purposes the most important type of symmetry that a molecule can exhibit is mirror image symmetry. However, the question of whether a molecular graph is equivalent to its mirror image has different interpretations depending on what assumptions are made about the rigidity of the molecular structure. If there is a deformation of 3-space taking a molecular bond graph to its mirror image then the molecule is said to be topologically achiral. If a molecular graph can be …

Do We Really Know What Makes Educational Software Effective? A Call For Empirical Research On Effectiveness, Karen Jolicoeur, Dale E. Berger

CGU Faculty Publications and Research

Empirical information on specific factors that make educational software effective in reaching instructional objectives would be of considerable value. The authors describe the current state of evaluation research with educational software and discuss how popular software review methods fall short of meeting our need to know how well specific programs work.

Computers And The Nature Of Man: A Historian's Perspective On Controversies About Artificial Intelligence, Judith V. Grabiner

Pitzer Faculty Publications and Research

The purpose of the present paper is to provide a historical perspective on recent controversies, from Turing's time on, about artificial intelligence, and to make clear that these are in fact controversies about the nature of man. First, I shall briefly review three recent controversies about artificial intelligence, controversies over whether computers can think and over whether people are no more than information-processing machines. These three controversies were each initiated by philosophers who, irrespective of what the programs of their time actually did, viewed with alarm the argument that if a machine can think, a thinking being is just a …

Distributed Recovery In Applicative Systems, Frank C. H. Lin, Robert M. Keller

All HMC Faculty Publications and Research

Applicative systems are promising candidates for achieving high performance computing through aggregation of processors. This paper studies the fault recovery problems in a class of applicative systems. The concept of functional checkpointing is proposed as the nucleus of a distributed recovery mechanism. This entails incrementally building a resilient structure as the evaluation of an applicative program proceeds. A simple rollback algorithm is suggested to regenerate the corrupted structure by redoing the most effective functional checkpoints. Another algorithm, which attempts to recover intermediate results, is also presented. The parent of a faulty task reproduces a functional twin of the failed task. …

A Semiclassical Model For Orientation Effects In Electron Transfer Reactions, Robert J. Cave, Stephen J. Klippenstein, R.A. Marcus

All HMC Faculty Publications and Research

An approximate solution to the single‐particle Schrödinger equation with an oblate spheroidal potential well of finite depth is presented. The electronic matrix element H_BA for thermal electron transfer is calculated using these wave functions, and is compared with values of H_BA obtained using the exact solution of the same Schrödinger equation. The present method yields accurate results for H_BA, within the oblate spheroidal potential well model, and is useful for examining the orientational effects of the two centers on the rate of electron transfer.

Chemical Applications Of Scanning Tunneling Microscopy, Paul West, John Kramer, David V. Baxter, Robert J. Cave, John D. Baldeschwieler

All HMC Faculty Publications and Research

The development of a scanning tunneling microscope at the California Institute of Technology is well under way. Electron tunneling has been demonstrated, and preliminary surface images of gold films have been obtained. Additional instrumental development is required to achieve the atomic resolution which is required for the study of chemical processes on surfaces. A theoretical model is also being developed for the study of tunneling of electrons from the probe to surfaces with molecular species absorbed, and with atomic and molecular species intervening between the probe and the surface. These experimental tools and theoretical models, which are being developed concurrently, …

Mutual Orientation Effects On Electron-Transfer Reactions Between Porphyrins, Robert J. Cave, Paul Siders, R.A. Marcus

All HMC Faculty Publications and Research

Mutual orientation effects on the rate of nonadiabatic electron transfer between several diporphyrin pairs of experimental interest are examined. The electronic matrix element for electron transfer is calculated within a one-electron spheroidal model for a variety of states and orientations which are relevant to both biological and synthetic electron-transfer systems. Both the mutual orientation of the pairs and the nodal structure of the donor and acceptor orbitals can have large effects on calculated rates.

Alphabetic Minimax Trees Of Degree At Most T*, D. Coppersmith, Maria M. Klawe, Nicholas Pippenger

All HMC Faculty Publications and Research

Problems in circuit fan-out reduction motivate the study of constructing various types of weighted trees that are optimal with respect to maximum weighted path length. An upper bound on the maximum weighted path length and an efficient construction algorithm will be presented for trees of degree at most t, along with their implications for circuit fan-out reduction.

Reliable Computation In The Presence Of Noise, Nicholas Pippenger

All HMC Faculty Publications and Research

This talk concerns computation by systems whose components exhibit noise (that is, errors committed at random according to certain probabilistic laws). If we aspire to construct a theory of computation in the presence of noise, we must possess at the outset a satisfactory theory of computation in the absence of noise.

A theory that has received considerable attention in this context is that of the computation of Boolean functions by networks (with perhaps the strongest competition coming from the theory of cellular automata; see [G] and [GR]). The theory of computation by networks associates with any two sets Q and …

A Prime Strongly Positive Amphicheiral Knot Which Is Not Slice, Erica Flapan

Pomona Faculty Publications and Research

We begin by giving several definitions. A knot K in S³ is said to be amphicheiral if there is an orientation-reversing diffeomorphism h of S³ which leaves K setwise invariant. Suppose, in addition, that K is given an orientation. ThenK is said to be positive amphicheiral if h preserves the orientation of K. If, in addition, the diffeomorphism h is an involution then K is strongly positive amphicheiral. Finally, we say a knot is slice if it bounds a smooth disc in B⁴. In this note we shall give a smooth example of …

The Taman Negara Batek: A People In Transition, Paul Faulstich

Pitzer Faculty Publications and Research

Batek Negritos from the vicinity of Taman Negara National Park in West Malaysia are a hunting and gathering people presently experiencing rapid encroachment by the modern world. Under the authority of the Malaysian government, they are being encouraged to settle and to emulate Malay subsistence farming communities. Unfortunately, this strategy has had a number of adverse effects on the Batek.

Approaching Distributed Database Implementations Through Functional Programming Concepts, Robert M. Keller, Gary Lindstrom

All HMC Faculty Publications and Research

The application of functional programming concepts to the data representation and querying aspects of databases has been discussed by Shipman and Buneman, et al. respectively. We argue the suitability of a function-based approach to additional aspects of database systems, including updating, transaction serialization, and physical distribution and communication. It is shown how the NmergeH extension of a purely functional model permits serializable concurrent "primary site" distribution control. We also present preliminary experimental results which indicate that a reasonable degree of concurrency is attainable from the functional approach.

Measuring R And D Productivity, Richard A. Pappas, Donald S. Remer

All HMC Faculty Publications and Research

Measuring the productivity of an R&D organization is extremely tricky. Productivity is usually defined as a ratio of an output, like number of cars produced on an assembly line, to an input, like the wages paid the workers. While R&D may have a measurable input, the output is often intangible and difficult to quantify. This is further complicated because the return from an R&D department may not be realized for one or two decades,which means the time lag is much higher than in factory measurements. Furthermore, many researchers believe that this kind of measurement may be counterproductive,since the mere act …

Problems Of Channel Correlation And Statistical Bias In Photon-Correlation Spectroscopy, Richard C. Haskell, Gary L. Pisciotta

All HMC Faculty Publications and Research

Correlation between channels of the normalized photocount-rate correlation function g⁽²⁾(τ) becomes significant at high count rates and leads to a number of data-analysis problems. We derive an expression for channel correlation that is valid for a detector area of arbitrary extent and compare the theoretical predictions with measured values. A data-analysis procedure is demonstrated that employs the theoretical expression for channel correlation and provides a rigorous test of an assumed fitting function. The procedure facilitates the use of the cumulant method in determining the polydispersity of scatterers. An expression for the statistical bias of g^{(2) …}

The Quaternary Bone Caves And Associated Sites At Wallingford, Jamaica, Donald A. Mcfarlane, R. E. Gledhill

WM Keck Science Faculty Papers

A group of caves associated with the sink of the One Eye River in St. Elizabeth Parish, Jamaica, have been the subject of numerous important palaeontological investigations beginning 1919. Unfortunately, considerable confusion has arisen in the literature through inadequate documentation of different sites. The caves of the immediate area are described and located, and their palaeontological significance is summarised in the light of recent taxonomic review and relevant geochronological evidence.

Response Of Lithographic Mask Structures To Repetitively Pulsed X-Rays: Thermal Stress Analysis, A. Ballantyne, H.A. Hyman, Clive L. Dym, R.C. Southworth

All HMC Faculty Publications and Research

This paper examines the effects of thermal loading and time history upon the thermal stresses developed in lithographic mask structures as would be expected under irradiation by intense soft x rays. The objective of this work was to examine the phenomenology of the interaction and to evaluate the limits placed upon mask dosage. The mechanics of mask failure are examined in terms of single pulse and cumulative, or fatigue, effects. A number of prototypical mask structures are investigated, which show that the application of intense pulsed sources to x‐ray lithography does not reduce the potential utility of the techique. However, …

Some Graph-Colouring Theorems With Applications To Generalized Connection Networks, David G. Kirkpatrick, Maria M. Klawe, Nicholas Pippenger

All HMC Faculty Publications and Research

With the aid of a new graph-colouring theorem, we give a simple explicit construction for generalized n-connectors with 2k - 1 stages and O( n^{1 + 1 / k} (log n )^{( k - 1)/ 2} ) edges. This is asymptotically the best explicit construction known for generalized connectors.

On The Steepest Descent For Nonpotential Locally Lipschitzian Vector Fields, Alfonso Castro

All HMC Faculty Publications and Research

In [4] J. Neuberger gave various sufficient conditions for the solvability of nonvariational operator equations via a variant of the steepest descent method. In this note we give versions of these conditions under weaker assumptions on the smoothness of the operators.

Response Of Lithographic Mask Structures To Repetitively Pulsed X-Rays: Dynamic Response, Clive L. Dym, A. Ballantyne

All HMC Faculty Publications and Research

This paper addresses the issue of the dynamic response of thin lithographic mask structures to thermally induced stress fields. In particular, the impact of repetitively pulsed x‐ray sources are examined: the short duration (1–100 nsec) pulses induce large step changes in mask temperatures, which can, in turn, induce a dynamic response. The impact of conductive cooling of the mask is to reduce the repetitively pulsed problem to a series of isolated nearly identical thermal impulses of duration approximately equal to the cooling time. The importance of self‐weight and prestress is examined, and an analysis of the nonlinear dynamic response to …

Necessary And Sufficient Conditions For Certain Homology 3-Spheres To Have Smooth Zp-Actions, Erica Flapan

Pomona Faculty Publications and Research

We derive necessary and sufficient conditions for a broad class of homology 3-spheres, obtained as the gluing of two knot complements, to have Zp-actions.

We explore when a homology sphere, obtained as the gluing of two knot complements has any smooth periodic diffeomorphisms.

Infinitely Periodic Knots, Erica Flapan

Pomona Faculty Publications and Research

One aspect of the study of 3-manifolds is to determine what infinite group actions a given manifold has. Some important questions that one can ask about these actions on a given manifold are: What periods could they have? and, what sets of points may be fixed by the action?

A Model For Orientation Effects In Electron‐Transfer Reactions, Paul Siders, Robert J. Cave, R.A. Marcus

All HMC Faculty Publications and Research

A method for solving the single‐particle Schrödinger equation with an oblate spheroidal potential of finite depth is presented. The wave functions are then used to calculate the matrix element T_BA which appears in theories of nonadiabatic electron transfer. The results illustrate the effects of mutual orientation and separation of the two centers on T_BA. Trends in these results are discussed in terms of geometrical and nodal structure effects. Analytical expressions related to T_BA for states of spherical wells are presented and used to analyze the nodal structure effects for T_BA for the spheroidal wells.

Simulated Performance Of A Reduction-Based Multiprocessing System, Robert M. Keller, Frank C. H. Lin

All HMC Faculty Publications and Research

Multiprocessing systems have the potential for increasing system speed over what is now offered by device technology. They must provide the means of generating work for the processors, getting the work to processors, and coherently collecting the results from the processors. For most applications, they should also ensure the repeatability of behavior, i.e., determinacy, speed-independence, or elimination of "critical races." Determinacy can be destroyed, for example, by permitting-in separate, concurrent processes statements such as "x: = x + 1" and "if x = 0 then… else…", which share a common variable. Here, there may be a critical race, in that …

Group Comparability: A Multiattribute Utility Measurement Approach To The Use Of Random Assignment With Small Numbers Of Aggregated Units, C. Anderson Johnson, John W. Graham, Brian R. Flay, William B. Hansen, Linda M. Collins

CGU Faculty Publications and Research

It is not always possible, especially in large-scale evaluation research, to ensure that random assignment will produce groups that are comparable on any number of potentially important factors. Typically, gaining comparability has been achieved only at the expense of random assignment. A method is presented that allows multivariate comparability while making only minimal restrictions on randomization. The procedure is demonstrated in the context of assigning 63 aggregated units (schools) to 28 experimental and control conditions. Good comparability of groups for all primary main effects and interactions was verified for 15 individual variables.

Rediflow Multiprocessing, Robert M. Keller, Frank C. H. Lin, Jiro Tanaka

All HMC Faculty Publications and Research

We discuss the concepts underlying Rediflow, a multiprocessing system being designed to support concurrent programming through a hybrid model of reduction, dataflow, and von Neumann processes. The techniques of automatic load-balancing in Rediflow are described in some detail.

Consistency Testing For Data-Flow Circuits, Chu S. Jhon, Robert M. Keller

All HMC Faculty Publications and Research

One means of making VLSI design tractable is to proceed from a high-level specification of a circuit in terms of functionality, to the circuit level. A notable error which may occur in a topdown design starting with a data-flow graph representation of a circuit is a design inconsistency due to deadlock. This paper attempts to further develop the theoretical basis for algorithms which analyze the deadlock property of circuits on the basis of their data-flow graph representations. A systematic scheme to verify the absence of deadlock in data-flow graphs is also presented.