Abstract Previous studies of search in channel graphs have assumed global search, for which the status of any link can be probed by the search algorithm at any time. We consider for the first time local search, for which only links to which an idle path from the source has already been established may be probed. We show that some well‐known channel graphs may require exponentially more probes, on average, when search must be local than when it may be global. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013

Suppose that a random n -bit number V is multiplied by an odd constant M ≥ 3, by adding shifted versions of the number V corresponding to the 1s in the binary representation of the constant M . Suppose further that the additions are performed by carry-save adders until the number of summands is reduced to two, at which time the final addition is performed by a carry-propagate adder. We show that in this situation the distribution of the length of the longest carry-propagation chain in the final addition is the same (up to terms tending to 0 as n → ∞) as when two independent n -bit numbers are added, and in particular the mean and variance are the same (again up to terms tending to 0). This result applies to all possible orders of performing the carry-save additions.

Frougny has presented a method that generalizes various "on-the-fly” operations that have been presented, mainly in connection with computer arithmetic. First, we shall trace the origin of this method to its source, which is the celebrated paper of Rabin and Scott that introduced the notion of nondeterminism and the power-set construction. Second, we shall show that an understanding of this origin may lead to great quantitative improvements in applications of the method. Finally, we shall show by a pathological example that the method as originally presented by Frougny may result in circuits that are larger, in terms of gates per step, by two exponentiations than those that are constructed as described in the present paper.

We consider crossbar switching networks with base b (that is, constructed from $b\times b$ crossbar switches), scale k (that is, with $b^k$ inputs, $b^k$ outputs, and $b^k$ links between each consecutive pair of stages), and depth l (that is, with l stages). We assume that the crossbars are interconnected according to the spider-web pattern, whereby two diverging paths reconverge only after at least k stages. We assume that each vertex is independently idle with probability q, the vacancy probability. We assume that $b\ge2$ and the vacancy probability q are fixed, and that k and $l=ck$ tend to infinity with ratio a fixed constant $c > 1$. We consider the linking probability Q (the probability that there exists at least one idle path between a given idle input and a given idle output). In a previous paper [Discrete Appl. Math., 37/38 (1992), pp. 437-450] it was shown that if $c\le2$, then the linking probability Q tends to 0 if $0 < q < q_c$ (where $q_c=1/b^{(c-1)/c}$ is the critical vacancy probability) and tends to $(1-\xi)^2$ (where $\xi$ is the unique solution of the equation $\bigl(1-q(1-x)\bigr)^b=x$ in the range $0 < x < 1$) if $q_c < q < 1$. In this paper we extend this result to all rational $c > 1$. This is done by using generating functions and complex-variable techniques to estimate the second moments of various random variables involved in the analysis of the networks.

Sweeney--Robertson--Tocher (SRT) division, as it was discovered in the late 1950s, represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. In this paper, the original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able to show that SRT division is ergodic, and is even Bernoulli, for all real divisors and dividends. With the Bernoulli property, we are able to use entropy to prove that the natural extensions of SRT division are isomorphic by way of the Kolmogorov--Ornstein theorem. We demonstrate how our methods and results can be applied to a much larger class of division algorithms.

We show that if X and Y are integers independently and uniformly distributed in the set {1,...,N}, then the information lost in forming their product (which is given by the equivocation H(X,Y|XmiddotY)), is Theta(loglogN). We also prove two extremal results regarding cases in which X and Y are not necessarily independently or uniformly distributed. First, we note that the information lost in multiplication can of course be 0. We show that the condition H(X,Y|XmiddotY)=0 implies 2log2N-H(X,Y)=Omega(loglogN). Furthermore, if X and Y are independent and uniformly distributed on disjoint sets of primes, it is possible to have H(X,Y|XmiddotY)=0 with log2N-H(X) and log2N-H(Y) each O(loglogN). Second, we show that no matter how X and Y are distributed, H(X,Y|XmiddotY)=O(logN/loglogN). Furthermore, there are distributions (in which X and Y are independent and uniformly distributed over sets of numbers having only small and distinct prime factors) for which we have H(X,Y|XmiddotY)=Omega(logN/loglogN)

