We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the majority of their influencers. We study the algorithmic properties of the fixed-point behaviour of such networks, showing that the problem of establishing whether individuals converge to stable opinions is PSPACE-complete.

Upper bounds are given for the complexity of two very natural randomized algorithms for finding the sink of an Acyclic Unique Sink Orientation (AUSO) of the n-cube. For Random-Edge, we obtain an upper bound of about 1.80n, improving upon the the previous upper bound of about 2n/nlog n obtained by Gärtner and Kaibel. For Random-Jump, we obtain an upper bound of about (3/2)n, improving upon the previous upper bound of about 1.72n obtained by Mansour and Singh. AUSOs provide an appealing combinatorial abstraction of linear programming and other computational problems such as finding optimal strategies for turn-based Stochastic Games.

Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A player's power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms. Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.

The existence of polynomial-time algorithms for the solution of parity games is a major open problem. The fastest known algorithms for the problem are randomized algorithms that run in subexponential time. These algorithms are all ultimately based on the randomized subexponential simplex algorithms of Kalai and of Matoušek, Sharir, and Welzl. Randomness seems to play an essential role in these algorithms. We use a completely different, and elementary, approach to obtain a deterministic subexponential algorithm for the solution of parity games. The new algorithm, like the existing randomized subexponential algorithms, uses only polynomial space, and it is almost as fast as the randomized subexponential algorithms mentioned above.

It is known that if P and NP are different then there is an infinite hierarchy of different complexity classes that lie strictly between them. Thus, if P ≠ NP, it is not possible to classify NP using any finite collection of complexity classes. This situation has led to attempts to identify smaller classes of problems within NP where dichotomy results may hold: every problem is either in P or is NP-complete. A similar situation exists for counting problems. If P ≠#P, there is an infinite hierarchy in between and it is important to identify subclasses of #P where dichotomy results hold. Graph homomorphism problems are a fertile setting in which to explore dichotomy theorems. Indeed, Feder and Vardi have shown that a dichotomy theorem for the problem of deciding whether there is a homomorphism to a fixed directed acyclic graph would resolve their long-standing dichotomy conjecture for all constraint satisfaction problems. In this article, we give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. Let H be a fixed directed acyclic graph. The problem is, given an input digraph G , determine how many homomorphisms there are from G to H . We give a graph-theoretic classification, showing that for some digraphs H , the problem is in P and for the rest of the digraphs H the problem is #P-complete. An interesting feature of the dichotomy, which is absent from previously known dichotomy results, is that there is a rich supply of tractable graphs H with complex structure.

Recursively-constructed couplings have been used in the past for mixing on trees. We show how to extend this technique to nontree-like graphs such as lattices. Using this method, we obtain the following general result. Suppose that G is a triangle-free graph and that for some $\degree \geq 3$, the maximum degree of G is at most $\degree$. We show that the spin system consisting of q-colorings of G has strong spatial mixing, provided $q > \alpha \degree-\gamma$, where $\alpha\approx 1.76322$ is the solution to $\alpha^\alpha=e$, and $\gamma = \frac{4\alpha^3-6\alpha^2-3\alpha+4}{2(\alpha^2-1)}\approx 0.47031$. Note that we have no additional lower bound on q or $\degree$. This is important for us because our main objective is to have results which are applicable to the lattices studied in statistical physics, such as the integer lattice $\zset^d$ and the triangular lattice. For these graphs (in fact, for any graph in which the distance-k neighborhood of a vertex grows subexponentially in k), strong spatial mixing implies that there is a unique infinite-volume Gibbs measure. That is, there is one macroscopic equilibrium rather than many. Our general result gives, for example, a ``hand proof' of strong spatial mixing for 7-colorings of triangle-free 4-regular graphs. (Computer-assisted proofs of this result were provided by Salas and Sokal [\textit{J. Stat. Phys}., 86 (1997), pp.\ 551--579] (for the rectangular lattice) and by Bubley, Dyer, Greenhill, and Jerrum [\textit{SIAM J. Comput.}, 29 (1999), pp.\ 387--400].) It also gives a hand proof of strong spatial mixing for 5-colorings of triangle-free 3-regular graphs. (A computer-assisted proof for the special case of the hexagonal lattice was provided earlier by Salas and Sokal [\textit{J. Stat. Phys}., 86 (1997), pp.\ 551--579].) Toward the end of the paper we show how to improve our general technique by considering the geometry of the lattice. The idea is to construct the recursive coupling from a system of recurrences rather than from a single recurrence. We use the geometry of the lattice to derive the system of recurrences. This gives us an analysis with a horizon of more than one level of induction, which leads to improved results. We illustrate this idea by proving strong spatial mixing for $q=10$ on the lattice $\zset^3$. Finally, we apply the idea to the triangular lattice, adding computational assistance. This gives us a (machine-assisted) proof of strong spatial mixing for $10$-colorings of the triangular lattice. (Such a proof for $11$ colors was given by Salas and Sokal [\textit{J. Stat. Phys}., 86 (1997), pp.\ 551--579].) For completeness, we also show that our strong spatial mixing proof implies rapid mixing of Glauber dynamics for sampling proper colorings of neighborhood-amenable graphs. (It is known that strong spatial mixing often implies rapid mixing, but existing proofs seem to be written for $\zset^d$.) Thus our strong spatial mixing results give rapid

