Search

DNA based nanostructures and devices are becoming ubiquitous in nanotechnology with rapid advancements in theory and experiments in DNA self-assembly which have led to a myriad of DNA nanodevices. However, the modeling methods used by researchers in the field for design and analysis of DNA nanostructures and nanodevices have not progressed at the same rate. Specifically, there does not exist a formal system that can capture the spectrum of the most frequently intended chemical reactions on DNA nanostructures and nanodevices which have branched and pseudo-knotted structures. In this paper we introduce a graph rewriting system for modeling DNA nanodevices. We define pseudo-DNA nanostructures (\(\mathbf {PDN}\)s), which describe the sequence information and secondary structure of DNA nanostructures, but exclude modeling of tertiary structures. We define a class of labeled graphs called DNA graphs, that provide a graph theoretic representation of PDNs. We introduce a set of graph rewrite rules that operate on DNA graphs. Our DNA graphs and graph rewrite rules provide a powerful and expressive way to model DNA nanostructures and their reactions. These rewrite rules model most conventional reactions on DNA nanostructures, which include hybridization, dehybridization, base-stacking, and a large family of enzymatic reactions. A subset of these rewrite rules would likely be used for a basic graph rewrite system modeling most DNA devices, which use just DNA hybridization reactions, whereas other of our rewrite rules could be incorporated as needed for DNA devices for example enzymic reactions. To ensure consistency of our systems, we define a subset of DNA graphs which we call well-formed DNA graphs, whose strands have consistent \(5^\prime \) to \(3^\prime \) polarity. We show that if we start with an input set of well-formed DNA graphs, our rewrite rules produce only well-formed DNA graphs. We give four detailed example applications of our graph rewriting system on (1) Yurke et al. [82] DNA tweezer system, (2) Yurke et al. [77] catalytic hairpin-based triggered branched junctions, (3) Dirks and Pierce [17] HCR, and (4) Qian and Winfree [59] scalable circuit of seesaw gates. Finally, we have a working software prototype (DAGRS) that we have used to generate automatically well-formed DNA graphs using a basic rewriting rule set for some of the examples mentioned.

This paper gives improved parallel methods for several exact factorizations of some classes of symmetric positive definite (SPD) matrices. Our factorizations also provide us similarly efficient algorithms for exact computation of the solution of the corresponding linear systems (which need not be SPD), and for finding rank and determinant magnitude. We assume the input matrices have entries that are rational numbers expressed as a ratio of integers with at most a polynomial number of bits @b. We assume a parallel random access machine (PRAM) model of parallel computation, with unit cost arithmetic operations, including division, over a finite field Z"p, where p is a prime number whose binary representation is linear in the size of the input matrix and is randomly chosen by the algorithm. We require only bit precision O(n(@b+logn)), which is the asymptotically optimal bit precision for @b>=logn. Our algorithms are randomized, giving the outputs with high likelihood >=1-1/n^@W^(^1^). We compute LU and QR factorizations for dense matrices, and LU factorizations of sparse matrices which are s(n)-separable, reducing the known parallel time bounds for these factorizations from @W(log^3n) to O(log^2n), without an increase in processors (matching the best known work bounds of known parallel algorithms with polylog time bounds). Using the same parallel algorithm specialized to structured matrices, we compute LU factorizations for Toeplitz matrices and matrices of bounded displacement rank in time O(log^2n) with nloglogn processors, reducing by a nearly linear factor the best previous processor bounds for polylog times (however, these prior works did not generally require unit cost division over a finite field). We use this result to solve in the same bounds: polynomial resultant; and Pade approximants of rational functions; and in a factor O(logn) more time: polynomial greatest common divisors (GCD) and extended GCD; again reducing the best processor bounds by a nearly linear factor.

The usual assumption for proofs of the optimality of lossless encoding is a stationary ergodic source. Dynamic sources with non-stationary probability distributions occur in many practical situations where the data source is formed from a composition of distinct sources, for example, a document with multiple authors, a multimedia document, or the composition of distinct packets sent over a communication channel. There is a vast literature of adaptive methods used to tailor the compression to dynamic sources. However, little is known about optimal or near optimal methods for lossless compression of strings generated by sources that are not stationary ergodic. Here, we do not assume the source is stationary. Instead, we assume that the source produces an infinite sequence of concatenated finite strings s1…sn, where: (i) Each finite string si is generated by a sampling of a (possibly distinct) stationary ergodic source Si, and (ii) the length of each of the si is lower bounded by a function L(n) such that L(n)/log(n) grows unboundedly with the length n of all the text within s1…si. Thus each input string is a sequence of substrings generated by possibly distinct and unknown stationary ergodic sources. The optimal expected length of a compressed coding of a finite prefix s1…sk is ∑i=1kniHi, where ni is the length of si and Hi is the entropy of Si. We give a window-based LZ77-type method for compression that we prove gives an encoding with asymptotically optimal expected length. We give another LZ77-type method for compression where the expected time for encoding and decoding is nearly linear (approaching arbitrarily close to linear O(n) for large n). We also prove that this later method gives an encoding with asymptotically optimal expected length. In addition, give a dictionary-based LZ78-type method for compression, which takes linear time with small constant factors. This final algorithm also gives an encoding with asymptotically optimal expected length, assuming the Si are stationary ergodic sources that satisfy certain mixing conditions and L(n)⩾ne for some e>0.

This paper (see also [1]) extends the alternating Turing machine (A-TM) of Chandra, Kozen and Stockmeyer [2], the private and the blind alternating machines of Reif [3,4] to model multiplayer games of incomplete information. We use these machines to provide matching lower bounds for our decision algorithms described in our companion paper [5]. We also apply multiple person alternation to other machine types. We show that multiplayer games of incomplete information can be undecidable general. However, one form of incomplete information games that is decidable we term as hierarchical games (defined later in this paper). In hierarchical multiplayer games, each additional clique (subset of players with same information) increases the complexity of the outcome problem by a further exponential. Consequently, if a multiplayer game of incomplete information with k cliques has a space bound of S ( n ), then its outcome can be k repeated exponentials harder than games of complete information with the same space bound S ( n ). This paper proves that this exponential blow-up must occur in the worst case. We define TEAM-PRIVATE-PEEK and TEAM-BLIND-PEEK, extending the previous models of PEEK. These new games can be shown to be complete for their respective classes. We use these games to establish lower bounds on complexity of multiplayer games of incomplete information and blindfold multiplayer games. We analyze the time bounded alternating machines, and conclude that time is not a very critical resource for multiplayer alternation. We also show DQBF (a variant of QBF) to be complete in NEXPTIME .