If a sequence of independent unbiased random bits is fed into a finite automaton, it is straightforward to calculate the expected number of acceptances among the first n prefixes of the sequence. This paper deals with the situation in which the random bits are neither independent nor unbiased, but are nearly so. We show that, under suitable assumptions concerning the automaton, if the difference between the entropy of the first n bits and n converges to a constant exponentially fast, then the change in the expected number of acceptances also converges to a constant exponentially fast. We illustrate this result with a variety of examples in which numbers following the reciprocal distribution, which governs the significands of floating-point numbers, are recoded in the execution of various multiplication algorithms.

SRT division, as it was discovered in the late 1950s represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. The original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able to show that SRT division is ergodic, and is even Bernoulli, for all real divisors and dividends. With the Bernoulli property, we are able to use entropy to prove that the natural extensions of SRT division are isomorphic by way of the Kolmogorov-Ornstein theorem. We demonstrate how our methods and results can be applied to a much larger class of division algorithms.

Let /spl rho/ denote the density matrix of a quantum state having n parts 1, ..., n. For I/spl sube/N={1, ..., n}, let /spl rho//sub I/=Tr/sub N/spl bsol/I/(/spl rho/) denote the density matrix of the state comprising those parts i such that i/spl isin/I, and let S(/spl rho//sub I/) denote the von Neumann (1927) entropy of the state /spl rho//sub I/. The collection of /spl nu/=2/sup n/ numbers {S(/spl rho//sub I/)}/sub I/spl sube/N/ may be regarded as a point, called the allocation of entropy for /spl rho/, in the vector space R/sup /spl nu//. Let A/sub n/ denote the set of points in R/sup /spl nu// that are allocations of entropy for n-part quantum states. We show that A~/sub n/~ (the topological closure of A/sub n/) is a closed convex cone in R/sup /spl nu//. This implies that the approximate achievability of a point as an allocation of entropy is determined by the linear inequalities that it satisfies. Lieb and Ruskai (1973) have established a number of inequalities for multipartite quantum states (strong subadditivity and weak monotonicity). We give a finite set of instances of these inequalities that is complete (in the sense that any valid linear inequality for allocations of entropy can be deduced from them by taking positive linear combinations) and independent (in the sense that none of them can be deduced from the others by taking positive linear combinations). Let B/sub n/ denote the polyhedral cone in R/sup /spl nu// determined by these inequalities. We show that A~/sub n/~=B/sub n/ for n/spl les/3. The status of this equality is open for n/spl ges/4. We also consider a symmetric version of this situation, in which S(/spl rho//sub I/) depends on I only through the number i=/spl ne/I of indexes in I and can thus be denoted S(/spl rho//sub i/). In this case, we give for each n a finite complete and independent set of inequalities governing the symmetric allocations of entropy {S(/spl rho//sub i/)}/sub 0/spl les/i/spl les/n/ in R/sup n+1/.

The 2-way quantum finite automaton introduced by Kondacs and Watrous [Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75] can accept nonregular languages with bounded error in polynomial time. If we restrict the head of the automaton to moving classically and to moving only in one direction, the acceptance power of this 1-way quantum finite automaton is reduced to a proper subset of the regular languages. In this paper we study two different models of 1-way quantum finite automata. The first model, termed measure-once quantum finite automata, was introduced by Moore and Crutchfield [Theoret. Comput. Sci., 237 (2000), pp. 275--306], and the second model, termed measure-many quantum finite automata, was introduced by Kondacs and Watrous [Proceedings of the38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75]. We characterize the measure-once model when it is restricted to accepting with bounded error and show that, without that restriction, it can solve the word problem over the free group. We also show that it can be simulated by a probabilistic finite automaton and describe an algorithm that determines if two measure-once automata are equivalent. We prove several closure properties of the classes of languages accepted by measure-many automata, including inverse homomorphisms, and provide a new necessary condition for a language to be accepted by the measure-many model with bounded error. Finally, we show that piecewise testable sets can be accepted with bounded error by a measure-many quantum finite automaton, introducing new construction techniques for quantum automata in the process.

If G = (V, E) is a graph, the incidence graphI (G) is the graph with vertices $V\cup E$ and an edge joining $v\in V$ and $e\in E$ when and only when v is incident with e in G. For G equal to K n (the complete graph on n vertices) or K n,n (the complete bipartite graph on n + n vertices), we enumerate the matchings (sets of edges, no two having a vertex in common) in I(G), both exactly (in terms of generating functions) and asymptotically. We also enumerate the equivalence classes of matchings (where two matchings are considered equivalent if there is an automorphism of G that induces an automorphism of I(G) that takes one to the other).