Recursively-constructed couplings have been used in the past for mixing on trees. We show for the first time how to extend this technique to nontree-like graphs such as the integer lattice. Using this method, we obtain the following general result. Suppose that G is a triangle-free graph and that for some /spl Delta/ /spl ges/ 3, the maximum degree of G is at most /spl Delta/. We show that the spin system consisting of q-colourings of G has strong spatial mixing, provided q > /spl alpha//spl Delta/, where /spl alpha/ /spl ap/ 1.76322 is the solution to /spl alpha//sup /spl alpha// = e. Note that we have no additional lower bound on q or /spl Delta/. This is important for us because our main objective is to have results which are applicable to the lattices studied in statistical physics such as the integer lattice /spl Zopf//sup d/ and the triangular lattice. For these graphs (in fact, for any graph in which the distance-k neighbourhood of a vertex grows sub-exponentially in k), strong spatial mixing implies that there is a unique infinite-volume Gibbs measure. That is, there is one macroscopic equilibrium rather than many. We extend our general result, obtaining, for example, the first "hand proof" of strong spatial mixing for 7-colourings of triangle-free 4-regular graphs. (Computer-assisted proofs of this result were provided by Salas and Sokal (1997) for the rectangular lattice and by Bubley et al. (1999)). The extension also gives the first hand proof of strong spatial mixing for 5-colourings of triangle-free 3-regular graphs. (A computer-assisted proof for the special case of the hexagonal lattice was provided by Salas and Sokal). Towards the end of the paper we show how to improve our general technique by considering the geometry of the lattice. The idea is to construct the recursive coupling from a system of recurrences rather than from a single recurrence. We use the geometry of the lattice to derive the system of recurrences. This gives us an analysis with a horizon of more than one level of induction, which leads to improved results. We illustrate this idea by proving strong spatial mixing for q = 10 on the lattice /spl Zopf//sup 3/. Finally, we apply the idea to the triangular lattice, adding computational assistance. This gives us the first (machine-assisted) proof of strong spatial mixing for 10-colourings of the triangular lattice. (Such a proof for 11 colours was given by Salas and Sokal.).

We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, $\lambda$, is at least 0.42 and that the capacity of every backoff protocol is at most 0.42. Thus, we show that backoff protocols have (provably) smaller capacity than full-sensing protocols. Finally, we show that the corresponding results, with the larger arrival bound of 0.531, also hold for every acknowledgment-based protocol.

