Digital Commons Network^™

Tree-Based Multicasting In Wormhole-Routed Irregular Topologies, Ran Libeskind-Hadas, Dominic Mazzoni '99, Ranjith Rajagopalan '99

All HMC Faculty Publications and Research

A deadlock-free tree-based multicast routing algorithm is presented for all direct networks, regardless of interconnection topology. The algorithm delivers a message to any number of destinations using only a single startup phase. In contrast to existing tree-based schemes, this algorithm applies to all interconnection topologies, requires only fixed-sized input buffers that are independent of maximum message length, and uses a single asynchronous flit replication mechanism. The theoretical basis of the technique used here is sufficiently general to develop other tree-based multicasting algorithms for regular and irregular topologies. Simulation results demonstrate that this tree-based algorithm provides a very promising means of …

Positive Solutions For A Concave Semipositone Dirichlet Problem, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

No abstract provided for this article

Average-Case Lower Bounds For Noisy Boolean Decision Trees, William Evans, Nicholas Pippenger

All HMC Faculty Publications and Research

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the …

A Minmax Principle, Index Of The Critical Point, And Existence Of Sign Changing Solutions To Elliptic Boundary Value Problems, Alfonso Castro, Jorge Cossio, John M. Neuberger

All HMC Faculty Publications and Research

In this article we apply the minmax principle we developed in [6] to obtain sign-changing solutions for superlinear and asymptotically linear Dirichlet problems.

We prove that, when isolated, the local degree of any solution given by this minmax principle is +1. By combining the results of [6] with the degree-theoretic results of Castro and Cossio in [5], in the case where the nonlinearity is asymptotically linear, we provide sufficient conditions for:

i) the existence of at least four solutions (one of which changes sign exactly once),

ii) the existence of at least five solutions (two of which change sign), and …

Convergence Of Random Walks On The Circle Generated By An Irrational Rotation, Francis E. Su

All HMC Faculty Publications and Research

Fix . Consider the random walk on the circle which proceeds by repeatedly rotating points forward or backward, with probability , by an angle . This paper analyzes the rate of convergence of this walk to the uniform distribution under ``discrepancy'' distance. The rate depends on the continued fraction properties of the number . We obtain bounds for rates when is any irrational, and a sharp rate when is a quadratic irrational. In that case the discrepancy falls as (up to constant factors), where is the number of steps in the walk. This is the first example of a sharp …

Newton's Cubic Roots, Lisette G. De Pillis

All HMC Faculty Publications and Research

No abstract included in this article