Let X be an unbiased random bit, let Y be a qubit. whose mixed state depends on X, and let the qubit Z be the result of passing Y through a depolarizing channel, which replaces Y with a completely random qubit with probability p. We measure the quantum mutual information between X and Y by T(X; Y)=S(X)+S(Y)-S(X, Y), where S(...) denotes von Neumann's (1948) entropy. (Since X is a classical bit, the quantity T(X; Y) agrees with Holevo's (1973) bound /spl chi/(X; Y) to the classical mutual information between X and the outcome of any measurement of Y.) We show that T(X; Z) /spl les/ (1-p)/sup 2/T(X; Y). This generalizes an analogous bound for classical mutual information due to Evans and Schulman (1993), and provides a new proof of their result.

A tree, being a connected acyclic graph, can be bicolored in two ways, which differ from each other by exchange of the colors. We shall say that a tree is equicolorable if these bicolorings assign the two colors to equal numbers of vertices. Labelled equicolored trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolorable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolorable is asymptotically just twice the probability that its vertices would be equicolored if they were assigned colors by independent unbiased coin flips. Our goal in this paper is the enumeration of unlabelled equicolorable trees (that is, trees up to isomorphism), both exactly (in terms of generating functions) and asymptotically. We treat both the rooted and unrooted versions of this problem and conclude that in either case the probability that a randomly chosen n-vertex unlabelled tree is equicolorable is asymptotically 1.40499... times as large as the probability that it would be equicolored if its vertices were assigned colors by independent unbiased coin flips.

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, ie., capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, UNKNOTTING PROBLEM is in NP. We also consider the problem, SPLITTING PROBLEM of determining whether two or more such polygons can be split, or continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it. We show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE. We also give exponential worst-case running time bounds for deterministic algorithms to solve each of these problems. These algorithms are based on the use of normal surfaces and decision procedures due to W. Haken, with recent extensions by W. Jaco and J. L. Tollefson.

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting entirely of idle vertices or to find a cut (separating the given input from the given output) consisting entirely of busy vertices. We shall also allow the search to fail to find either a path or a cut with some probability bounded by a parameter called the failure probability. This is to be accomplished by sequentially probing the idle-or-busy status of vertices, where the vertex chosen for each probe may depend on the outcome of previous probes. Thus, a search algorithm may be modeled as a decision tree. For average-case analysis, we assume that each vertex is independently idle with some fixed probability, called the vacancy probability (and therefore busy with the complementary probability). For one commonly studied channel graph type, the parallel graph, we show that the expected number of probes is at most proportional to the length of a path, irrespective of the vacancy probability, and even if the allowed failure probability is zero. Another type of channel graph that we study is the spider-web graph, which is superior to the parallel graph as regards linking probability (the probability that an idle path, rather than a busy cut, exists). For this graph, we give upper and lower bounds that grow exponentially with the length of a path, when the vacancy probability and failure probability are fixed appropriately. © 1999 John Wiley & Sons, Inc. Networks 33: 249–259, 1999

Shannon's notion of the entropy of a random variable is used to give simplified proofs of asymptotic formulas for the logarithms of the numbers of monotone Boolean functions and Horn (1951) functions, and for equivalent results concerning families of sets and closure operations.

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 worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.

It is shown that if a formula is constructed from noisy 2-input NAND gates, with each gate failing independently with probability E, then reliable computation can or cannot take place according as /spl epsiv/ is less than or greater than /spl epsiv//sub 0/=(3-/spl radic/7)/4=0.08856....

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted (that is, whether it is capable of being continuously deformed without self-intersection so that it lies in a plane). We show that this problem, UNKNOTTING PROBLEM, is in NP. We also consider the problem, SPLITTING PROBLEM, of determining whether two or more such polygons can be split (that is, whether they are capable of being continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it), and show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE.

The aspect of purity versus impurity that we address involves the absence versus presence of mutation: the use of primitives (RPLACA and RPLACD in Lisp, set-car! and set-cdr! in Scheme ) that change the state of pairs without creating new pairs.It is well known that cyclic list structures can be created by impure Lisp, but not by pure Lisp.In this sense, impure Lisp is "more powerful" than pure Lisp.If the inputs and outputs are restricted to be sequences of atomic symbols, however, this difference in computability disappears.We show that if the temporal sequence of input and output operations must be maintained (that is, if computations must be "on-line"), then a difference in complexity remains.We do this by comparing the power of pure and impure "Lisp machines."We show that what an impure Lisp machine does in n steps (executions of primitive operations), a pure Lisp machine can do in O(n log n) steps, and that in some cases ⍀(n log n) steps are necessary.