Cooper, Dyer, and Frieze [J. Algorithms, 39 (2001), pp. 117--134] studied the problem of sampling H-colorings (nearly) uniformly at random. Special cases of this problem include sampling colorings and independent sets and sampling from statistical physics models such as the Widom--Rowlinson model, the Beach model, the Potts model and the hard-core lattice gas model. Cooper et al. considered the family of "cautious" ergodic Markov chains with uniform stationary distribution and showed that, for every fixed connected "nontrivial " graph H, every such chain mixes slowly. In this paper, we give a complexity result for the problem. Namely, we show that for any fixed graph H with no trivial components, there is unlikely to be any polynomial almost uniform sampler (PAUS) for H-colorings. We show that if there were a PAUS for the H-coloring problem, there would also be a PAUS for sampling independent sets in bipartite graphs, and, by the self-reducibility of the latter problem, there would be a fully polynomial randomized approximation scheme (FPRAS) for #BIS---the problem of counting independent sets in bipartite graphs. Dyer, Goldberg, Greenhill, and Jerrum have shown that #BIS is complete in a certain logically defined complexity class. Thus, a PAUS for sampling H-colorings would give an FPRAS for the entire complexity class. In order to achieve our result we introduce the new notion of sampling-preserving reduction which seems to be more useful in certain settings than approximation-preserving reduction.

In this paper we consider the following scenario. A set of n jobs with different threads is being run concurrently. Each job has an associated weight, which gives the proportion of processor time that it should be allocated. In a single time quantum, p threads of (not necessarily distinct) jobs receive one unit of service, and we require a rule that selects those p threads, at each quantum. Proportionate fairness means that over time, each job will have received an amount of service that is proportional to its weight. That aim cannot be achieved exactly due to the discretisation of service provision, but we can still hope to bound the extent to which service allocation deviates from its target. It is important that any scheduling rule be simple since the rule will be used frequently.We consider a variant of the Surplus Fair Scheduling (SFS) algorithm of Chandra, Adler, Goyal, and Shenoy. Our variant, which is appropriate for scenarios where jobs consist of multiple threads, retains the properties that make SFS empirically attractive but allows the first proof of proportionate fairness in a multiprocessor context. We show that when the variant is run, no job lags more than p H(n)-p+1 steps below its target number of services, where H(n) is the Harmonic function. Also, no job is over-supplied by more than O(1) extra services. This analysis is tight and it also extends to an adversarial setting, which models some situations in which the relative weights of jobs change over time.

Cooper, Dyer and Frieze studied the problem of sampling H-colourings (nearly) uniformly at random. Special cases of this problem include sampling colourings and independent sets and sampling from statistical physics models such as the Widom-Rowlinson model, the Beach model, the Potts model and the hard-core lattice gas model. Cooper et al. considered the family of "cautious" ergodic Markov chains with uniform stationary distribution and showed that, for every fixed connected "nontrivial" graph H, every such chain mixes slowly. In this paper, we give a complexity result for the problem. Namely, we show that for any fixed graph H with no trivial components, there is unlikely to be any Polynomial Almost Uniform Sampler (PAUS) for H-colourings. We show that if there were a PAUS for the H-colouring problem, there would also be a PAUS for sampling independent sets in bipartite graphs and, by the self-reducibility of the latter problem, there would be a Fully-Polynomial Randomised Approximation Scheme (FPRAS) for BIS --- the problem of counting independent sets in bipartite graphs. Dyer, Goldberg, Greenhill and Jerrum have shown that BIS is complete in a certain logically-defined complexity class. Thus, a PAUS for sampling H-colourings would give an FPRAS for the entire complexity class. In order to achieve our result we introduce the new notion of sampling-preserving reduction which seems to be more useful in certain settings than approximation-preserving reduction.

Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation guarantee. We improve the approximation guarantee of their work and present further improvements for some important NP-hard special cases of this problem (e.g., in the preemptive case where machines can suspend work on operations and later resume). We also present NC algorithms with improved approximation guarantees for some NP-hard special cases.