{This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications, the matrices are symmetric and sparse : with O(n) non-zero entries. The problem has an efficient sequential solution in this case, requiring O(n2) work by use of the sparse Lanczos method. A major remaining open question is: to find a polylog time parallel algorithm with matching work bounds. Unfortunately, the sparse Lanczos method cannot be parallelized to faster than time Ω (n) using n processors. Let M(n) be the processor bound to multiply two n \times n matrices in O(log n) parallel time. Giesbrecht [G2] gave the best previous polylog time parallel algorithms for the characteristic polynomial of a dense matrix with O (M(n)) processors. There is no known improvement to this processor bound in the case where the matrix is sparse. Often, in addition to being symmetric and sparse, the matrix has a sparsity graph (which has edges between indices of the matrix with non-zero entries) that has small separators. This paper gives a new algorithm for computing the characteristic polynomial of a sparse symmetric matrix, assuming that the sparsity graph is s(n) -separable and has a separator of size s(n)=O(nγ) , for some γ , 0 < γ < 1 , that when deleted results in connected components of ≤α n vertices, for some 0 < α < 1 , with the same property. We derive an interesting algebraic version of Nested Dissection, which constructs a sparse factorization of the matrix A-λ In where A is the input matrix and In is the n \times n identity matrix. While Nested Dissection is commonly used to minimize the fill-in in the solution of sparse linear systems, our innovation is to use the separator structure to bound also the work for manipulation of rational functions in the recursively factored matrices. The matrix elements are assumed to be over an arbitrary field. We compute the characteristic polynomial of a sparse symmetric matrix in polylog time using P(n)(n+M(s(n)))≤ P(n)(n+ s(n) 2.376) processors, where P(n) is the processor bound to multiply two degree n polynomials in O(log n) parallel time using a PRAM (P(n) = O(n) if the field supports an FFT of size n but is otherwise O(nlog log n) [CK]. Our method requires only that a matrix be symmetric and non-singular (it need not be positive definite as usual for Nested Dissection techniques). For the frequently occurring case where the matrix has small separator size, our polylog parallel algorithm has work bounds competitive with the best known sequential algorithms (i.e., the Ω(n2) work of sparse Lanczos methods), for example, when the sparsity graph is a planar graph, s(n) ≤ O( \sqrt n ) , and we require polylog time with only P(n)n1.188 processors.

This paper discusses learning algorithms for ascertaining membership, inclusion, and equality in permutation groups. The main results are randomized learning algorithms which take a random generator set of a fixed group G ≤ S n as input. We discuss randomized algorithms for learning the concepts of group membership, inclusion, and equality by representing the group in terms of its strong sequence of generators using random examples from G . We present O ( n 3 log n ) time sequential learning algorithms for testing membership, inclusion and equality. The running time is expressed as a function of the size of the object set. ( G ≤ S n can have as many as n ! elements.) Our bounds hold for all input groups. We also introduce limited parallelism, and our lower processor bounds make our algorithms more practical. Finally, we show that learning two-groups is in class NC by reducing the membership, inclusion, and inequality problems to solving linear systems over GF (2). We present an O (log 3 n ) time learning algorithm using n ω processors for learning two-groups from examples (where n × n matrix product takes logarithmic time using n ω processors).

Given the n complex coefficients of a degree n-1 complex polynomial, we wish to evaluate the polynomial at a large number $m \ge n$ of points on the complex plane. This problem is required by many algebraic computations and so is considered in most basic algorithm texts (e.g., [A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974]). We assume an arithmetic model of computation, where on each step we can execute an arithmetic operation, which is computed exactly. All previous exact algorithms [C. M. Fiduccia, Proceeding} 4th Annual ACM Symposium on Theory of Computing, 1972, pp. 88--93; H. T. Kung, Fast Evaluation and Interpolation, Carnegie-Mellon, 1973; A. B. Borodin and I. Munro, The Computational Complexity of Algebraic and Numerical Problems, American Elsevier, 1975; V. Pan, A. Sadikou, E. Landowne, and O. Tiga, Comput. Math. Appl., 25 (1993), pp. 25--30] cost at least work $\Omega(\log^2 n)$ per point, and previously, there were no known approximation algorithms for complex polynomial evaluation within the unit circle with work bounds better than the fastest known exact algorithms. There are known approximation algorithms [V. Rokhlin, J. Complexity, 4 (1988), pp. 12--32; V. Y. Pan, J. H. Reif, and S. R. Tate, in Proceedings 32nd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 703--713] for polynomial evaluation at real points, but these do not extend to evaluation at general points on the complex plane. We provide approximation algorithms for complex polynomial evaluation that cost, in many cases, near constant amortized work per point. Let $k = \log(|P|/\epsilon)$, where |P| is the sum of the moduli of the coefficients of the input polynomial P(z). Let {\it ${\tilde{P}}(z_j)$ be an $\epsilon$-approx of $P(z)$} if $\epsilon$ upper bounds the modulus of the error of the approximation ${\tilde{P}}(z_j)$ at each evaluation point zj, that is, $|P(z_j)-{\tilde{P}}(z_j)| \le \epsilon;$ note that $\epsilon$ is an absolute error bound rather than a relative error bound. In many applications (particularly in signal processing) the evaluation points zj are fixed and require only polylogarithmic $k = \log(|P|/\epsilon) = O(\log^{O(1)} n)$; for these cases we get a surprising reduction in work by use of approximation algorithms, as compared to the fastest known exact algorithms. We $\epsilon$-approx complex degree n-1 polynomial evaluation at $m \ge n\log n/\log^2 k $ fixed points on or within the unit disk in the complex plane in amortized work O(log2 k) per point, which is O(log2 log n) for polylogarithmic k. If the m points are not fixed, then we have increased amortized work O(log2 k + log m) per point, which is O(log m) for polylogarithmic k and $m \ge n\log n/\log k,$ and is still substantially below the previous bound of $\Omega(\log^2 m)$ for known exact algorithms. We further reduce our amortized bounds for special sets of evaluation points widely used in signal processing applications. The chirp transform is equivalent to evaluating a complex degree n-1 polynomial at the chirp points, which are $\zeta^j, j = 0,\dots,m-1$, for some fixed complex number $\zeta.$ We $\epsilon$-approx complex degree $n-1$ polynomial evaluation at these $m$ chirp points, where $m \ge n \log n/\log^2 k$ and $|\zeta| \le 1$ % or (ii) $m \ge n$ and $|\zeta| \le $ a function that limits to $1$ %for %$k = o(n)$ and large $n$) in amortized work O(log k) per point, whereas the previous best bounds for exact evaluation (via the chirp transform) were $\Omega(\log m)$ per point [A. V. Aho, K. Steiglitz, and J. D. Ullman, SIAM J. Comput., 4 (1975), pp. 533--539]. Using instead a reduction to approximate real polynomial evaluation (by interpolation at the Chebyshev points), in total work O(n log k), we $\epsilon$-approx the evaluation of a degree n polynomial at the first n powers of the n'th root of unity, where $n' \ge \Omega(n^2/k), $ and $\epsilon$-approx the n-point DFT for certain inputs with descending coefficient magnitude. All of our results require polylogarithmic (that is, logO(1)n)depth with the same work bounds.We also provide a lower bound for a wide class of schemes for approximate evaluation of a degree n-1 polynomial on the unit circle; namely, we prove that if a scheme uses an approximation polynomial of degree k-1, then it can be convergent only over a small fraction O(k/n) of the unit circle. We believe this is the first lower bound of this sort proved, and the proof uses an interesting reduction to the approximation of a matrix product by a matrix of reduced rank.