The aspect of purity versus impurity that we address involves the absence versus presence of mutation: the use of primitives (RPLACA and RPLACD in Lisp, set-car! and set-cdr! in Scheme) that change the state of pairs without creating new pairs. It is well known that cyclic list structures can be created by impure programs, but not by pure ones. In this sense, impure Lisp is more powerful than pure Lisp. If the inputs and outputs of programs are restricted to be sequences of atomic symbols, however, this difference in computability disappears. We shall show that if the temporal sequence of input and output operations must be maintained (that is, if computations must be online), then a difference in complexity remains: for a pure program to do what an impure program does in n steps, O(n log n) steps are sufficient, and in some cases Ω(n log n) steps are necessary.

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 Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.

Switching networks with probabilistic traffic are positioned prominently in communication engineering. Measures of performance for such a network include the blocking probability of the network and the time for the routing algorithm to establish communication paths. Although literature exists concerning blocking probability, little theoretical progress in efficient routing algorithms has been made. Since the network is under a probabilistic traffic, it is meaningful to measure the routing algorithm by its expected running time. In this paper, we consider routing algorithms for a class of networks known as series-parallel networks. We first prove a lower bound for the expected time for any routing algorithm to establish a communication path and then present an algorithm that has an expected time within a constant factor of the lower bound, thus establishing the optimality of the algorithm. © 1996 John Wiley & Sons, Inc.

Define f on the integers $n > 1$ by the recurrence $f( n ) = \min \{ n,\min _{m|n} 2f( m ) + 3f( n/m ) \}$. The function f has $f( n ) = n$ as its upper envelope, attained for all prime n. The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form $f( n ) \sim C( \log n )^{1 + 1/\gamma } $ for certain constants $\gamma $ and C, in the sense that for any $\varepsilon > 0$, the inequality $f( n ) \leq ( C + \varepsilon )( \log n )^{1 + 1/\gamma } $ holds for infinitely many n, while$f( n ) \leq ( C + \varepsilon )( \log \,n )^{1 + 1/\gamma } $ holds for only finitely many. In fact, $\gamma = 0.7878 \ldots $ is the unique real solution of the equation $2^{ - \gamma } + 3^{ - \gamma } = 1$, and $C = 1.5595 \ldots $ is given by the expression $C = \left( {\gamma \left( {2^{ - \gamma } \log 2^\gamma + 3^{ - \gamma } \log 3^\gamma } \right)^{1/\gamma } /\left( {\gamma + 1} \right)\left( {15^{ - \gamma } \log ^{\gamma + 1} \frac{5}{2} + 3^{ - \gamma } \sum _{5 \leq k \leq 7} \log ^{\gamma + 1} \frac{k + 1}{1} + \sum _{8 \leq k \leq 15} \log ^{\gamma + 1} \frac{k + 1}{1}} \right)^{1/\gamma } } \right)$. This paper also considers the function $f_0 $ defined by replacing the integers $n > 1$ with the reals $n > 1$ in the above recurrence: $f_0 (x)= \min \{ x,\inf _{1 < y < x} 2f_0 ( x/y ) + 3f_0 ( x/y ) \}$. The author shows that $f_0 ( x ) \sim C_0 ( \log \,x )^{1 + 1/\gamma } $, where $C_0 = 1.5586 \ldots $ is given by $C_0 = 6e ( 2^{ - \gamma } \log 2^{ - \gamma } + 3^{ - \gamma } \log 3^{ - \gamma } )^{1/\gamma } \left( {\gamma /\left( {\gamma + 1} \right)} \right)^{1 + 1/\gamma } $ and is smaller than C by a factor of 0.9994... .

The authors consider fault-tolerant circuit-switching networks under a random switch failure model. Three circuit-switching networks of theoretical importance—nonblocking networks, rearrangeable networks, and superconcentrators—are studied. The authors prove lower bounds for the size (the number of switches) and depth (the largest number of switches on a communication path) of such fault-tolerant networks and explicitly construct such networks with optimal size $\Theta ( n ( \log n )^2 )$ and depth $\Theta ( \log n )$.

