Mathematics Commons^™

Faster Circuits And Shorter Formulas For Multiple Addition, Multiplication And Symmetric Boolean Functions, Michael Paterson, Uri Zwick, Nicholas Pippenger

All HMC Faculty Publications and Research

A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulas for the carry-save addition of n numbers using any given basic addition unit. More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N, then the shortest multiple carry-save addition formulas that could be obtained by composing BA units are of size n1p+o(1)/, where p is the unique real number for which the Lp norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal …

Radially Symmetric Solutions To A Superlinear Dirichlet Problem In A Ball With Jumping Nonlinearities, Alfonso Castro, Alexandra Kurepa

All HMC Faculty Publications and Research

Let p,φ :[0,T] → R be bounded functions with φ > 0. Let g:R → R be a locally Lipschitzian function satisfying the superlinear jumping condition:

(i) lim u → - ∞ (g(u)/u) ε R

(ii) lim u → ∞ (g(u)/(u^{1 + ρ} )) = ∞ for some ρ > 0, and

(iii) lim u → ∞ (u/g(u))^N/2(NG(κ u) - ((N - 2)/2)u · g(u)) = ∞ for some κ ε (0,1] where G is the primitive of g.

Here we prove that the number of solutions of the boundary value problem Δu + g(u) = p(|x|) + cφ …

Review: J.R. Porter And R.G. Woods, Extensions And Absolutes Of Hausdorff Spaces (New York, Berlin, Heidelberg, 1987), Melvin Henriksen

All HMC Faculty Publications and Research

Reviewed work: Jack R. Porter and R. Grant Woods. Extensions and absolutes of Hausdorff spaces. Springer-Verlag, New York, Berlin, Heidelberg, 1987, xiii + 856 pp., $89.00. ISBN 0-387-96212-3.

Nonnegative Solutions For A Class Of Radially Symmetric Nonpositone Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

We consider the existence of radially symmetric non-negative solutions for the boundary value problem