We consider the problem of approximate solution x̄ of of a linear system Ax = b over the reals, such that ∥Ax̄ − b∥ ≤ ε ∥b∥, for a given ε, 0 < ε < 1. This is one of the most fundamental of all computational problems. Let κ(A) = ∥A∥ ∥A−1∥ be the condition number of the n × n input matrix A. Sparse, Diagonally Dominant (DD) linear systems appear very frequently in the solution of linear systems associated with PDEs and stochastic systems, and generally have polynomial condition number. While there is a vast literature on methods for approximate solution of sparse DD linear systems, most of the results are empirical, and to date there are no known proven linear bounds on the complexity of this problem. Using iterative algorithms, and building on the work of Vaidya [1] and Gremban et al. [2–4] we provide the best known sequential work bounds for the solution of a number of major classes of DD sparse linear systems. Let π = log(κ(A)ε). The sparsity graph of A is a graph whose nodes are the indices and whose edges represent pairs of indices of A with nonzero entries. The following results hold for a DD matrix A with nonzero off-diagonal entries of bounded magnitude: 1.(1) if A has a sparsity graph which is a regular d-dimensional grid for constant d, then our work is O(nπ2),2.(2) if A is a stochastic matrix with fixed s(n)-separable graph as its sparsity graph, then our work is O((n + s(n)2)π).The following results hold for a DD matrix A with entries of unbounded magnitude: 1.(3) if A is sparse (i.e., O(n) nonzeros), our work is less than O(n(π + log n))1.5,2.(4) if A has a sparsity graph in a family of graphs with constant size forbidden graph minors (e.g., planar graphs), then our work is bounded by O(n(π + log n)1+o(1)) in the case log n = o(log π) and O(n(π + log n))1+o(1) in the case log π = o(log n).We use approximate preconditioned iterations to compute a sequence of iterative improvements to the preconditioned linear system. For class (1) of matrices (and class (2) with s(n) = O(√n)), we construct in n) work preconditioners, which reduce the condition number of the resulting preconditioned linear system condition number to O(1); and our resulting total work bounds to approximately solve the linear systems are O(n), if π = O(1). For class (4), we are within a small increasing factor of these bounds.