We show how to construct, for each n, a system Sn with the following properties.(1) The system S'n has n inputs, n outputs, and O(n) components, each of which is of one of a fixed finite number of finitestate machines, and is connected to a fixed finite number of other components through cables, each of which carries signals from a fixed finite alphabet.(2) When some of the inputs, and an equal number of outputs, are "marked" (by the presentation of a certain signal), then after O(log n) steps (a time proportional to the "diameter" of the network) the system will establish a set of disjoint paths from the marked inputs to the marked outputs.The construction of these "self-routing superconcentrators" incorporates some methodological improvements in the exploitation of expanders that can also be used to improve results on self-routing non-blocking networks (due to Arora, Leighton and Maggs), faulttolerant packet-routing networks (due to Leighton and Maggs) and token-distribution algorithms (due to Peleg and Upfal).

Circuit-switching networks are used to support simultaneous (data, voice and image) communications across multiprocessor parallel systems, distributed computer systems, and telecommunication systems.Circuit-switching networks accomplish simultaneous communications by means of disjoint paths of electrical links and switches.In this paper, we shall consider fault-tolerant circuit-switching networks under a random switch failure model.Three circuit-switching net works of theoretical importance, non-blocking networks, rearrange able networks and superconcent raters, are studied.We prove lower bounds for the size (the number of switches) and depth (the largest number of switches on a communication path) of such faulttolerant networks.And we explicitly construct such networks with optimal sizes and depths.

Non-blocking networks have many applications in communications.Typical examples are telephone switching networks and communication networks among processors or between processors and memory

An upper bound asymptotic to $2n\log _e n$ is established for the number of comparators required in a network that classifies n values into two classes, each containing $n / 2$ values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to $(n / 2)\log _2 n$.)

The expected capacity of a class of sparse concentrators called modular concentrators is determined. In these concentrators, each input is connected to exactly two outputs, each output is connected to exactly three inputs, and the girth (the length of the shortest cycle in the connexion graph) is large. Two definitions of expected capacity are considered. For the first (which is due to Masson and Morris), it is assumed that a batch of customers arrive at a random set of inputs and that a maximum matching of these customers to servers at the outputs is found. The number of unsatisfied requests is negligible if customers arrive at fewer than one-half of the inputs, and it grows quite gracefully even beyond this threshold. The situation in which customers arrive sequentially is considered, and the decision as to how to serve each is made randomly, without knowledge of future arrivals. In this case, the number of unsatisfied requests is larger but still quite modest.

A proof is provided that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a network with noisy gates. This result was first stated by R.L. Dobrushin and S.I. Ortyukov (1977). However, the authors believe that the analysis given by Dobrushin and Ortyukov is not entirely correct. The authors establish the result by following the same steps and by replacing the questionable part of their analysis with entirely new arguments.>

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 n/sup 1/p+o(1)/, where p is the unique real number for which the L/sub p/ norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal q such that multiple carry-save addition circuits of depth (q+o(1)) log n could be constructed by combining BA units. On the basis of these optimal constructions of multiple carry-save adders, the shallowest known multiplication circuits are constructed.>

A new probabilistic failure model for networks of gates is formulated. Although this model has not been used previously, it supports the proofs of both the positive and negative results appearing in the literature. Furthermore, with respect to this new model, the complexity measures of both size and depth are affected by at most constant multiplicative factors when the set of functions that can be computed by gates is changed from one finite and complete basis to another, or when the bound on the failure probability of the gates is changed (within the limits allowed by the basis), or when the bound on the error probability of the network is changed (within the limits allowed by the basis and the failure probability of the gates).

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 shown that the probability that a vertex is occupied at the jamming limit tends to $(1 - 1/(d - 1)^{2/(d - 2)} )/2$ as the length of the shortest cycle through it tends to $\infty $. Also treated are graphs that have short cycles but for which every edge is in at most one cycle; in this way approximations are obtained to the occupancy probabilities for two-dimensional triangular, square and hexagonal lattices. Finally, a similar problem is treated in which edges rather than vertices are occupied, and the occupation of an edge prevents the later occupation of edges incident with it. In each case the solution gives the dynamic evolution of the occupancy probabilities, as well as their values at the jamming limit.

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 $\Omega (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 network while the degree will remain practically fixed. We therefore raise the question whether it is possible to avoid the connectivity requirements by slightly lowering our expectations. In many practical situations we may be willing to “lose” some correct processors and settle for cooperation between the vast majority of the processors. Thus motivated, we present a general simulation technique by which vertices (processors) in almost any network of bounded degree can simulate an algorithm designed for the complete network. The simulation has the property that although some correct processors may be cut off from the majority of the network by faulty processors, the vast majority of the correct processors will be able to communicate among themselves undisturbed by the (arbitrary) behavior of the faulty nodes. We define a new paradigm for distributed computing, almost-everywhere agreement, in which we require only that almost all correct processors reach consensus. Unlike the traditional Byzantine agreement problem, almost-everywhere agreement can be solved on networks of bounded degree. Specifically, we can simulate any sufficiently resilient Byzantine agreement algorithm on a network of bounded degree using our communication scheme described above. Although we “lose” some correct processors, effectively treating them as faulty, the vast majority of correct processors decide on a common value.

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} )$.

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 that it does not seem to predict quantitatively the limiting value of the failure probability or the ratio by which computation proceeds more slowly in the presence of failures.>

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.