We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider,nusers generate messages for the channel according to a probability distribution. Raghavan and Upfal have given a protocol in which the expecteddelay(time to get serviced) of every message is O(logn) when messages are generated according to a Bernoulli distribution with generation rate up to about 1/10. Our main results are the following protocols: (a) one in which the expected average message delay is O(1) when messages are generated according to a Bernoulli distribution with a generation rate smaller than 1/e, and (b) one in which the expected delay of any message is O(1) for an analogous model in which users are synchronized (i.e., they agree about the time), there are potentially an infinite number of users, and messages are generated according to a Poisson distribution with generation rate up to 1/e. (Each message constitutes a new user.) To achieve (a), we first show how to simulate (b) usingnsynchronized users, and then show how to build the synchronization into the protocol.

We consider the problem of generating layouts of multilevel networks, in particular, switching, sorting, and interconnection networks, as compactly as possible on VLSI grids.Besides traditional interest in these problems motivated by interconnection topologies in parallel computing and switching circuits in telecommunications, there is renewed interest in such layouts in the context of ATM (Asynchronous Transfer Mode) switches.Our results improve on the existing area bounds for these networks by factors of up to three.

We consider the problem of fitting an n × n distance matrix D by a tree metric T. Let $\varepsilon$ be the distance to the closest tree metric under the $L_{\infty}$ norm; that is, $\varepsilon=\min_T\{\parallel T-D\parallel{\infty}\}$. First we present an O(n 2 ) algorithm for finding a tree metric T such that $\parallel T-D\parallel{\infty}\leq 3\varepsilon$. Second we show that it is ${\cal NP}$-hard to find a tree metric T such that $\parallel T-D\parallel{\infty} < \frac{9}{8}\varepsilon$. This paper presents the first algorithm for this problem with a performance guarantee.

The grid-area required by a sorting net for input vectors of length N is shown to be at least (N -1)"/2.Of 11 a sorting nets which use o(N2) comparators, the bitonic sorting net of Batcher has been known to have a layout of O(N"), but the hidden constant factor has not been investigated.A straightforward use of known techniques leads to a layout of grid-area 20.25N2.We present area-efficient layouts of the bitonic

Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x 1 ≤ x 2 ≤ … ≤ x m and n elements y 1 ≤ y 2 ≤ … ≤ y m , where n ≥ m. Batcher's odd-even merge yields the following upper bound: M(m,n) ≤ ½(m + n)log 2 m + O(n); in particular, M(n,n) ≤ n log 2 n + o(n) We prove the following lower bound that matches the upper bound above asymptotically as n ≥ m →∞; M(m,n) ≥ ½(m+n)log 2 m - O(m) in particular, M(n,n) ≥ n log 2 - O(n). Our proof technique extends to give similarily tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.

Span programs provide a linear algebraic model of computation. Lower Bounds for span programs imply lower bounds for formula size, symmetric branching programs and for contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a technique for proving lower bounds for monotone span programs, and prove a lower bound of Ω(m/sup 2.5/) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.

When distributed processes contend for a shared resource, we need a good distributed contention resolution protocol, e.g., for multiple-access channels (ALOHA, Ethernet), PRAM emulation, and optical routing. Under a stochastic model of request generation from n synchronous processes, Raghavan & Upfal (1995) have shown a protocol which is stable for a positive request rate; their main result is that for every resource request, its expected delay (time to get serviced) is O(log n). Assuming that the initial clock times of the processes are within a known bound of each other, we present a stable protocol, wherein the expected delay for each request is O(1). We derive this by showing an analogous result for can infinite number of processes, assuming that all processes agree on the time.

This paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms, a lower bound of about $(1 + \frac{9}{4(m + 1)}) \cdot n$ character comparisons is obtained. For general algorithms, a lower bound of about $(1 + \frac{2}{m + 3}) \cdot n$ character comparisons is obtained. These lower bounds complement an on-line upper bound of about $(1 + \frac{8}{3(m + 1)}) \cdot n$ comparisons obtained recently by Cole and Hariharan. The lower bounds are obtained by finding patterns with interesting combinatorial properties. It is also shown that for some patterns off-line algorithms can be more efficient than on-line algorithms.