\begin{displaymath}\begin{array}{*{20}{c}} { - \Delta u(x) = \lambda f(u(x))\qua... ...\\ {u(x) = 0\quad \left\Vert x \right\Vert = 1} \\ \end{array} \end{displaymath}

where $ \lambda > 0,f(0) < 0$ (non-positone), $ f' \geq 0$ and $ f$ is superlinear. We establish existence of non-negative solutions for $ \lambda $ small which extends some work of our previous paper on non-positone problems, where we considered the case $ N = 1$. Our work also proves a recent conjecture by Joel Smoller and Arthur Wasserman.

Nonnegative Solutions To A Semilinear Dirichlet Problem In A Ball Are Positive And Radially Symmetric, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

We prove that nonnegative solutions to a semilinear Dirichlet problem in a ball are positive, and hence radially symmetric. In particular, this answers a question in [3] where positive solutions were proven to be radially symmetric. In section 4 we provide a sufficient condition on the geometry of the domain which ensures that nonnegative solutions are positive in the interior.

Turnpike Structures For Optimal Maneuvers, Arthur T. Benjamin

All HMC Faculty Publications and Research

This dissertation is concerned with problems of optimally maneuvering a collection of objects ("pieces") from one location to another, subject to various restrictions on the allowable movements. We illustrate and prove that when the "distance" from the origin to the destination is large, and the movement rules and environment satisfy certain "homogeneity" properties, there exist near-optimal trajectories with very special (turnpike) structure.

These results are obtained by representing the problem through a configuration graph. Here, we have a node for each configuration and an arc for every "different" legal move. Each arc is endowed with a scalar weight …

Random Sequential Absorption On Graphs, Nicholas Pippenger

All HMC Faculty Publications and Research

This paper analyzes a process whereby the vertices of a graph are considered in a random sequence,and each considered vertex is “occupied” unless it or an adjacent vertex has previously been occupied. The process continues until no more vertices can be occupied, at which point the “jamming limit” has been reached. The case in which the graph is regular (so that every vertex has degree $d\geqq 2$ and has “few short cycles” is treated. In particular, the results apply to infinite regular trees, to finite graphs obtained from them by forming quotient graphs, and to random regular graphs.

It is …

The Space Of Minimal Prime Ideals Of C(X) Need Not Be Basically Disconnected, Alan Dow, Melvin Henriksen, Ralph Kopperman, J. Vermeer

All HMC Faculty Publications and Research

Problems posed twenty and twenty-five years ago by M. Henriksen and M. Jerison are solved by showing that the space of minimal prime ideals of the ring C(X) of continuous real-valued functions on a compact (Hausdorff) space need not be basically disconnected-or even an F-space.

Multiple Solutions For A Dirichlet Problem With Jumping Nonlinearities Ii, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

No abstract provided for this article.

Locally Finite Families, Completely Separated Sets And Remote Points, Melvin Henriksen, Thomas J. Peters

All HMC Faculty Publications and Research

It is shown that if X is a nonpseudocompact space with a σ-locally finite π-base, then X has remote points. Within the class of spaces possessing a σ-locally finite π-base, this result extends the work of Chae and Smith, because their work utilized normality to achieve complete separation. It provides spaces which have remote points, where the spaces do not satisfy the conditions required in the previous works by Dow, by van Douwen, by van Mill, or by Peters.

The lemma: "Let X be a space and let {Cε: € < α} be a locally finite family of cozero sets of X. Let {Zε: € < α } be a family of zero sets of X such that for each € < α, Zε с Cε. Then ∪_ε<α Zε is completely separated from X/∪εCε", is a fundamental …

Stability Of Steady Cross-Waves: Theory And Experiment, Seth Lichter, Andrew J. Bernoff

All HMC Faculty Publications and Research

A bifurcation analysis is performed in the neighborhood of neutral stability for cross waves as a function of forcing, detuning, and viscous damping. A transition is seen from a subcritical to a supercritical bifurcation at a critical value of the detuning. The predicted hysteretic behavior is observed experimentally. A similarity scaling in the inviscid limit is also predicted. The experimentally observed bifurcation curves agree with this scaling.

A Semilinear Wave Equation With Nonmonotone Nonlinearity, Alfonso Castro, Sumalee Unsurangsie

All HMC Faculty Publications and Research

We prove that a semilinear wave equation in which the range of the derivative of the nonlinearity includes an eigenvalue of infinite multiplicity has a solution. The solution is obtained through an iteration scheme which provides a priori estimates.

Fault Tolerance In Networks Of Bounded Degree, Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal

All HMC Faculty Publications and Research

Achieving processor cooperation in the presence of faults is a major problem in distributed systems. Popular paradigms such as Byzantine agreement have been studied principally in the context of a complete network. Indeed, Dolev [J. Algorithms, 3 (1982), pp. 14–30] and Hadzilacos [Issues of Fault Tolerance in Concurrent Computations, Ph.D. thesis, Harvard University, Cambridge, MA, 1984] have shown that Ω(t) connectivity is necessary if the requirement is that all nonfaulty processors decide unanimously, where t is the number of faults to be tolerated. We believe that in forseeable technologies the number of faults will grow with the size of the …

Wide-Sense Nonblocking Networks, Paul Feldman, Joel Friedman, Nicholas Pippenger

All HMC Faculty Publications and Research

A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size O( n log n ), and with depth k and size O( n^{1 + 1/k} ( log n )^{1 - 1/k} ).

Nonnegative Solutions For A Class Of Nonpositone Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

In the recent past many results have been established on non-negative solutions to boundary value problems of the form

-u''(x) = λf(u(x)); 0 < x < 1,

u(0) = 0 = u(1)

where λ>0, f(0)>0 (positone problems). In this paper we consider the impact on the non-negative solutions when f(0)<0. We find that we need f(u) to be convex to guarantee uniqueness of positive solutions, and f(u) to be appropriately concave for multiple positive solutions. This is in contrast to the case of positone problems, where the roles of convexity and concavity were interchanged to obtain similar results. We further establish the existence of non-negative solutions with interior zeros, which did not exist in positone problems.

Reliable Computation By Formulas In The Presence Of Noise, Nicholas Pippenger

All HMC Faculty Publications and Research

It is shown that if formulas are used to compute Boolean functions in the presence of randomly occurring failures then: (1) there is a limit strictly less than 1/2 to the failure probability per gate that can be tolerated, and (2) formulas that tolerate failures must be deeper (and, therefore, compute more slowly) than those that do not. The heart of the proof is an information-theoretic argument that deals with computation and errors in very general terms. The strength of this argument is that it applies with equal ease no matter what types of gate are available. Its weaknesses is …

The Bisection Method: Which Root?, Arthur T. Benjamin

All HMC Faculty Publications and Research

No abstract provided in this article.

Quasi F-Covers Of Tychonoff Spaces, Melvin Henriksen, J. Vermeer, R. G. Woods

All HMC Faculty Publications and Research

A Tychonoff topological space is called a quasi F-space if each dense cozero-set of X is C*-embedded in X. In Canad. J. Math. 32 (1980), 657-685 Dashiell, Hager, and Henriksen construct the "minimal quasi F-cover" QF(X) of a compact space X as an inverse limit space, and identify the ring C(QF(X)) as the order-Cauchy completion of the ring C*(X). In On perfect irreducible preimages, Topology Proc. 9 (1984), 173-189, Vermeer constructed the minimal quasi F-cover of an arbitrary Tychonoff space. In this paper the minimal quasi F-cover of a compact space X is constructed as the space of ultrafilters …

Ordered Products Of Topological Groups, Melvin Henriksen, Ralph Kopperman, Frank A. Smith

All HMC Faculty Publications and Research

The topology most often used on a totally ordered group (G, <) is the interval topology. There are usually many ways to totally order G x G (e.g., the lexicographic order) but the interval topology induced by such a total order is rarely used since the product topology has obvious advantages. Let ℝ(+) denote the real line with its usual order and Q(+) the subgroup of rational numbers. There is an order on Q x Q whose associated interval topology is the product topology, but no such order on ℝ x ℝ can be found. In this paper we characterize those pairs G, H of totally ordered groups such that there is a total order on G x H for which the interval topology is the product topology.

Infinitely Many Radially Symmetric Solutions To A Superlinear Dirichlet Problem In A Ball, Alfonso Castro, Alexandra Kurepa

All HMC Faculty Publications and Research

In this paper we show that a radially symmetric superlinear Dirichlet problem in a ball has infinitely many solutions. This result is obtained even in cases of rapidly growing nonlinearities, that is, when the growth of the nonlinearity surpasses the critical exponent of the Sobolev embedding theorem. Our methods rely on the energy analysis and the phase-plane angle analysis of the solutions for the associated singular ordinary differential equation.

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 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.

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 …

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.

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.

Uniqueness Of Positive Solutions For A Class Of Elliptic Boundary Value Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

Uniqueness of non-negative solutions conjectured in an earlier paper by Shivaji is proved. Our methods are independent of those of that paper, where the problem was considered only in a ball. Further, our results apply to a wider class of nonlinearities.

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Π_k-formulae of size n for which every Σ_k-formula has size exp Ω(n^1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σ_k-formula of size exp O(n^1/(k-1)). Thus our hierarchy theorem is the best possible.

On Determinism Versus Non-Determinism And Related Problems, Wolfgang J. Paul, Nicholas Pippenger, Endre Szemeredi, William T. Trotter

All HMC Faculty Publications and Research

We show that, for multi-tape Turing machines, non-deterministic linear time is more deterministic Turing machines (that receive their input on their work tape) require time Q(n2) to powerful than deterministic linear time. We also recognize non-palindromes of length n (it is easy to discuss the prospects for extending this result to see that time O(n log n) is. sufficient for a more general Turing machines. non-deterministic machine). 1. Introduction

Reduction Methods Via Minimax, Alfonso Castro

All HMC Faculty Publications and Research

Lecture notes in mathematics originally published in Differential Equations book series.

On Multiple Solutions Of Nonlinear Elliptic Equations With Odd Nonlinearities, Alfonso Castro, J. V. A. Gonçalves

All HMC Faculty Publications and Research

In this paper we stablish results on multiplicity of solutions for the boundary value problem where a e IR and f: R - IR is an odd continuous function.