Article Fault tolerance in networks of bounded degree Share on Authors: C Dwork IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile , D Peleg IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile , N Pippenger IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile , E Upfal IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 370–379https://doi.org/10.1145/12130.12169Online:01 November 1986Publication History 35citation451DownloadsMetricsTotal Citations35Total Downloads451Last 12 Months18Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Two variants of the concept "non-blocking" have been defined in the literature: "strictly" non-blocking and "wide-sense" non-blocking. Hitherto, only toy examples were known of connectors that are wide-sense non-blocking but not strictly non-blocking, and these examples are more expensive than comparable strictly non-blocking connectors. In this paper we show for the first time how wide-sense non-blocking connectors can be less expensive than comparable strictly non- blocking connectors. In the simplest case we show that strictly non-blocking n-connectors with depth 2 must have ~2(n 2) edges, but wide-sense non-blocking n-connectors with depth 2 can have O(n 3/2 (log n) I/2) edges.

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.

We show that many Boolean functions (including, in a certain sense, "almost all" Boolean functions) have the property that the number of noisy gates needed to compute them differs from the number of noiseless gates by at most a constant factor. This may be contrasted with results of von Neumann, Dobrushin and Ortyukov to the effect that (1) for every Boolean function, the number of noisy gates needed is larger by at most a logarithmic factor, and (2) for some Boolean functions, it is larger by at least a logarithmic factor.