In this paper, we examine the problem of incrementally evaluating algebraic functions. In particular, iff(x1,x2,?,xn)=(y1,y2,?,ym) is an algebraic problem, we consider answering on-line requests of the form “change inputxito valuev” or “what is the value of outputyj?” We first present lower bounds for some simply stated algebraic problems such as multipoint polynomial evaluation, polynomial reciprocal, and extended polynomial GCD, proving an ?(n) lower bound for the incremental evaluation of these functions. In addition, we prove two time-space trade-off theorems that apply to incremental algorithms for almost all algebraic functions. We then derive several general-purpose algorithm design techniques and apply them to several fundamental algebraic problems. For example, we give anO(n)time per request algorithm for incremental DFT. We also present a design technique for serving incremental requests using a parallel machine, giving a choice of either optimal work with respect to the sequential incremental algorithm or superfast algorithms withO(loglogn) time per request with a sublinear number of processors.

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2min magnitude, the root problem is to find all the roots off(z) up to specified precision 2−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog5nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n2log2nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log6nlogB) usingnprocessors.

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k−1)-dimensional spaceRk−1,f∶V→Rk−1, such that no hyperplane containsk points of {f(v)|v∈V}, and for eachv∈V−X, f(v) is in the convex hull of {f(w)| (v, w)∈E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovasz and Wigderson in “Rubber bands, convex embeddings and graph connectivity”,Combinatorica8 (1988), 91–102.

We present a parallel algorithm based on open ear decomposition to construct an embedding of a graph onto the plane or report that the graph is nonplanar. Our parallel algorithm runs on a CRCW PRAM in logarithmic time with a number of processors bounded by that needed for finding connected components in a graph and for performing bucket sort.

Given inputs x 1 ,…, x n , which are independent identically distributed random variables over a domain D , and an associative operation \to;, the probabilistic prefix computation problem is to compute the product x 1 \to; x 2 \to; … \to; x n and its n - 1 prefixes. Instances of this problem are finite state transductions on random inputs, the addition or subtraction of two random n -bit binary numbers, and the multiplication or division of a random n -bit binary number by a constant. The best known constant fan-in circuits for these arithmetic operations had logarithmic depth, linear size, and produce no errors. Furthermore, matching lower bounds for depth and size (up to constant factors between the upper and lower bounds) had previously been obtained for the case of constant fan-in circuits with no errors. We give arithmetic circuits for probabilistic prefix computation, which for these random arithmetic operations have constant fan-in, linear size, O (log log n ) depth, but error probability less than n −α for any given α > 0. For any constant fan-in circuits computing these random arithmetic operations with error probability n −α , we prove the circuit depth must be bounded from below by Ω(log log n ). Hence, we conclude our circuits have asymptotically optimal depth among circuits with error probability n −α . We also give error-free circuits for these random arithmetic operations with constant fan-in at all nodes but one, linear size, and O (log log n ) expected delay for their parallel evaluation.

A Threshold Circuit consists of an acyclic digraph of unbounded fanin, where each node computes a threshold function or its negation. This paper investigates the computational power of Threshold Circuits. A surprising relationship is uncovered between Threshold Circuits and another class of unbounded fanin circuits which are denoted Finite Field Z P ( n ) Circuits, where each node computes either multiple sums or products of integers modulo a prime P ( n ). In particular, it is proved that all functions computed by Threshold Circuits of size S ( n ) &#x2265 n and depth D(n) can also be computed by Z P(n) Circuits of size O ( S ( n ) log S ( n ) + nP ( n ) log P ( n )) and depth O ( D ( n )). Furthermore, it is shown that all functions computed by Z P ( n ) Circuits of size S ( n ) and depth D ( n ) can be computed by Threshold Circuits of size O ((1/&#x2208 2 )( S ( n ) log P ( n )) 1+&#x2208 ) and depth O ((1/&#x2208 5 ) D ( n )). These are the main results of this paper. There are many useful and quite surprising consequences of this result. For example, an integer reciprocal can be computed in size n O (1)M and depth O (1). More generally, any analytic function with a convergent rational polynomial power series (such as sine, cosine, exponentiation, square root, and logarithm) can be computed within accuracy 2 -nc , for any constant c , by Threshold Circuits of polynomial size and constant depth. In addition, integer and polynomial division, FFf, polynomial interpolation, Chinese Remaindering, all the elementary symmetric functions, banded matrix inverse, and triangular Toeplitz matrix inverse can be exactly computed by Threshold Circuits of polynomial size and constant depth. All these results and simulations hold for polytime uniform circuits. This paper also gives a corresponding simulation oflogspace uniform Z P ( n ) Circuits by logspace uniform Threshold Circuits requiring an additional multiplying factor of O (log log log P ( n ) depth. Finally, purely algebraic methods forlowerbounds for ZP(n) Circuits are developed. Using degree arguments, a Depth Hierarchy Theorem for Z P ( n ) Circuits is proved: for any S ( n ) &#x2265 n , D ( n ) = O ( S ( n ) c' ) for some constant c' P ( n ) where 6( S ( n )/ D ( n )) D ( n ) P ( n ) c' 2 n , there exist explicitly constructible functions computable by Z P ( n ) Circuits of size S ( n ) and depth D ( n ), but provably not computable by Z P ( n ) Circuits of size S ( n ) c and depth o D ( n )) for any constant c &#x2265 1.

Simulated annealing is a family of randomized algorithms for solving multivariate global optimization problems. Empirical results from the application of simulated annealing algorithms to certain hard problems including certain types of NP-complete problems demonstrate that these algorithms yield better results than known heuristic algorithms. But for the worst case input, the time bound can be exponential. In this paper, for the first time, we show how to improve the performance of simulated annealing algorithms by exploiting some special properties of the cost function to be optimized. In particular, the cost functions we consider are small-separable, with parameter s(n). We develop an algorithm we call “Nested Annealing” which is a simple modification of simulated annealing where we assign different temperatures to different regions. Simulated annealing can be shown to have expected run time 2Ω(n) whereas our improved algorithm has expected performance 2Os(n). Thus for example, in many vision and VLSI layout problem, for whichs(n=O(n), our time bound is 2O(n) rather than 2Ω(n).

The conventional Tile Assembly Model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. We describe a natural extension to TAM called the Probabilistic Tile Assembly Model (PTAM) to model the inherent probabilistic behavior in physically realized self-assembled systems. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile set. These rulers can then be used as components for construction of other complex structures. In TAM, a deterministic linear assembly of length N requires a tile set of cardinality at least N . In contrast, for any given N , we demonstrate linear assemblies of expected length N with a tile set of cardinality *** (logN ) and prove a matching lower bound of *** (logN ). We also propose a simple extension to PTAM called *** -pad systems in which we associate *** pads with each side of a tile, allowing abutting tiles to bind when at least one pair of corresponding pads match and prove analogous results. All our probabilistic constructions are free from co-operative tile binding errors and can be modified to produce assemblies whose probability distribution of lengths has arbitrarily small tail bounds dropping exponentially with a given multiplicative factor increase in number of tile types. Thus, for linear assembly systems, we have shown that randomization can be exploited to get large improvements in tile complexity at a small expense of precision in length.

This paper applies the parallel tree contraction techniques developed in Miller and Reif’s paper [Randomness and Computation, Vol. 5, S. Micali, ed., JAI Press, 1989, pp. 47’72] to a number of fundamental graph problems. The paper presents an $O(\log n)$ time and $n / \log n$ processor, a 0-sided randomized algorithm for testing the isomorphism of trees, and an $O(\log n)$ time, n algorithm for maximal subtree isomorphism and for common subexpression elimination. An O(log n) time, n-processor algorithm for computing the canonical forms of trees and subtrees is given. An Olog n time algorithm for computing the tree of 3-connected components of a graph, an $O(\log ^2 n)$ time algorithm for computing an explicit planar embedding of a planar graph, and an $O(\log ^3 n)$ time algorithm for computing a canonical form for a planar graph are also given. All these latter algorithms use only $n^{O(1)} $ processors on a Parallel Random Access Machine (PRAM) model with concurrent writes and concurrent reads.

We accelerate by a factor of log n and with no increase of the processor bound our previous parallel algorithm for path algebra computation in the case of the minimum cost path computation in an n -vertex graph and, more generally, wherever the path algebra has an order relation defined by its ⊕ operation. The acceleration is obtained by means of a novel technique of stream contraction.

Division is a fundamental problem for arithmetic and algebraic computation. This paper describes Boolean circuits (of bounded fan-in) for integer division (finding reciprocals) that have size $O(M(n))$ and depth $O(\log n \log \log n)$, where $M(n)$ is the size complexity of $O(\log n)$ depth integer multiplication circuits. Currently, $M(n)$ is known to be $O(\log n \log \log n)$, but any improvement in this bound that preserves circuit depth will be reflected by a similar improvement in the size complexity of our division algorithm. Previously, no one has been able to derive a division circuit with size $O(n \log^c n)$ for any c, and simultaneous depth less than $\Omega (\log^2 n)$. The circuit families described in this paper are logspace uniform; that is, they can be constructed by a deterministic Turing machine in space $O(\log n)$.The results match the best-known depth bounds for logspace uniform circuits, and are optimal in size.The general method of high-order iterative formulas is of independent ...

We present a parallel algorithm for pseudo-random number generation. Given a seed of n? truly random bits for any ? > 0, our algorithm generates n? pseuderandom bits for any c > 1. This takes poly-log time using n?? processors where ?? = k? for some fixed small constant k > 1. We show that the pseuds-random bits output by our algorithm can not be distinguished from truly random bits in parallel poly-log time using a polynomial number of processors with probability 1/2 + 1/nO(1) if the multiplicative inverse problem almost always can not be solved in RNC. The proof is interesting and is quite different from previous proofs for sequential pseudo-random number generators.Our generator is fast and its output is provably as effective for RNC algorithms as truly random bits. Our generator passes all the statistical tests in KNUTH[14].Moreover, the existence of our generator has a number of central consequences for complexity theory. Given a randomized parallel algorithm A (over a wide class of machine models such as parallel RAMS and fixed connection networks) with time bound T(n) and processor bound P(n), we show A can be simulated by a parallel algorithm with time bound T(n) + O((log n)(log log n)), processor bound P(n)n??, and only using n? truly random bits for any ? > 0.Also, we show that if the multiplicative inverse problem is almost always not in RNC, then RNC is within the class of languages accepted by uniform poly-log depth circuits with unbounded fan-in and strictly sub-exponential size ?? > 0 2n?.

A finite group G is commonly presented by a set of elements which generate G. We argue that for algorithmic purposes a considerably better presentation for a fixed group G is given by random generator set for G: a set of random elements which generate G. We bound the expected number of random elements requied to generate a given group G.

Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. It is ubiquitous in biological constructions at the cellular and molecular scale and has also been identified by nanoscientists as a fundamental method for building nano-scale structures. Recent years see convergent interest and efforts in studying self-assembly from mathematicians, computer scientists, physicists, chemists, and biologists. However most complexity theoretic studies of self-assembly utilize mathematical models with two limitations: 1) only attraction, while no repulsion, is studied; 2) only assembled structures of two dimensional square grids are studied. In this paper, we study the complexity of the assemblies resulting from the cooperative effect of repulsion and attraction in a more general setting of graphs. This allows for the study of a more general class of self-assembled structures than the previous tiling model. We define two novel assembly models, namely the accretive graph assembly model and the self-destructible graph assembly model, and identify one fundamental problem in them: the sequential construction of a given graph, referred to as Accretive Graph Assembly Problem ($\textsc{AGAP}$) and Self-Destructible Graph Assembly Problem ($\textsc{DGAP}$), respectively. Our main results are: (i) $\textsc{AGAP}$ is NP-complete even if the maximum degree of the graph is restricted to 4 or the graph is restricted to be planar with maximum degree 5; (ii) counting the number of sequential assembly orderings that result in a target graph ($\textsc{\#AGAP}$) is #P-complete; and (iii) $\textsc{DGAP}$ is PSPACE-complete even if the maximum degree of the graph is restricted to 6 (this is the first PSPACE-complete result in self-assembly). We also extend the accretive graph assembly model to a stochastic model, and prove that determining the probability of a given assembly in this model is #P-complete.

The topic of Partial Differential Equations (PDEs) is an interesting area where the techniques of discrete mathematics and numerical algorithms can be brought together to solve problems that would normally be considered more properly in the domain of continuous mathematics. We investigate the bit-complexity of discrete solutions to linear PDEs, which is a realistic measure for parallel computers such as the CONNECTION MACHINE (CM1) and MASPAR. We show that for a large class of linear PDEs satisfying some routine assumptions of the multigrid methods, the N point discretization of their solution can be compressed to only a constant number of bits per discretization point, without loss of information or introducing errors beyond the order of the discretization error. More specifically, we show that the bit-complexity of the compressed solution is O(N) for both storage space and the total number of operations. We also compute the compressed solution by a parallel algorithm using O(logN) time and N/logN bit-serial processors. The best previous bounds on the bit-complexity (for both sequential time and storage space) were at least NlogN; furthermore, the order of NlogN bit-serial processors were required to support the O(logN) parallel time in the known algorithms. We believe this is the first case where a linear or algebraic system can be provably compressed (i.e. the bit-complexity of storage of the compressed solution is less than the solution size) and also the first case where the use of data compression provably speeds up the time to solve the system (in the compressed form).

This paper presents several results on the weighted region optimal path problem. An often-used approach to approximately solve this problem is to apply a discrete search algorithm to a graph \(\mathcal{G}_\epsilon\) generated by a discretization of the problem; this graph guarantees to contain an e-approximation of an optimal path between given source and destination points. We first provide a discretization scheme such that the size of \(\mathcal{G}_\epsilon\) does not depend on the ratio between the maximum and minimum unit weights. This leads to the first e-approximation algorithm whose complexity is not dependent on the unit weight ratio. We also introduce an empirical method, called adaptive discretization method, that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. BUSHWHACK is a discrete search algorithm used for finding optimal paths in \(\mathcal{G}_\epsilon\). We added two heuristics to BUSHWHACK to improve its performance and scalability.

Given a univariate complex polynomial f(x) of degree n with rational coefficients expressed as a ratio of two integers >

Given a univariate polynomial f(z) of degree n with complex coefficients, whose real and imaginary parts can be expressed as a ratio of two integers less than 2/sup m/ in magnitude, the root problem is to find all the roots of f(z) up to specified precision 2/sup -/spl mu//. Assuming the arithmetic model for computation, we provide, for any /spl epsiv/>0, an algorithm which has complexity O(n/sup 1+/spl epsiv// log b), where b=m+/spl mu/. This improves on the previous best known algorithm for the problem which has complexity O(n/sup 2/ log b). We claim it that it follows from the fact that we can bound the precision required in all the arithmetic computations, that the complexity of our algorithm in the Boolean model of computation is O(n/sup 2+/spl epsiv//(n+b) log/sup 2/ b log log b). >

This paper gives a new algorithm for computing the characteristic polynomial of a symmetric sparse matrix. We derive an interesting algebraic version of nested dissection, which constructs a sparse factorization the matrix A-/spl lambda/ where A is the input matrix. While nested dissection is commonly used to minimize the fill-in in the solution of sparse linear systems, our innovation is to use the separator structure to bound also the work for manipulation of rational polynomials in the recursively factored matrices. We compute the characteristic polynomial sparse symmetric matrix in polylog time using O(n(n+P(s(n))))/spl les/O(n(n+s(n)/sup 2.376/)) processors, where the sparsity graph of the matrix has separator size s(n). Our method requires only that the matrix be symmetric and nonsingular (it need not be positive definite as usual for nested dissection techniques); we use perturbation methods to avoid singularities. For the frequently occurring case where the matrix has small separator size our polylog parallel algorithm requires work bounds competitive with the best known sequential algorithms (i.e. sparse Lanczos methods), for example: (1) when the sparsity graph is a planar graph, s(n)/spl les//spl radic/n, and we require only n/sup 2.188/ processors, and (2) in the case where the input matrix is b-banded, we require only O(nP(b))=O(n) processors, for constant b.

This paper introduces average case analysis of fully dynamic graph connectivity (when the operations are edge insertions and deletions). To this end we introduce the model of stochastic graph processes, i.e. dynamically changing random graphs with random equiprobable edge insertions and deletions, which generalizes Erdos and Renyi's 35 year-old random graph process. As the stochastic graph process continues indefinitely, all potential edge locations (in V × V) may be repeatedly inspected (and learned) by the algorithm. This learning of the structure seems to imply that traditional random graph analysis methods cannot be employed (since an observed edge is not a random event anymore). However, we show that a small (logarithmic) number of dynamic random updates are enough to allow our algorithm to re-examine edges as if they were random with respect to certain events (i.e. the graph “forgets” its structure). This short memory property of the stochastic graph process enables us to present an algorithm for graph connectivity which admits an amortized expected cost of O(log3n) time per update. In contrast, the best known deterministic worst-case algorithms for fully dynamic connectivity require n1/2 time per update.

Known polylog parallel algorithms for the solution of linear systems and related problems require computation of the characteristic polynomial or related forms, which are known to be highly unstable in practice. However, matrix factorizations of various types, bypassing computation of the characteristic polynomial, are used extensively in sequential numerical computations and are essential in many applications. This paper gives new parallel methods for various exact factorizations of several classes of matrices. We assume the input matrices are n × n with either integer entries of size ≤ 2no(1). We make no other assumption on the input. We assume the arithmetic PRAM model of parallel computation. Our main result is a reduction of the known parallel time bounds for these factorizations from O(log3n) to O(log2n). Our results are work efficient; we match the best known work bounds of parallel algorithms with polylog time bounds, and are within a log n factor of the work bounds for the best known sequential algorithms for the same problems. The exact factorizations we compute for symmetric positive definite matrices include: 1. recursive factorization sequences and trees, 2. LU factorizations, 3. QR factorizations, and 4. reduction to upper Hessenberg form. The classes of matrices for which we can efficiently compute these factorizations include:1. dense matrices, in time O(log2n) with processor bound P(n) (the number of processors needed to multiply two n × n matrices in O(log n time), 2. block diagonal matrices, in time O(log2b with P(b)n/b processors, 3. sparse matrices which are s(n)-separable (recursive factorizations only), in time O(log2n) with P(s(n)) processors where s(n) is of the form n γ for 0 4. banded matrices, in parallel time O((logn) log b) with P(b)n/b processors. Our factorizations also provide us similarly efficient algorithms for exact computation (given arbitrary rational matrices that need not be symmetric positive definite) of the following: 1. solution of the corresponding linear systems, 2. the determinant, 3. the inverse. Thus our results provide the first known efficient parallel algorithms for exact solution of these matrix problems, that avoids computation of the characteristic polynomial or related forms. Instead we use a construction which modifies the input matrix, which may initially have arbitrary condition, so as to have condition nearly 1, and then applies a multilevel, pipelined Newton iteration, followed by a similar multilevel, pipelined Hensel Lifting.

Parallel tree contraction has been found to be a useful and quite powerful tool for the design of a wide class of efficient graph algorithms. We propose a corresponding technique for the parallel solution of incremental problems. As our computational model, we assume a variant of the CRCW PRAM where we can dynamically activate processors by a forking operation.We consider a dynamic binary tree T of ≤ n nodes and unbounded depth. We describe a procedure, which we call the dynamic parallel tree contraction algorithm, which incrementally processes various parallel modification requests and queries:(1)parallel requests to add or delete leaves of T, or modify labels of internal nodes or leaves of T, and also(2) parallel tree contraction queries which require recomputingvalues at specified nodes. Each modification or query is with respect to a set of nodes U in T.Our dynamic parallel tree contraction algorithm is a randomized algorithm that takes O(log(|U|log n)) expected parallel time using O(|U|log n/log(|U|log n) processors. We give a large number of applications (with the same bounds), including:(a) maintaining the usual tree properties (such as number of ancestors, preorder, etc.),(b) Eulerian tour,(c) expression evaluation, (d) least common ancestor, and(e) canonical forms of trees. Previously, there where no known parallel algorithms for incrementally maintaining and solving such problems in parallel time less than T(log n).In deriving our incremental algorithms, we solve a key subproblem, namely a processor activation problem, within the same asymptotic bounds, which may be useful in the design of other parallel incremental algorithms. This algorithm uses an interesting persistent parallel data structures involving a non-trivial construction.In a subsequent paper, we apply our dynamic parallel tree contraction technique to various incremental graph problems: maintaining various properties, (such as coloring, minimum covering set, maximum matching, etc.). of parallel series graphs, outerplanar graphs, Helin networks, bandwidth-limited networks, and various other graphs with constant separator size.

This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n_n matrices over a fixed ground field. Let P(n) and M(n) be the PRAM processor bounds for O(log n) time multiplication of two degree n polynomials, and n_n matrices, respectively. Let T(n) be the time bounds, using M(n) processors, for testing if an n_n matrix is nonsingular, and if so, computing its inverse. We compute the rank R of a matrix in randomized parallel time O(log n+T(R) log R) using nP(n)+M(R) processors (P(n)+RP(R) processors for constant displacement rank matrices, e.g., Toeplitz matrices). We find a maximum linearly independent subset (MLIS) of an n-set of n-dimensional vectors in time O(T(n) log n) using M(n) randomized processors and we also give output-sensitive algorithms for this problem. Applications include output-sensitive algorithms for finding: (i) a size R maximum matching in an n-vertex graph using time O(T(R) log n) and nP(n) T(R)+RM(R) processors, and (ii) a maximum matching in an n-vertex bipartite graph, with vertex subsets of sizes n1 n2 , using time O(T(n1) log n) and nP(n) T(n1)+ n1 M(n1) processors. 2001 Academic Press

We give an algorithm for imbedding a graph G of n vertices onto an oriented surface of minimal genus g. If g > 0 then we also construct a forbidden subgraph of G which is homeomorphic to a graph of size exp(O(g)!) which cannot be imbedded on a surface of genus g-1. Our algorithm takes sequential time exp(O(g)!)nO(1). Since exp(O(g)!) = exp(exp(O(glog(g)))), our algorithm is polynomial time for genus g=O(loglog(n)/logloglog(n)). A simple parallel implementation of our algorithm takes parallel time (logn)O(1)+O(g)! using exp(O(g)!)nO(1) processors. We give also the smallest known upper bound, namely exp(O(g)!), on the number F(g) of homeomorphic distinct forbidden subgraphs for graph imbeddings onto a surface of genus g. The two best previous algorithms [Filotti, Miller, Reif,79] and [Robertson and Seymour,86] for graph imbedding onto a surface of genus g, required nO(g) and f(g)n2 sequential time, respectively. The work of [Robertson and Seymour,86] also gave a finite bound for F(g). However their proof spanned many papers and were highly nonconstructive; f(g) and F(g) were bounded by some (large) tower of exponents of g. Our work provides a distinct constructive approach giving considerably improved bounds for f(g) and F(g) and vastly simplified proofs. In particular, we use a “bootstrap” technique that uses a discovered forbidden subgraph for given genus g'

We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log2n) time withn1+?processors, for any ?0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2·log(m)?log(n)+O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton3/2+?, for any ?0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128?1147), which requiresn4randomized processors orn5deterministic processors.

This paper extends the authors' parallel nested dissection algorithm of [13] originally devised for solving sparse linear systems. We present a class of new applications of the nested dissection method, this time to path algebra computations (in both cases of single source and all pair paths), where the path algebra problem is defined by a symmetric matrix A whose associated graph G with n vertices is planar. We substantially improve the known algorithms for path algebra problems of that general class; this has further applications to maximum flow and minimum cut problems in an undirected planar network and to the feasibility testing of a multicommodity flow in a planar network.

We consider a restricted propositional dynamic logic, Strict Deterministic Propositional Dynamic Logic (SDPDL), which is appropriate for reasoning about deterministic well-structured programs. In contrast to PDL, for which the validity problem is known to be complete in deterministic exponential time, the validity problem for SDPDL is shown to be polynomial space complete. We also show that SDPDL is less expressive than PDL, and give a complete axiomatization for it. The results rely on structure theorems for models of satisfiable SDPDL formulas, and the proofs give insight into the effects of nondeterminism on intractability and expressiveness in program logics.

This paper introduces a class of 1 player games of perfect information, which we call complementing games;; the player is allowed moves which complement the value of successive plays. A complementing game is symmetric if all noncomplement moves are reversible (i.e., form a symmetric relation). These games are naturally related to a class of machines we call symmetric complementing machines. Symmetric nondeterministic machines were studied in [Lewis and Papadimitriou, 80]; they are identical to our symmetric complementing machines with complement moves allowed only on termination. (A companion paper to appear describes the computational complexity of symmetric complementing and alternating machines.) Of particular interest is the complexity class -&-Sgr;(

Two-player games of incomplete information have certain portions of positions which are private to each player and cannot be viewed by the opponent. Asymptotically optimal decision algorithms for space bounded games are provided. Various games of incomplete information are presented which are shown to be universal in the sense that they are the hardest of all reasonable games of incomplete information. The problem of determining the outcome of these universal games from a given initial position is shown to be complete in doubly exponential time. “Private alternating Turing machines” are defined to be a new type of alternating Turing machines related to games of incomplete information. The space complexity S(n) of these machines is characterized in terms of the complexity of deterministic Turing machines, with time bounds doubly exponential in S(n) . Blindfold games are restricted games in that the second player is not allowed to modify the common position. Asymptotically optimal decision algorithms for space bounded blindfold games are provided. Various blindfold games are also shown to have exponential space complete outcome problems and to be universal for reasonable blindfold games. “Blind alternating Turing machines” are defined to be private alternating Turing machines with restrictions similar to those in blindfold games. The space complexity of these machines is characterized in terms of the complexity of deterministic Turing machines with a single exponential increase in space bounds.

This paper concerns vertex connectivity in random graphs. We present results bounding the cardinality of the biggest k-block in random graphs of the Gn,p model, for any constant value of k. Our results extend the work of Erdos and Renyi and Karp and Tarjan. We prove here that Gn,p, with p⩾ c n , has a giant k-block almost surely, for any constant k>0. The distribution of the size of the giant k-block is examined. We provide bounds on this distribution which are very nearly tight. We furthermore prove here that the cardinality of the biggest k-block is greater than n-log n, with probability at least 1−1/(n2log n), for p⩾ c n and c>k+3.

A dynamic connectivity problem consists of an initial graph, and a sequence of operations consisting of graph modifications and graph connectivity tests. The size n of the problem is the sum of the maximum number of vertices and edges of the derived graph, plus the number of operations to be executed. Each graph modification is a deletion of either an edge or an isolated vertex. Each graph connectivity test is to determine if there exists a path in the current graph between two given vertices (the vertices can vary for distinct tests). The best previously known time for this dynamic connectivity problem was Ω(n 2 ). Our main result is an O(ng+n log n) time algorithm for the dynamic connectivity problem in the case of the maximum genus of the derived graph being g.

The problem of movement in two-dimensional Euclidean space that is bounded by a (not necessarily convex) polygon is considered. Movement is restricted to be along straight line segments, and the objective is to minimize the number of bends or "turns" in a path. Most past work on this problem has addressed the movement between a source point and a destination point. An O(n \ast \log (n)) time algorithm is presented for computing a data structure that represents the minimal-turn paths from a source point to all other points in the polygon. An advantage of this algorithm is that it uses relatively simple data structures and is practical to implement. Another advantage is that it is easily generalized to accommodate the movement of a disk of radius r > 0.

This paper assumes a parallel RAM (random access machine) model which allows both concurrent reads and concurrent writes of a global memory.The main result is an optimal randomized parallel algorithm for INTEGER_SORT (i.e., for sorting n integers in the range $[1,n]$). This algorithm costs only logarithmic time and is the first known that is optimal: the product of its time and processor bounds is upper bounded by a linear function of the input size. Also given is a deterministic sublogarithmic time algorithm for prefix sum. In addition this paper presents a sublogarithmic time algorithm for obtaining a random permutation of n elements in parallel. And finally, sublogarithmic time algorithms for GENERAL_SORT and INTEGER_SORT are presented. Our sub-logarithmic GENERAL_SORT algorithm is also optimal.

This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first visited before v in depth-first search order of G. We show that this problem, for undirected and directed graphs, is complete in deterministic polynomial time with respect to deterministic log-space reductions. This gives strong evidence that depth-first search ordering can be done neither in deterministic space (log n) c nor in parallel time (log n) c , for any constant c > 0.

We present a parallel algorithm for pseudorandom number generation. Given a seed of $n^\varepsilon $ truly random bits for any $\varepsilon > 0$, our algorithm generates $n^c $ pseudorandom bits for any $c > 1$. This takes poly-log time using $n^{\varepsilon '} $ processors where $\varepsilon ' = k\varepsilon $ for some fixed small constant $k > 1$. We show that the pseudorandom bits output by our algorithm cannot be distinguished from truly random bits in parallel poly-log time using a polynomial number of processors with probability $\frac{1}{2} + {1 / {n^{O(1)} }}$ if the Multiplicative Inverse Problem almost always cannot be solved in ${\bf RNC}$. The proof is interesting and is quite different from previous proofs for sequential pseudorandom number generators.Our generator is fast and its output is provably as effective for ${\bf RNC}$ algorithms as truly random bits. Our generator passes all the statistical tests in Knuth [14].Moreover, the existence of our generator has a number of central conseque...

A randomized algorithm that sorts on an N node network with constant valence in O (log N ) time is given. More particularly, the algorithm sorts N items on an N -node cube-connected cycles graph, and, for some constant k , for all large enough α , it terminates within kα log N time with probability at least 1 - N - α .

The most efficient previously known parallel algorithms for the inversion of a nonsingular n × n matrix A or solving a linear system Ax = b over the rational numbers require O(log2n) time and M(n)n processors [provided that M(n) processors suffice in order to multiply two n × n rational matrices in time O(logn)]. Furthermore, the known polylog arithmetic time algorithms for those problems are numerically unstable. In this paper we apply Newton's iteration and initially choose an approximate inverse matrix by following Ben-Israel. This quadratically convergent and numerically stable iterative method takes O(log2n) parallel time using M(n) processors to compute the inverse (within the relative precision 2−nc for a positive constant c) of an n × n rational matrix A with the condition number at most nd for a constant d. This is the optimum processor bound and by a factor of n improvement of the previously known processor bounds for polylogarithmic time matrix inversion. The algorithm does not require to precompute the condition number of the input matrix, but it just converges slower for ill-conditioned input matrices.

This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n×n matrices over a fixed ground field. Let P(n) and M(n) be the PRAM processor bounds for O(logn) time multiplication of two degree n polynomials, and n×n matrices, respectively. Let T(n) be the time bounds, using M(n) processors, for testing if an n×n matrix is nonsingular, and if so, computing its inverse. We compute the rankR of a matrix in randomized parallel time O(logn+T(R)logR) using nP(n)+M(R) processors (P(n)+RP(R) processors for constant displacement rank matrices, e.g., Toeplitz matrices). We find a maximum linearly independent subset (MLIS) of an n-set of n-dimensional vectors in time O(T(n)logn) using M(n) randomized processors and we also give output-sensitive algorithms for this problem. Applications include output-sensitive algorithms for finding: (i) a size R maximum matching in an n-vertex graph using time O(T(R)logn) and nP(n)/T(R)+RM(R) processors, and (ii) a maximum matching in an n-vertex bipartite graph, with vertex subsets of sizes n1⩽n2, using time O(T(n1)logn) and nP(n)/T(n1)+n1M(n1) processors.

Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. It is ubiquitous in biological constructions at the cellular and molecular scale and has also been identified by nanoscientists as a fundamental method for building nano-scale structures. Recent years have seen convergent interest and efforts in studying self-assembly from mathematicians, computer scientists, physicists, chemists, and biologists. However most complexity theoretical studies of self-assembly utilize mathematical models with two limitations: (1) only attraction, while no repulsion, is studied; (2) only assembled structures of two dimensional square grids are studied. In this paper, we study the complexity of the assemblies resulting from the cooperative effect of repulsion and attraction in a more general setting of graphs. This allows for the study of a more general class of self-assembled structures than the previous tiling model. We define two novel assembly models, namely the accretive graph assembly model and the self-destructible graph assembly model, and identify a fundamental problem in them: the sequential construction of a given graph. We refer to it as the Accretive Graph Assembly Problem (AGAP) and the Self-Destructible Graph Assembly Problem (DGAP), in the respective models. Our main results are: (i) AGAP is NP-complete even if the maximum degree of the graph is restricted to 4 or the graph is restricted to be planar with maximum degree 5; (ii) counting the number of sequential assembly orderings that result in a target graph (#AGAP) is #P-complete; and (iii) DGAP is PSPACE-complete even if the maximum degree of the graph is restricted to 6 (this is the first PSPACE-complete result in self-assembly). We also extend the accretive graph assembly model to a stochastic model, and prove that determining the probability of a given assembly in this model is #P-complete.

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines. In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S ( n ) space bounded k -player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S ( n ). Furthermore, S ( n ) space bounded k -player blindfold games have a deterministic space upper bound of k repeated exponentials of S ( n ). This paper proves that this exponential blow-up can occur. We also show that time bounded games do not exhibit such hierarchy. A T ( n ) time bounded blindfold multiplayer game, as well as a T ( n ) time bounded multiplayer game of incomplete information, has a deterministic space bound of T ( n ).

The most efficient known parallel algorithms for inversion of a nonsingular n × n matrix A or solving a linear system Ax = b over the rationals require O(log n)2 time and M(n)n0.5 processors (where M(n) is the number of processors required in order to multiply two n × n rational matrices in time O(log n).) Furthermore, all known polylog time algorithms for those problems are unstable: they require the calculation to be done with perfect precision; otherwise they give no results at all.This paper describes parallel algorithms that have good numerical stability and remain efficient as n grows large. In particular, we describe a quadratically convergent iterative method that gives the inverse (within the relative precision 2-nO(1)) of an n × n rational matrix A with condition ≤ n0(1) in O(log n)2 time using M(n) processors. This is the optimum processor bound and the factor n0.5 improvement of known processor bounds for polylog time matrix inversion. It is the first known polylog time algorithm that is numerically stable. The algorithm relies on our method of computing an approximate inverse of A that involves O(log n) parallel steps and n2 processors.Also, we give a parallel algorithm for solution of a linear system Ax = b with a sparse n × n symmetric positive definite matrix A. If the graph G(A) (which has n vertices and has an edge for each nonzero entry of A) is s(n)-separable, then our algorithm requires only O((log n)(log s(n))2) time and |E| + M(s(n)) processors. The algorithm computes a recursive factorization of A so that the solution of any other linear system Ax = b′ with the same matrix A requires only O(log n log s(n)) time and |E| + s(n)2 processors.