The Fishspear priority queue algorithm is presented and analyzed. Fishspear is comparable to the usual heap algorithm in its worst-case running time, and its relative performance is much better in many common situations. Fishspear also differs from the heap method in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it potentially attractive for implementation of very large queues on paged memory systems.

Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x/sub 1/or=m. Batcher's odd-even merge yields the following upper bound: M(m,n)or=m to infinity :M(m,n)>or=/sup 1///sub 2/(m+n)log/sub 2/(m+1)-O(m); in particular, M(n,n)>or=nlog/sub 2/n-O(n). The authors' proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.>

We present an embedding of the complete binary tree with n leaves in the & x & mesh, for any n = 22m where m is a positive integer.

Paterson, Pippenger and Zwick have recently obtained a general theory that describes the optimal way in which given carry-save adders can be combined into carry-save networks. Their work produces, in particular, multiplication circuits of depth 3.71 log2 n (these circuits put out two numbers whose sum is the result of the multiplication).

It is shown that a random restriction leaving only a fraction in of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O( in /sup 1.63/). This is an improvement over previous results. The new exponent yields an increased lower bound of approximately n/sup 2.63/ for the de Morgan formula size of a function in P defined by A.E. Andreev (1987). This is the largest lower bound known, even for functions in NP.>

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

We consider schemes for recursively dividing a set of geometric objects by hyperplanes until all objects are separated. Such a binary partition is naturally considered as a binary tree where each internal node corresponds to a division and the leaves correspond to the resulting fragments of objects. The goal is to choose the hyperplanes properly so that the size of the binary partition, i.e., the number of resulting fragments of the objects, is minimized. We construct binary partitions of size Ο(n log n) for n edges in the plane, and of size Ο(n) if the edges are orthogonal. In three dimensions, we obtain binary partitions of size Ο(n2) for n planar facets, and prove a lower bound of Ω(n3/2). Two applications of efficient binary partitions are given. The first is an Ο(n2)-sized data structure for implementing a hidden-surface removal scheme of Fuchs, Kedem and Naylor [5]. The second application is in solid modelling: given a polyhedron described by its n faces, we show how to generate an Ο(n2)-sized CSG (constructive-solid-geometry) formula whose literals correspond to half-spaces supporting the faces of the polyhedron (see Peterson [9] and Dobkin et al. [3]). The best previous results for both of these problems were Ο(n3).

It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\alpha + m)$, where $\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time.

An algorithm is presented for finding a maximum-weight spanning tree of a set of n points in the Euclidean plane, where the weight of an edge (pi, pj) equals the Euclidean distance between the points pi and pj. The algorithm runs in time Ο (n logn) and requires Ο (n) space. If the points are vertices of a convex polygon (given in order along the boundary), then our algorithm requires only a linear amount of time and space. These bounds are the best possible in the algebraic computation-tree model. We also establish various properties of maximum spanning trees that can be exploited to solve other geometric problems.

A universal chain of order m for a metric space S is a sequence of $m - 1$ real numbers such that any multiset of m points from S can be sequenced so that the distances between successive points are no larger than the corresponding numbers in the chain. The length of a chain is the sum of its numbers. Upper and lower bounds are proved for the lengths of universal chains for the unit interval, unit square and for higher dimensions. Applications to wiring layouts in circuit boards are presented.

A monotonic priority set is a new data structure which supports maximum-finding and deletions over a set of weighted points in the plane. Global updates to the weights can also be made, incrementing the weights of all points above a given threshold in one of the coordinates. The weights are assumed to be always monotonic in both coordinates. An efficient implementation of this structure is presented and two main applications are described. The first is to the problem of optimal assembly of code for computers with two kinds of jump instruction: long and short. The task in the second application is the implementation of a queuing discipline based on the ranks with respect to two different criteria.

The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.

The Fishspear priority queue algorithm is presented and analyzed. Fishspear makes fewer than 80% as many comparisons as heaps in the worst case, and its relative performance is even better in rnany common situations. The code itself embodies an unusual recursive structure which permits highly dynamic and data-dependent execution. Fishspear also differs from heaps in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it possibly attractive for implementation of very large queues on paged memory systems. (Details of the implementation are deferred to the full paper.)