Currently known parallel communication schemes allow n nodes interconnected by arcs (in such a way that each node meets only a fixed number of arcs) to transmit n packets according to an arbitrary permutation in such a way that (1) only one packet is sent over a given arc at any step, (2) at most 0(log n) packets reside at a given node at any time and (3) with high probability, each packet arrives at its destination within 0(log n) steps. We present and analyze a new parallel communication scheme that ensures that at most a fixed number of packets reside at a given node at any time.

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with πk-formula of size n for which every σk-formula has size exp ω(n1/(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(n1/(k−1)). Thus our hierarchy theorem is the best possible.

Algorithms are presented which modify logical networks of bounded fan-in to obtain functionally equivalent networks of bounded fan-m and fan-out, so that both size and depth are not increased by more than constant factors.

We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.

We show that the minimum possible size of an n-superconcentrator with depth 2k≥4 is θ(nλ(k, n)), where λ(k, .) is the inverse of a certain function at the k-th level of the primitive recursive hierarchy. It follows that the minimum possible depth of an n-superconcentrator with linear size is θ(β(n)), where β is the inverse of a function growing more rapidly than any primitive recursive function. Similar results hold for generalizers. We give a simple explicit construction for a (d1...dk)-generalizer with depth k and size (d1+...+dk)d1...dk. This is applied to give a simple explicit construction for a generalized n-connector with depth 2k−3 and size (2d1+3d2+...+3dk−1+2dk) d1...dk. These are the best explicit constructions currently available. We also show that, for each fixed k≥2, the minimum possible size of a generalized n-connector with depth k is Ω(n1+1/k) and 0((n log n)1+1/k).

The results of this paper concern the question of how fast machines with one type of storage media can simulate machines with a different type of storage media. Most work on this question has focused on the question of how fast one deterministic machine can simulate another. In this paper we shall look at the question of how fast a probabilistic machine can simulate another. This approach should be of interest in its own right, in view of the great attention that probabilistic algorithms have recently attracted.

An algorithm is given for routing in permutation networks-that is, for computing the switch settings that implement a given permutation. The algorithm takes serial timeO(n(logN)2) (for one processor with random access to a memory ofO(n) words) or parallel timeO((logn)3) (fornsynchronous processors with conflict-free random access to a common memory ofO(n) words). These time bounds may be reduced by a further logarithmic factor when all of the switch sizes are integral powers of two.

A general model is presented for synchronous protocols that resolve conflicts among message transmissions to a multiple-access broadcast channel. An information-theoretic method is used now to show that if only finitely many types of conflicts can be distinguished by the protocol, utilization of the channel at rates approaching capacity is impossible. A random-coding argument is used to show that if the number of conflicting transmissions can be determined (which requires distinguishing infinitely many types of conflicts) then utilization of the channel at rates arbitrarily close to capacity can be achieved.

This paper has three claims to interest. First, it combines comparative schematology with complexity theory. This combination is capable of distinguishing among Strong's “languages of maximal power,” a distinction not possible when comparative schematology is based on computability considerations alone, and it is capable of establishing exponential disparities in running times, a capability not currently possessed by complexity theory alone.

Let $y_1 , \cdots ,y_p $ be monomials over the indeterminates $x_1 , \cdots ,x_q $. For every $y = (y_1 , \cdots ,y_p )$ there is some minimum number $L(y)$ of multiplications sufficient to compute $y_1 , \cdots ,y_p $ from $x_1 , \cdots ,x_q $ and the identity 1. Let $L(p,q,N)$ denote the maximum of $L(y)$ over all y for which the exponent of any indeterminate in any monomial is at most N. We show that if $p = (N + 1^{o(q)} )$ and $q = (N + 1^{o(p)} )$, then $L(p,q,N) = \min \{ p,q\} \log N + H/\log H + o(H /\log H)$, where $H = pq\log (N + 1)$ and all logarithms have base 2.

The problem solved in this paper is the following. Let x1, ..., xn be indeterminates; let r1, ..., rk be simple radicals, by which is meant let r1, ..., rk be the square roots of rational functions of x1, ..., xn; and let f1, ..., fm be simple algebraic functions, by which is meant let f1, ..., fm be rational functions of r1, ..., rk and x1, ..., xn. What is the minimum possible cost of computing f1, ..., fm from x1, ..., xn, if rational operators have cost zero and square root extractions (the only irrational operations allowed) have cost one?

It is well known that time bounds for machines correspond closely to size bounds for networks, and that space bounds correspond to depth bounds. It is not known whether simultaneous time and space bounds correspond to simultaneous size and depth bounds. It is shown here that simultaneous time and "reversal" bounds correspond to simultaneous size and depth bounds, and that simultaneous time and space bounds correspond to simultaneous size and "width" bounds.

Various computational models (such as machines and combinational logic networks) induce various and, m general, different computational complexity measures Relations among these measures are established by studying the ways m which one model can "simulate" another It ts shown that a machine with k-dimensional storage tapes (respectively, with tree-structured storage media) can be simulated on-hne by a machine with onedimensional storage tapes m time O(n 2-ilk) (respectively, m time O(n2/log n)) An obhv:ous machine Is defined to be one whose head posmons, as functions of time, are independent of the input, and It Is shown that any machine with one-d~menslonal tapes can be simulated on-hne by an oblivious machine with two one-dimensional tapes in time O(n log n) All of these results are the best possible, at least insofar as on-hne simulation is concerned.By slmdar methods It is shown that n steps of the computation of an arbitrary machine with onedimensional tapes can be performed by a combinational logic network of cost O(n log n) and delay O(n)

The 2,3-trees that are optimal in the sense of having minimal expected number of nodes visited per access are characterized in terms of their “profiles”. The characterization leads directly to a linear-time algorithm for constructing a K-key optimal 2,3-tree for a sorted list of K keys. A number of results are derived that demonstrate how different in structure these optimal 2,3-trees are from their “average” cousins.

Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.

A problem with a demonstrable Ume-space trade-off Is exhibited The problem is to compile a straight-line program for a certain unmterprted expression; time ~s reckoned as the number of mstrucUons m the program, space as the number of registers referred to There are programs using linear space and linear tune, but any program using less than linear space uses more than linear rune KEY WORDS AND PHRASES time, space, pebble game, straight-line program, register allocauon CR CATEGORIES 5 23, 5 24, 5 25, 5 32

An n-connector is an acyclic directed graph having n inputs and n outputs and satisfying the following condition: given any one-to-one correspondence between inputs and distinct outputs, there exists a set of vertex-disjoint paths that join each input to the corresponding output. It is known that the minimum possible number of edges in an n-connector lies between lower and upper bounds that are asymptotic to $3n\log _3 n$ and $6n\log _3 n$ respectively. A generalized n-connector satisfies the following stronger condition: given any one-to-many correspondence between inputs and disjoint sets of outputs, there exists a set of vertex-disjoint trees that join each input to the corresponding set of outputs. It is shown that the minimum number of edges in a generalized n-connector is asymptotic to the minimum number in an n-connector.

An n-superconcentrator is an acyclic directed graph with n inputs and n outputs for which, for every $r \leqq n$, every set of r inputs, and every set of r outputs, there exists an r-flow (a set of r vertex-disjoint directed paths) from the given inputs to the given outputs. We show that there exist n-superconcentrators with $39n + O(\log n)$ (in fact, at most $40n$) edges, depth $O(\log n)$, and maximum degree (in-degree plus out-degree) 16.

Let M be a p-by-q matrix of non-negative integers. We shall consider the problem of obtaining the p rows of M by computations in which 1. the zero vector (0,...,0) and the q unit vectors (1,...,0),...,(0,...,1) are available at no cost; 2. the sum of two (not necessarily distinct) previously computed vectors is available at a cost of one "step". Such a computation is called an addition chain for M. Let l(M) denote the minimum possible number of steps in an addition chain for M. Let L(p, q, N) denote the maximum of l(M) over all p-by-q matrices M whose entries are drawn from {0, 1,...,N}.

In this paper we study the complexity of realizing a monotone but otherwise arbitrary Boolean function. We consider realizations by means of networks and formulae. In both cases the possibility exists that although a monotone function can always be realized in terms of monotone basis functions, a more economical realization may be possible if basis functions that are not themselves monotone are used. Thus, we have four cases, namely: 1. The cost of realizing a monotone function with a network over a universal basis. 2. The cost of realizing a monotone function with a network over a monotone basis. 3. The cost of realizing a monotone function with a formula over a universal basis. 4. The cost of realizing a monotone function with a formula over a monotone basis. For the first case, we obtain a complete solution to the problem. For the other three cases, we obtain improvements over previous results and come within a logarithmic factor or two of a complete solution.

Graphs that in a certain precise sense are rich in sets of vertex-disjoint paths are studied. Bounds are obtained on the minimum number of edges in such graphs, and these are used to deduce nonlinear lower bounds on the computational complexity of shifting, merging, and matching problems.

Our purpose in this paper is to establish some relationships between two areas pioneered by Shannon: information theory and the complexity of switching networks that realize Boolean functions. We investigate the following three questions. 1. How does the complexity of a function depend on the number of 1's and 0's in its truth table? 2. How does the complexity of an incompletely specified function depend on the number of unspecified entries in its truth table? 3. If we do not insist that a function be realized exactly, but allow a certain number of entries in its truth table to be changed, what reduction in complexity is possible? These questions are answered by combinatorial arguments, but in each case the answer admits an information-theoretic interpretation that renders it more memorable. This interpretation has only heuristic significance, however, and does not provide an alternate means of deriving our results.

For networks that exhibit neither concentration nor expansion, the well-known probabilistic model of C. Y. Lee is refined so as to take account of the dependence of events in different stages. For series-parallel networks, the refined model yields exact expressions for the point-to-point blocking probability. These expressions bear the same relationship to the refined model as the KittredgeMolina expressions do to Lee's model. Comparison between the two sets of expressions shows that Lee's model tends to overestimate the blocking probability. Asymptotic analysis of the new expressions leads to improved upper bounds on the cost: it is shown that a network that carriesNerlangs with a blocking probability at most\epsilon > 0can be built with6N \log_{2} N + O(N \log \log 1/\epsilon)contacts.

A concentration network is a contact switching network that provides a number of potential users (connected to its inputs) with access to a smaller number of equivalent resources (connected to its outputs). Its basic property is that any sufficiently small subset of the inputs can be simultaneously connected by disjoint paths to distinct outputs, although the particular outputs to which they are to be connected cannot, in general, be specified arbitrarily. We show that a strictly nonblocking concentration network must have at least3n \log_{3} n - O(n)contacts wherenis the number of connections to be established simultaneously.