The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the "Byzantine Generals" problem.

A property of Boolean functions of n variables is described and shown to imply lower bounds as large as $\Omega (n\log n)$ on the number of literals in any Boolean formula for any function with the property. Formulas over the full basis of binary operations $( \wedge , \oplus ,{\text{ etc.}})$ are considered. The lower bounds apply to all but a vanishing fraction of symmetric functions, in particular, to all threshold functions with sufficiently large threshold and to the “congruent to zero modulo k” function for $k > 2$. In the case $k = 4$, the bound is optimal.

Information is not transferred instantaneously; there is always a propagation delay before an output is available as an input to the next computational step. Propagation delay is a function of wire length, so we study the length of edges in planar graphs. We prove matching (to within a constant factor) upper and lower bounds on minimax edge length for four planar embedding problems for complete binary trees. (The results are summarized in Table 1.) Because trees are often subcircuits of larger circuits, these results imply general performance limits due to propagation delay. The results give important information for the popular technique of pipelining.

We consider the problem of finding a minimal cost layout of a tree in Euclidian d-space. A tree is an acyclic undirected edge-weighted graph, and a layout is an assignment of a point in d-dimensional Euclidian space to each of the nodes of the tree. The “length” of an edge in the layout is the “distance” between its endpoints as measured by some norm. The cost of an edge is its length times its weight, and the cost of the whole layout is the sum of the costs of all the edges. We assume the positions of certain nodes are fixed in advance, and we wish to place the remaining nodes so as to minimize the cost of the layout.

Let gk:{0,1}n+k → {0,1}, where n = 2k, be the binary function defined by gk(a1,···, ak, X0,···, xn-1) = x(a) where (a) is the natural number with binary representation a1,···, ak. This function models the reading operation in a random-access storage. In [1] Paul proved a 2n lower bound to the combinational complexity of gk. This correspondence derives a realization for gk in a circuit with 2n + 0(√n) gates and a depth asymptotic to k.

When selecting from, or sorting, a file stored on a read-only tape and the internal storage is rather limited, several passes of the input tape may be required. We study the relation between the amount of internal storage available and the number of passes required to select the Kth highest of N inputs. We show, for example, that to find the median in two passes requires at least Ω(N1/2) and at most O(N1/2 log N) internal storage. For probabilistic methods, Θ(N1/2) internal storage is necessary and sufficient for a single pass method which finds the median with arbitrarily high probability.

Every Boolean function of n arguments has a circuit of depth $n + 1$ over the basis $\{ f|f:\{ 0,1\} ^2 \to \{ 0,1\} \} $.

A unification algorithm is described which tests a set of expressions for unifiability and which requires time and space which are only linear in the size of the input.

Let C(n)k be the Boolean function of n variables that equals one iff the number of arguments equal to one is a multiple of k. It is shown that every Boolean expression for C(n)k, allowing all of the 16 binary connectives, has size exceeding εn log n/log log n, ε> 0. This result follows from a general criterion relating the minimum size expression for a Boolean function to the kinds of subfunctions obtainable through restriction. Lower bounds on formula size for several other functions are obtained. In some cases, the lower bounds are nearly achievable by known constructions.

The purpose of this paper is to establish the following result.

A Turing machine whose behavior is restricted so that each read-write head can change its direction only a bounded number of times is reversal-bounded. Here we consider nondeterministic multitape acceptors which are both reversal-bounded and also operate in linear time. Our main result shows that such an acceptor need have only three pushdown stores as auxiliary storage, each pushdown store need make only one reversal, and the acceptor can operate in real time.

We present algorithms which use only $O(\sqrt n )$ nonscalar multiplications (i.e. multiplications involving “x” on both sides) to evaluate polynomials of degree n, and proofs that at least $\sqrt n $ are required. These results have practical application in the evaluation of matrix polynomials with scalar coefficients, since the “matrix $ \times $ matrix” multiplications are relatively expensive, and also in determining how many multiplications are needed for polynomials with rational coefficients, since multiplications by integers can in principle be replaced by several additions.