Self-assembly is fundamental to both biological processes and nanoscience. Key features of self-assembly are its probabilistic nature and local programmability. These features can be leveraged to design better self-assembled systems. 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. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile set, where any tile type may appear more than once in the assembly. The tile complexity of a linear assembly is the cardinality of the tile set that produces it. These rulers can then be used as components for construction of other complex structures. While square assemblies have been extensively studied, many questions remain about fixed length linear assemblies, which are more basic constructs yet fundamental building blocks for molecular architectures. In this work, we extend TAM to take advantage of inherent probabilistic behavior in physically realized self-assembled systems by introducing randomization. We describe a natural extension to TAM called the probabilistic tile assembly model (PTAM). A restriction of the model, which we call the standard PTAM is considered in this report. Prior work in DNA self-assembly strongly suggests that standard PTAM can be realized in the laboratory. In TAM, a deterministic linear assembly of length $N$ requires a tile set of cardinality at least $N$. In contrast, we show various nontrivial probabilistic constructions for forming linear assemblies in PTAM with tile sets of sublinear cardinality, using techniques that differ considerably from existing assembly techniques. In particular, for any given $N$ we demonstrate linear assemblies of expected length $N$ with a tile set of cardinality $\Theta(\log N)$ using one pad per side of each tile. We prove a matching lower bound of $\Omega(\log N)$ on the tile complexity of linear assemblies of any given expected length $N$ in standard PTAM systems using one pad per side of each tile. We further demonstrate how linear assemblies can be modified to produce assemblies with sharp tail bounds on distribution of lengths by concatenating various assemblies together. In particular, we show that for infinitely many $N$ we can get linear assemblies with exponentially dropping tail distributions using $O(\log^3 N)$ tile types. We also propose a simple extension to PTAM called $\kappa$-pad systems in which we associate $\kappa$ pads with each side of a tile, allowing abutting tiles to bind when at least one pair of corresponding pads match. This gives linear assemblies of expected length $N$ with a $2$-pad (two pads per side of each tile) tile set of cardinality $\Theta(\frac{\log N}{\log \log N})$ for infinitely many $N$. We show that we cannot get smaller tile complexity by proving a lower bound of $\Omega(\frac{\log N}{\log \log N})$ for each $N$ on the cardinality of the $\kappa$-pad ($\kappa$-pads per side of each tile) tile set required to form linear assemblies of expected length $N$ in standard $\kappa$-pad PTAM systems for any positive integer $\kappa$. The techniques that we use for deriving these tile complexity lower bounds are notable as they differ from traditional Kolmogorov complexity based information theoretic methods used for lower bounds on tile complexity. Also, Kolmogorov complexity based lower bounds do not preclude the possibility of achieving assemblies of very small tile multiset cardinality for infinitely many $N$. In contrast, our lower bounds are stronger as they hold for every $N$, rather than for almost all $N$. All our probabilistic constructions are free from co-operative tile binding errors. 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 presents several results on some cost-minimizing path problems in polygonal regions. For these types of problems, an approach often used to compute approximate optimal paths is to apply a discrete search algorithm to a graph G(epsilon) constructed from a discretization of the problem; this graph is guaranteed to contain an epsilon-good approximate optimal path, i.e., a path with a cost within (1 + epsilon) factor of that of an optimal path, between given source and destination points. Here, epsilon > 0 is the user-defined error tolerance ratio. We introduce a class of piecewise pseudo-Euclidean optimal path problems that includes several non-Euclidean optimal path problems previously studied and show that the BUSHWHACK algorithm, which was formerly designed for the weighted region optimal path problem, can be generalized to solve any optimal path problem of this class. We also introduce an empirical method called the adaptive discretization method that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. It proceeds in multiple iterations, and in each iteration, it varies the approximation parameters and fine tunes the discretization.

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.

We discuss the problem of computing optimal paths on terrains for a mobile robot, where the cost of a path is defined to be the energy expended due to both friction and gravity. The physical model used by this problem allows for ranges of impermissible traversal directions caused by overturn danger or power limitations. The model is interesting and challenging, as it incorporates constraints found in realistic situations, and these constraints affect the computation of optimal paths. We give some upper- and lower-bound results on the combinatorial size of optimal paths on terrains under this model. With some additional assumptions, we present an efficient approximation algorithm that computes for two given points a path whose cost is within a user-defined relative error ratio. Compared with previous results using the same approach, this algorithm improves the time complexity by using 1) a discretization with reduced size, and 2) an improved discrete algorithm for finding optimal paths in the discretization. We present some experimental results to demonstrate the efficiency of our algorithm. We also provide a similar discretization for a more difficult variant of the problem due to less restricted assumptions.

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but narrow passages in a robot's configuration space create significant difficulty for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which boosts the sampling density inside narrow passages. The bridge test relies on simple tests of local geometry and can be implemented efficiently in high-dimensional configuration spaces. The strengths of the bridge test and uniform sampling complement each other naturally and are combined to generate the final hybrid sampling strategy. Our planner was tested on point robots and articulated robots in planar workspaces. Preliminary experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.

In this paper we discuss the problem of computing optimal paths on terrains for a mobile robot. The cost of a path is defined to be the energy expended due to both friction and gravity. The model allows for ranges of impermissible traversal directions caused by overturn danger or power limitations. This model is interesting and challenging as it incorporates constraints found in realistic situations and these constraints affect the computation of optimal paths. We give some upper and lower bound results on the combinatorial size of energy-minimizing paths on terrains. We also present an efficient approximation algorithm that computes for two given points a path whose cost is within a user-defined relative error ratio. Compared to previous results with the same approach, this algorithm improves the time complexity by using: (1) a discretization with reduced size, and (2) an improved discrete algorithm for finding optimal paths in the discretization. We present some preliminary experimental results to demonstrate the efficiency of our algorithm. We also provide a similar discretization for the same model but under less restricted assumptions.

In this paper we define a class of mechanical systems consisting of rigid objects (defined by linear or quadratic surface patches) connected by frictional contact linkages between surfaces. (This class of mechanisms is similar to the analytical engine developed by Babbage in the 1800s, except that we assume frictional surfaces instead of toothed gears.) We prove that a universal Turing Machine (TM) can be simulated by a (universal) frictional mechanical system in this class consisting of a constant number of parts. Our universal frictional mechanical system has the property that it can reach a distinguished final configuration through a sequence of legal movements if and only if the universal TM accepts the input string encoded by its initial configuration. There are two implications from this result. First, the robotic mover's problem is undecidable when there are frictional linkages. Second, a mechanical computer can be constructed that has the computational power of any conventional electronic computer and yet has only a constant number of mechanical parts. Previous constructions for mechanical computing devices (such as Babbage's analytical engine) either provided no general construction for finite state control or the control was provided by electronic devices (as was common in electromechanical computers such as Mark I subsequent to Turing's result). Our result seems to be the first to provide a general proof of the simulation of a universal TM via a purely mechanical mechanism. In addition, we discuss the universal frictional mechanical system in the context of an error model that allows an error up to $\epsilon$ in each mechanical operation. We first show that, for a universal TM M, a frictional mechanical system in this $\epsilon$-error model can be constructed such that, given any space bound S, the system can simulate the computation of M on any input string $\omega$ if M decides $\omega$ in space bound S, provided that $\epsilon < 2^{-cS}$ for some constant c. We also show that, for any universal TM M and space bound S, there exists a frictional mechanical system in the $\epsilon$-error model with $\epsilon = \Omega(1)$; it has O(S) parts and can simulate M on any input $\omega$ that M decides in space bound S.

DNA self-assembly is a methodology for the construction of molecular scale structures. In this method, artificially synthesized single stranded DNA self-assemble into DNA crossover molecules (tiles). These DNA tiles have sticky ends that preferentially match the sticky ends of certain other DNA tiles, facilitating the further assembly into tiling lattices. DNA self-assembly can, using only a small number of component tiles, provide arbitrarily complex assemblies. We describe various novel DNA tiles with properties that facilitate self-assembly and their visualization by imaging devices such as atomic force microscope. We discuss key theoretical and practical challenges of DNA self-assembly, as well as numerous potential applications. We briefly discuss the ongoing development of attachment chemistry from DNA lattices to various types of molecules, and consider application of DNA lattices. We also discuss bounds on the speed and error rates of the various types of self-assembly reactions, as well as methods that may minimize errors in self-assembly.

The first main result of this paper is a novel nonuniform discretization approximation method for the kinodynamic motion-planning problem. The kinodynamic motion-planning problem is to compute a collision-free, time-optimal trajectory for a robot whose accelerations and velocities are bounded. Previous approximation methods are all based on a uniform discretization in the time space. On the contrary, our method employs a nonuniform discretization in the configuration space (thus also a nonuniform one in the time space). Compared to the previously best algorithm of Donald and Xavier, the running time of our algorithm reduces in terms of $1/\varepsilon$, roughly from $O((1/\varepsilon)^{6d-1})$ to $O((1/\varepsilon)^{4d-2})$, in computing a trajectory in a d-dimensional configuration space, such that the time length of the trajectory is within a factor of $(1+\varepsilon)$ of the optimal. More importantly, our algorithm is able to take advantage of the obstacle distribution and is expected to perform much better than the analytical result. This is because our nonuniform discretization has the property that it is coarser in regions that are farther from all obstacles. So for situations where the obstacles are sparse, or the obstacles are unevenly distributed, the size of the discretization is significantly smaller. Our second main result is the first known polynomial-time approximation algorithm for the curvature-constrained shortest-path problem in three and higher dimensions. We achieved this by showing that the approximation techniques for the kinodynamic motion-planning problem are applicable to this problem.

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 z j , 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 z j 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(log 2 k ) per point, which is O(log 2 log n) for polylogarithmic k. If the m points are not fixed, then we have increased amortized work O(log 2 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, log O(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.

In this paper, we present a framework for synthesizing I/O efficient out-of-core programs for block recursive algorithms, such as the fast Fourier transform (FFT) and block matrix transposition algorithms. Our framework uses an algebraic representation which is based on tensor products and other matrix operations. The programs are optimized for the striped Vitter and Shriver's two-level memory model in which data can be distributed using various cyclic(B) distributions in contrast to the normally used physical track distribution cyclic(B/sub d/), where B/sub d/ is the physical disk block size. We first introduce tensor bases to capture the semantics of block-cyclic data distributions of out-of-core data and also data access patterns to out-of-core data. We then present program generation techniques for tensor products and matrix transposition. We accurately represent the number of parallel I/O operations required for the synthesized programs for tensor products and matrix transposition as a function of tensor bases and data distributions. We introduce an algorithm to determine the data distribution which optimizes the performance of the synthesized programs. Further, we formalize the procedure of synthesizing efficient out-of-core programs for tensor product formulas with various block-cyclic distributions as a dynamic programming problem. We demonstrate the effectiveness of our approach through several examples. We show that the choice of an appropriate data distribution can reduce the number of passes to access out-of-core data by as large as eight times for a tensor product and the dynamic programming approach can largely reduce the number of passes to access out-of-core data for the overall tensor product formulas.

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 constructed by 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. We present a number of asymptotically efficient algorithms that address, at least from the theoretical point of view, optimal lossless compression of dynamic sources. We assume the source produces an infinite sequence of concatenated finite strings generated by sampling a stationary ergodic source.

Potentially, data compression techniques may have a broad impact in computing not only by decreasing storage and communication costs, but also by speeding up computation. For many image processing applications, the use of data compression is so pervasive that we can assume the inputs and outputs are in a compressed domain, and it is intriguing to consider doing computations on the data entirely in the compressed domain. We speed up processing by doing computations, including dot product and convolution on vectors and arrays, in a compressed transform domain. To do this, we make use of sophisticated algebraic techniques for evaluation and interpolation of sparse polynomials. We illustrate the basic methodology by applying these techniques to image processing problems, and in particular to speed up the well known splatting algorithm for volume rendering. The splatting algorithm is one of the most efficient of existing high quality volume rendering algorithms; it takes as input three dimensional volume sample data of size N/sup 3/ and outputs an N/spl times/N image in O(N/sup 3/f) time, where f is a parameter known as footprint size (which often is hundreds of pixels in practice). Assuming that the original sample data and the resulting image are stored in the transform domain and can be lossily compressed by a factor /spl rho/ with small error, we show that the rendering of the image can be done entirely in the compressed transform domain in decreased time O(/spl rho/N/sup 3/ log N). Hence we obtain a significant speedup over the splatting algorithm when f/spl Gt//spl rho/ log N.

In earlier work we presented the k-error protocol, a technique for protecting a dynamic dictionary method from error propagation as the result of any k errors on the communication channel or compressed file. Here we further develop this approach and provide experimental evidence that this approach is highly effective in practice against a noisy channel or faulty storage medium. That is, for LZ2-based methods that "blow up" as a result of a single error, with the protocol in place, high error rates (with far more than the k errors for which the protocol was previously designed) can be sustained with no error propagation (the only corrupted bytes decoded are those that are part of the string represented by a pointer that was corrupted).

. Given the n complex coe#cients of a degree n - 1 complex polynomial, we wish to evaluate the polynomial at a large number m # 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, Proceedings 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 ## log 2 n) per point, and previously, the...

The problem of communication and computation in the presence of errors is difficult, and general solutions can be time consuming and inflexible (particularly when implemented with a prescribed error detection/correction). A reasonable approach is to investigate reliable communication in carefully selected areas of fundamental interest where specific solutions may be more practical than general purpose techniques. In this paper, we study the problem of error-resilient communication and computation in a particularly challenging area, adaptive lossless data compression, where the devastating effect of error propagation is a long-standing open problem that was posed in the papers of Lempel and Ziv in the late 1970s. In fact, the non-error resilience of adaptive data compression has been a practical drawback of its use in many applications. Protocols that require the receiver to request retransmission from the sender when an error is detected can be impractical for many applications where such two-way communication is not possible or is self-defeating (e.g., with data compression, retransmission may be tantamount to losing the data that could have been transmitted in the mean time). In addition, bits of encoded data that are corrupted while data is in storage will in general not be recoverable and may corrupt the entire decompressed file. By error resilience, we mean that even though errors may not be detected, there are strong guarantees that their effects will not propagate. Our main result is a provable error-resilient adaptive lossless data-compression algorithm which nevertheless maintains optimal compression over the usual input distributions (e.g., stationary ergodic sources). We state our result in the context of a more general model that we call dynamic dictionary communication, where a sender and receiver work in a "lock-step" cooperation to maintain identical copies of a dictionary D that is constantly changing. For lossless data compression, the dictionary stores a set of strings that have been seen in the past and data is compressed by sending only indices of strings over the channel. Other applications of our model include robotics (e.g., remote terrain mapping) and computational learning theory.

Summary form only given, as follows. Data compression algorithms have been widely used in many areas to meet the demand of storage and transfer of large size data. Most of the data compression algorithms regard the input as a sequence of binary numbers and represent the compressed data also as a binary sequence. However, in many areas such as programming languages (e.g. LISP and C) and compiler design, it is more desirable to have a compression algorithm which compresses a data structure while keeping a similar structure of the original data in the compressed form. In addition to reducing storage space, such compression also has the benefit of efficiently executing various operations (e.g. searching) in the compressed form. We study the problem of compressing a non-binary data structure (e.g. tree, undirected and directed graphs) in an efficient way while keeping a similar structure in the compressed form. To date, there has been no proven optimal algorithm for this problem. We use the idea of building LZW tree in LZW compression to compress a binary tree generated by a stationary ergodic source. The tree is parsed into subtrees using breadth first search and an optimal dictionary is constructed with each index pointing to a distinct subtree. We replace the parsed subtrees by dictionary indices to formed the compressed tree. We also extend our tree compression algorithm to compress undirected and directed acyclic graphs.

We present the first known case of one-dimensional and two-dimensional string matching algorithms for text with bounded entropy. Let n be the length of the text and m be the length of the pattern. We show that the expected complexity of the algorithms is related to the entropy of the text for various assumptions of the distribution of the pattern. For the case of uniformly distributed patterns, our one dimensional matching algorithm works in O(nlogm/(pm)) expected running time where H is the entropy of the text and p=1-(1-H/sup 2/)/sup H/(1+H)/. The worst case running time T can also be bounded by (n log m/p(m+/spl radic/V))/spl les/T/spl les/(n log m/p(m-/spl radic/V)) if V is the variance of the source from which the pattern is generated. Our algorithm utilizes data structures and probabilistic analysis techniques that are found in certain lossless data compression schemes.

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 describes techniques for massively parallel computation at the molecular scale, which we refer to as molecular parallelism.

Article Work efficient parallel solution of Toeplitz systems and polynomial GCD Share on Author: John H. Reif Department of Computer Science, Duke University Department of Computer Science, Duke UniversityView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 751–761https://doi.org/10.1145/225058.225293Online:29 May 1995Publication History 3citation328DownloadsMetricsTotal Citations3Total Downloads328Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we consider the problem of correlational learning and present algorithms to determine correlated objects.

Presents advanced data compression techniques for predicting stock markets behavior under widely accepted market models in finance. The techniques are applicable to technical analysis, portfolio theory, and nonlinear market models. The authors find that lossy and lossless compression techniques are well suited for predicting stock prices as well as market modes such as strong trends and major adjustments. They also present novel applications of multispectral compression techniques to portfolio theory, correlation of similar stocks, effects of interest rates, transaction costs and taxes.>

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

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.

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.

This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental importance to robotics, but their computational complexity has not previously been investigated. We provide evidence that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In particular, we prove the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP-hard even if B has no velocity modulus bound, where, in both cases, B has 6 degrees of freedom. To prove these results, we use a unique method of simulation of a Turing machine that uses time to encode configurations (whereas previous lower bound proofs in robotic motion planning used the system position to encode configurations and so required unbounded number of degrees of freedom). We also investigate a natural class of dynamic problems that we call asteroid avoidance problems : B, the object we wish to move, is a convex polyhedron that is free to move by translation with bounded velocity modulus, and the polyhedral obstacles have known translational trajectories but cannot rotate. This problem has many applications to robot, automobile, and aircraft collision avoidance. Our main positive results are polynomial time algorithms for the 2-D asteroid avoidance problem, where B is a moving polygon and we assume a constant number of obstacles, as well as single exponential time or polynomial space algorithms for the 3-D asteroid avoidance problem, where B is a convex polyhedron and there are arbitrarily many obstacles. Our techniques for solving these asteroid avoidance problems use “normal path” arguments, which are an intereting generalization of techniques previously used to solve static shortest path problems. We also give some additional positive results for various other dynamic movers problems, and in particular give polynomial time algorithms for the case in which B has no velocity bounds and the movements of obstacles are algebraic in space-time.

We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with (nonnecessarily convex) polyhedral obstacles. Prior to this work, the best known algorithm required double-exponential time. Given that the problem is known to be PSPACE-hard, the bound we present is essentially the best (in the worst-case sense) that can reasonably be expected.

We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required Ω(n 2 log n) time and O (n 2 ) space, where n denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in O ( n log n) time), we present an O(kn) time algorithm, where k denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only O(n) space and, given a source point s , produces an O(n) size data structure such that the distance between s and any other point x in the plane ( x ) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in O (1) time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk).

The advantage of optics is its capability of providing highly parallel operations in a three-dimensional space. In this paper, we propose optical architectures to execute various image compression techniques. We optically implement the following compression techniques: transform coding, vector quantization, video coding. We show many generally used transform coding methods, for example, the cosine transform, can be implemented by a simple optical system. The transform coding can be carried out in constant time. Most of this paper is concerned with an innovative optical system for vector quantization using holographic associative matching. Limitations of conventional vector quantization schemes are caused by a large number of sequential searches through a large vector space. Holographic associative matching provided by multiple exposure holograms can offer advantageous techniques for vector-quantization-based compression schemes. Photorefractive crystals, which provide high-density recording in real time, are used as our holographic media. The reconstruction alphabet can be dynamically constructed through training or stored in the photorefractive crystal in advance. Encoding a new vector can be carried out by holographic associative matching in constant time. An extension to interframe coding using optical block matching methods is also discussed.>

Further applications of random sampling techniques which have been used for deriving efficient parallel algorithms are presented by J. H. Reif and S. Sen [Proc. 16th International Conference on Parallel Processing, 1987]. This paper presents an optimal parallel randomized algorithm for computing intersection of half spaces in three dimensions. Because of well-known reductions, these methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane, and Euclidean minimal spanning tree. The algorithms run in time $T = O(\log n)$ for worst-case inputs and use $P = O(n)$ processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only polylogarithmic number of random bits and terminate in the claimed time bound with probability $1 - n^{ - \alpha } $ for any fixed $\alpha > 0$. They are also optimal in $P\cdot T$ product since the sequential time bound for all thes...

There are now a number of fundamental problems in computational geometry that have optimal algorithms on PRAM models. This paper presents randomized parallel algorithms that execute on an n-processor butterfly interconnection network in $O(\log n)$ time for the following problems of input size n: trapezoidal decomposition, visibility, triangulation, and two-dimensional convex hull. These algorithms involve tackling some of the very basic problems, like binary search and load balancing, that are taken for granted in PRAM models. Apart from a two-dimensional convex hull algorithm, these are the first nontrivial geometric algorithms that attain this performance on fixed connection networks. These techniques use a number of ideas from Flashsort that have to be modified to handle more difficult situations; it seems likely that they will have wider applications.

This paper presents a data compression algorithm capable of significantly reducing the amounts of information contained in multispectral and hyperspectral images. The loss of information ranges from a perceptually lossless level, achieved at 20-30:1 compression ratios, to a one where exploitation of the images is still possible (over 100:1 ratios). A one-dimensional transform coder removes the spectral redundancy, and a two-dimensional wavelet transform removes the spatial redundancy of multispectral images. The transformed images are subsequently divided into active regions that contain significant wavelet coefficients. Each active block is then hierarchically encoded using multidimensional bitmap trees. Application of reversible histogram equalization methods on the spectral bands can significantly increase the compression/distortion performance. Landsat Thematic Mapper data are used to illustrate the performance of the proposed algorithm.>

Studies have indicated that sorting comprises about 20% of all computing on mainframes. Perhaps the largest use of sorting in computing (particularly business computing) is the sort required for large database operations (e.g. required by joint operations). In these applications the keys are many words long. Since our sorting algorithm hashes the key (rather than compare entire keys as in comparison sorts such as quicksort), our algorithm is even more advantageous in the case of large key lengths; in that case the cutoff is much lower. In case that the compression ratio is high, which can be determined after building the dictionary, we just adopt the previous sorting algorithm, e.g. quick sort. The same techniques can be extended to other problems (e.g. computational geometry problems) to decrease computation by learning the distribution of the inputs.>

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

The notion of output uensitive parallel algorithms for linear algebra problems is formalised in this paper, and such algorithms are presented for finding the rank R of an n x n matrix in randomised parallel time O(log n + logs@ using d(nz + iU(R)) processors, and for finding a maximum linearly independent subset of an n-set of n-dimensional vectors in randomised parallel time O((log n) logz R) using d(n2 + RIW(R)) processors (R is the sise of the subset).Also, output sensitive R.AfC algorithms for some combinatorial problems are developed.The best WC algorithm known for finding a maximum linearly independent subset of an n-set of n-dimensional vectors is giv+ the randomised parallel time ie O(logs TZ) using d(~(n)) processors.Note thatthis problem k-likely harder than the problem of finding a baais for the space spanned by the input vectors.An output sensitive 7WC-algorithm for computing greatest common divisors of polynomials is developed.This result is due to the second author.A miuimum vertex cover in a bipartite graph and a minimum X-Y vertex separator in a digraph can be found in rartdornised parallel time 0(log2 n) using d(lf(n)) processors (n is the number of vertices).This result is due to the first author.Not e that this is the best complexity bound known for 'RhfC algorithms, and matches the best R.Afc complexity bounds for the associated deciuion problems.1

Kinodynamicplanmng attempts to solve a robot motion problem subject to simultaneous kinematic and dynamics constraints.In the general problem, ggven a robot system, we must find a minimal-time trajectory that goes from a start position and veloclty to a goal position and velocity while avoiding obstacles by a safety margur and respecting constraints cm velocity and acceleration.We consider the simplified case of a point mass under Newtoman mechanics.together with velocity and acceleration bounds.The point must be flown from a start to a goal, amidst polyhedral obstacles in 2D or 3D.Although exact sohztions to this problem are not known, we provide the first provably good approximation algorlthm, and show that it runs in polynomial time.

This paper presents a parallel algorithm for the solution of a linear system $A{\bf x} = {\bf b}$ with a sparse $n \times n$ symmetric positive definite matrix A, associated with the graph $G(A)$ that has n vertices and has an edge for each nonzero entry of A. If $G(A)$ has an $s(n)$-separator family and a known $s(n)$-separator tree, then the algorithm requires only $O(\log ^3 n)$ time and $(|E| + {{M(s(n)))} / {\log n}}$ processors for the evaluation of the solution vector ${\bf x} = A^{ - 1} {\bf b}$, where $|E|$ is the number of edges in $G(A)$ and $M(n)$ is the number of processors sufficient for multiplying two $n \times n$ rational matrices in time $O(\log n)$. Furthermore, for this computational cost the algorithm computes a recursive factorization of A such that the solution of any other linear system $A{\bf x} = {\bf b}'$ with the same matrix A requires only $O(\log ^2 n)$ time and $({{|E|} / {\log n}}) + s(n)^2 $ processors.

Optical computing has recently become a very active research field. The advantage of optics is its capability of providing highly parallel operations in a three dimensional space. The authors propose optical architectures to execute various image compression techniques. They optically implement the following compression techniques: transform coding; vector quantization; and interframe coding; They show many generally used transform coding methods, for example, the cosine transform, can be implemented by a simple optical system. The transform coding can be carried out in constant time. Most of this paper is concerned with a sophisticated optical system for vector quantization using holographic associative matching. Holographic associative matching provided by multiple exposure holograms can offer advantageous techniques for vector quantization based compression schemes. Photorefractive crystals, which provide high density recording in real time, are used as the holographic media. The reconstruction alphabet can be dynamically constructed through training or stored in the photorefractive crystal in advance. Encoding a new vector can be carried out by holographic associative matching in constant time. An extension to interframe coding is also discussed.>

The authors demonstrate the power of combining the techniques of algebraic computation with ones of numerical computation. They do this by improving the known methods for polynomial evaluation on a set of real points and for simulation of n charged particles on the plane. In both cases they approximate (rather than exactly compute) the solutions and do this by exploiting algebraic techniques of the algorithm design.>

Nested dissection is a method for solving large sparse systems of linear equations.The method is inherently parallelizable and efficient algorithms for parallel nested dissection (PND) exist for various parallel architectures.

recursive steps in the worst case and thus require at least the order of n time in their parallel im-We present parallel algorithms for computing all plementation, even if the number of available propair shortest paths in directed graphs.Our algocessors is not bounded.O(n) time and n2 procesrithm has time complexity O(j(n)/p + l(n) log n) sor bounds can indeed be achieved, for inst ante, on the PRAM using p processors, where I(n) is in the straightforward parallelization of the algolog non the EREW PRAM, log log n on the CRCW rithm of [Fl].(Here and hereafter we assume the PRAM, ~(n) is o(n3).On the randomized CRCW customary PRAM models of parallel computing PRAM we are able to achieve time complexity [KR].)0(n3/p + iog n) using p processors.NC algorithms are also available for this problem.However, they either need O(n3 log n) ope-

Flashsort [RV83,86] and Samplesort [HC83] are related parallel sorting algorithms proposed in the literature.Both utilize a sophisticated randomized sampling technique to form a splitter set, but Samplesort distributes the splitter set to each processor while Flashsort uses splitter-directed routing.In this paper we present B-Flashsort, a new batched-routing variant of Flashsort designed to sort N>P values using P processors connected in a d-dimensional mesh and using constant space in addition to the input and output.The key advantage of the Flashsort approach over Samplesort is a decrease in memory requirements, by avoiding the broadcast of the splitter set to all processors.The practical advantage of B-Ftashsort over Flashsort is that it replaces pipelined splitter-directed routing with a set of synchronous local communications and bounds recursion, while still being demonstrably efficient.The performance of B-Flashsort and Samplesort is compared using a parameterized analytic model in the style of [BLM+91 ] to show that on a d-dimensional toroidal mesh B-Flashsort improves on Samplesort when (N/P) < P/(cllog P +c2dP1/d +C3), for machine-dependent parameters c1, C2, and C3.Empirical confirmation of the analytical model is obtained through implementations on a MasPar MP-1 of Samplesort and two B-Fhtshsort variants.tEmail: prins(?cs.uric.

Further applications of random sampling techniques which have been used for deriving efficient parallel algorithms are presented by J. H. Reif and S. Sen [Proc. 16th International Conference on Parallel Processing, 1987]. This paper presents an optimal parallel randomized algorithm for computing intersection of half spaces in three dimensions. Because of well-known reductions, these methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane, and Euclidean minimal spanning tree. The algorithms run in time $T = O(\log n)$ for worst-case inputs and use $P = O(n)$ processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only polylogarithmic number of random bits and terminate in the claimed time bound with probability $1 - n^{ - \alpha } $ for any fixed $\alpha > 0$. They are also optimal in $P\cdot T$ product since the sequential time bound for all these problems is $\Omega (n\log n)$. The best known deterministic parallel algorithms for two-dimensional Voronoi-diagram and three-dimensional convex hull run in $O(\log ^2 n)$ and $O(\log ^2 n\log ^ * n)$ time, respectively, while using $O(n/\log n)$ and $O(n)$ processors, respectively.

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) \geq 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/\epsilon ^2 )(S(n)\log P(n))^{1 + \epsilon } )$ and depth $O((1/\epsilon ^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)} $ 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^{ - n^c } $, for any constant c, by Threshold Circuits of polynomial size and constant depth. In addition, integer and polynomial FFT, 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 of logspace 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 for lower bounds for $Z_{P(n)} $ Circuits are developed. Using degree arguments, a Depth Hierarchy Theorem for $Z_{P(n)} $ Circuits is proved: for any $S(n) \geq n$, $D(n) = O(S(n)^{c'} )$ for some constant $c' < 1$, and prime $P(n)$ where $6(S(n)/D(n)^{D(n)} < P(n) \leq 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 \geq 1$.

This paper presents a class of lossy data compression algorithms capable of encoding images so that the loss of information complies with certain distortion requirements. The developed algorithms are based on tree-structured vector quantizers (TSVQ). The first distortion controlled algorithm uses variable-size image blocks encoded on quad-tree data structures to encode efficiently image areas with different information content. Another class of distortion controlled algorithms presented is based on recursive quantization of error image blocks that represent the difference between the current approximation and the original block. The progressive compression properties of these algorithms are described. Compression/distortion performance using satellite images provided by NASA is better than that of the TSVQ algorithms at high bit rates.>

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)

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.

Article Free Access Share on An exact algorithm for kinodynamic planning in the plane Authors: John Canny Computer Science Division, University of California, Berkeley Computer Science Division, University of California, BerkeleyView Profile , Ashutosh Rege Computer Science Division, University of California, Berkeley Computer Science Division, University of California, BerkeleyView Profile , John Reif Computer Science Department, Duke University, Durham, N.C. Computer Science Department, Duke University, Durham, N.C.View Profile Authors Info & Claims SCG '90: Proceedings of the sixth annual symposium on Computational geometryMay 1990Pages 271–280https://doi.org/10.1145/98524.98584Published:01 May 1990Publication History 22citation29DownloadsMetricsTotal Citations22Total Downloads29Last 12 Months16Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The ray-tracing problem is considered for optical systems consisting of a set of refractive or reflective surfaces. It is assumed that the position and the tangent of the incident angle of the initial light ray are rational. The computability and complexity of the ray-tracing problems are investigated for various optical models. The results show that, depending on the optical model, ray tracing is sometimes undecidable, sometimes PSPACE-hard, and sometimes in PSPACE.>

Article A randomized parallel algorithm for planar graph isomorphism Share on Authors: H. Gazit Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile , J. Reif Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 210–219https://doi.org/10.1145/97444.97687Online:01 May 1990Publication History 4citation468DownloadsMetricsTotal Citations4Total Downloads468Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

There are now a number of fundamental problems in computational geometry that have optimal algorithms on PRAM models.We present randomized parallel algorithms which execute on an n-processor butterfly inter-connection network in O(log n) time for the following problems of input size n: trapezoidal decomposition, visibility, triangulation and Z-D convex hull.These are based on some previous work of the authors on PRAM algorithms and a new algorithm for doing binary search on fixed connection network.Apart from a 2-D convex hull algorithm, these are the first non-trivial geometric algorithms which attain this performance on fixed connection networks.The techniques developed in this paper rely on random sampling methods to do loadbalancing on fixed-connection networks; it seems likely that they will have wider applications.

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 interest as a way of efficiently using parallel processors to solve algebraic problems. In particular, this algorithm implies that any rational function can be evaluated in these complexity bounds. As an introduction to high-order iterative methods a circuit is first presented for finding polynomial reciprocals (where the coefficients come from an arbitrary ring, and ring operations are unit cost in the circuit) in size $O(PM(n))$ and depth $O(\log n \log \log n)$, where $PM(n)$ is the size complexity of optimal depth polynomial multiplication.

The authors present a parallel algorithm based on open ear decomposition which, given a graph G on n vertices, constructs an embedding of G onto the plane or reports that G is nonplanar. This parallel algorithm runs on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM) in O(log n) time with the same processor bound as graph connectivity.>

We introduce a new randomized sampling technique, called Polling which has applications to deriving efficient parallel algorithms. As an example of its use in computational geometry, we present an optimal parallel randomized algorithm for intersection of half-spaces in three dimensions. Because of well-known reductions, our methods also yield equally efficient algorithms for fundamental problems like t,he convex hull in three dimensions, Voronoi diagram of point sites on a plane and Euclidean minimal spanning tree. Our algorithms run in time T = O(logn) for worst-case inputs and uses P = O(n) processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only O(log2 n) random bits and terminate in the claimed time bound with probability 1- n--(y for any o> 0. They are also optimal in P. T product since the sequential time bound for all these problems is Sl(nlogn). The best known deterministic parallel algorithms for 2-D Voronoi-diagram and 3-D Convex hull run in O(log2 n) and O(log2 nlog * n) time respectively while using O(n) processors.

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 Ο(M(n)) and depth Ο(lognlog logn), where M(n) is the size complexity of Ο(logn) depth integer multiplication circuits. Currently, M(n) is known to be Ο(nlogn 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 Ο(n logc n) for any c, and simultaneous depth less than Ω(log2 n). Our circuits are logspace uniform; that is, they can be constructed by a deterministic Turing machine in space Ο(log n).

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.

In this paper we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly like the terrain maps. A distinguishing feature of this algorithm is that its running time is sensitive to the actual size of the visible image rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is Ο((k +n)lognloglogn) where n and k are respectively the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time Ω(n2) irrespective of the output size (where as the output size k is Ο(n2) only in the worst case). We also present a parallel algorithm based on a similar approach which runs in time Ο(log4(n+k)) using Ο((n + k)/log(n+k)) processors in a CREW PRAM model. All our bounds are obtained using ammortized analysis.

The following problem, is considered: given a robot system find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. The simplified case of a point mass under Newtonian mechanics together with velocity and acceleration bounds is considered. The point must be flown from a start to a goal, amid 2-D or 3-D polyhedral obstacles. While exact solutions to this problem are not known, the first provably good approximation algorithm is given and shown to run in polynomial time.

We build a three-dimensional array of unreliable cellular automata that can simulate a universal Turing machine (more generally, a one-dimensional universal iterative array) reliably. This is the first reliable real-time simulation. The encoding is simple repetition, and no decoding is needed. The construction is based on Toom's work.

We give an algorithm for accepting a deterministic context-free language on the P-RAM, an exclusive-write, concurrent-read model of parallel computation. Whereas on inputs of length n, a deterministic push-down automaton will use time linear in n, our algorithm runs in time $O(\log n)$ on $n^3 $ processors. The algorithm is easily generalized to permit parallel simulation of any deterministic auxiliary pushdown automaton that uses space $s(n) \geqq \log n$ and time $2^{O(s(n))} $. The simulation runs in time $O(s(n))$ on $2^{O(s(n))} $ processors, and is nearly optimal, since we observe that any language accepted by a P-RAM in time $T(n)$ is accepted by a deterministic auxiliary pushdown automaton in space $T(n)$ and time $2^{O(T(n)^2 )} $.

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 consequences for complexity theory. Given a randomized parallel algorithm $\mathcal{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 that $\mathcal{A}$ can be simulated by a parallel algorithm with time bound $T(n) + O((\log n)(\log \log n))$, processor bound $P(n)n^{\varepsilon '} $, and only using $n^\varepsilon $ truly random bits for any $\varepsilon > 0$. Also, we show that if the Multiplicative Inverse Problem is almost always not in ${\bf RNC}$, the ${\bf RNC}$ is within the class of languages accepted by uniform poly-log depth circuits with unbounded fan-in and strictly subexponential size $ \cap _{\varepsilon > 0} 2^{n^\varepsilon } $ .

We present new techniques for establishing lower bounds in robot motion planning problems. Our scheme is based on path encoding and uses homotopy equivalence classes of paths to encode state. We first apply the method to the shortest path problem in 3 dimensions. The problem is to find the shortest path under an Lp metric (e.g. a euclidean metric) between two points amid polyhedral obstacles. Although this problem has been extensively studied, there were no previously known lower bounds. We show that there may be exponentially many shortest path classes in single-source multiple-destination problems, and that the single-source single-destination problem is NP-hard. We use a similar proof technique to show that two dimensional dynamic motion planning with bounded velocity is NP-hard. Finally we extend the technique to compliant motion planning with uncertainty in control. Specifically, we consider a point in 3 dimensions which is commanded to move in a straight line, but whose actual motion may differ from the commanded motion, possibly involving sliding against obstacles. Given that the point initially lies in some start region, the problem of finding a sequence of commanded velocities which is guaranteed to move the point to the goal is shown to be non-deterministic exponential time hard, making it the first provably intractable problem in robotics.

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

We describe a parallel algorithm for testing a graph for planarity, and for finding an embedding of a planar graph. For a graph on n vertices, the algorithm runs in O(log2 n) steps on n processors of a parallel RAM. The previous best algorithm for planarity testing in parallel polylog time ([Ja'Ja' and Simon, 82]) used a reduction to solving linear systems, and hence required Ω(n2..49...) processors by known methods, whereas our processor bounds are within a polylog factor of optimal. The most significant aspect of our parallel algorithms is the use of a sophisticated data structure for representing sets of embeddings, the PQ-tree of [Booth and Lueker, 76]. Previously no parallel algorithms for PQ-trees were known. We have efficient parallel algorithms for manipulating PQ-trees, which we use in our planarity algorithm.

This paper describes circuits for computation of a large class of algebraic functions on polynomials, power series, and integers, for which, it has been a long standing open problem to compute in depth less than $\Omega (\log n)^2 $. Algebraic circuits assume unit cost for elemental addition and multiplication. This paper describes $O(\log n)$ depth algebraic circuits which given as input the coefficients of n degree polynomials (over an appropriate ring), compute the product of $n^{O(1)} $ polynomials, the symmetric functions, as well as division and interpolation of real polynomials. Also described are $O(\log n)$ depth algebraic circuits which are given as input the first n coefficients of a power series (over an appropriate ring) compute the product of $n^{O(1)} $ power series, as well as division, reciprocal and reversion of real power series. Furthermore this paper describes boolean circuits of depth $O(\log n(\log \log n))$ which, given n-bit binary numbers, compute the product of n numbers and integer division. As corollaries, we get boolean circuits of the same depth for evaluating, within accuracy $2^{ - n} $, polynomials, power series, and elementary functions such as (fixed) powers, roots, exponentiations, logarithm, sine and cosine. All these circuits have constant indegree, polynomial size, and may be uniformly constructed by a deterministic Turing machine with space $O(\log n)$.

Abstract : Trees play a fundamental role in many computations, both for sequential as well as parallel problems. The classic paradigm applied to generate parallel algorithms in the presence of trees has been divide-conquer; finding a 1/3 - 2/3 separator and recursively solving the two subproblems. A now classic example is Brent's work on parallel evaluation of arithmetic expressions. This top-down approach has several complications, one of which is finding the separators. We define dynamic expression evaluation as the task of evaluating the expression with no free preprocessing. If we apply Brent's method, finding the separators seems to add a factor of log n to the running time. We give a bottom-up algorithm to handle trees. That is, all modifications to the tree are done locally. This bottom-up approach which we call CONTRACT has two major advantages over the top-down approach: (1) the control structure is straight forward and easier to implement facilitating new algorithms using fewer processors and less time; and (2) problems for which it was too difficult or too complicated to find polylog parallel algorithms are now easy.

We assume a parallel RAM model which allows both concurrent writes and concurrent reads of global memory. Our algorithms are randomized: each processor is allowed an independent random number generator. However our stated resource bounds hold for worst case input with overwhelming likelihood as the input size grows. We give a new parallel algorithm for integer sorting where the integer keys are restricted to at most polynomial magnitude. Our algorithm costs only logarithmic time and is the first known where the product of the time and processor bounds are bounded by a linear function of the input size. These simultaneous resource bounds are asymptotically optimal. All previous known parallel sorting algorithms required at least a linear number of processors to achieve logarithmic time bounds, and hence were nonoptimal by at least a logarithmic factor.

This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental importance to robotics, but their computational complexity has not previously been investigated. We provide evidence that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In particular, we prove the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP hard even if B has no velocity modulus bound, where in both cases B has 6 degrees of freedom. To prove these results we use a unique method of simulation of a Turing machine which uses time to encode configurations (whereas previous lower bound proofs in robotics used the system position to encode configurations and so required unbounded number of degrees of freedom). We also investigate a natural class of dynamic problems which we call asteroid avoidance problems: B, the object we wish to move, is a convex polyhedron which is free to move by translation with bounded velocity modulus, and the polyhedral obstacles have known translational trajectories but cannot rotate. This problem has many applications to robot, automobile, and aircraft collision avoidance. Our main positive results are polynomial time algorithms for the 2-D asteroid avoidance problem with bounded number of obstacles as well as single exponential time and nO(log n) space algorithms for the 3-D asteroid avoidance problem with an unbounded number of obstacles. Our techniques for solving these asteroid avoidance problems are novel in the sense that they are completely unrelated to previous algorithms for planning movement in the case of static obstacles. We also give some additional positive results for various other dynamic movers problems, and in particular give polynomial time algorithms for the case in which B has no velocity bounds and the movements of obstacles are algebraic in space-time.

We build a three-dimensional array of unreliable cellular automata that can simulate a universal Turing machine (more generally, a one-dimensional universal iterative array) reliably. This is the first reliable real-time simulation. The encoding is simple repetition, and no decoding is needed. The construction is based on Toom's work.

The most efficient known parallel algorithms for inversion of a nonsingular nxn matrix A or solving a linear system Ax=b over the rationals require O(log n) to the 2nd power time and M(n) square root of n processors (where M(n) is the number of processors required in order to multiply two nxn rational matrices in time O(log n)). Furthermore, all known polylog time algorithms for those problems are unstable: they require the calculations 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. Additional keywords: Iterations; Convergence; Newtons method; Computer architecture.

This paper concerns the fundamental problem of synchronizing communication between distributed processes whose speeds (steps per time unit) vary dynamically. Communication must be established in matching pairs, which are mutually willing to communicate. We show how to implement a distributed local scheduler to find these pairs. The only means of synchronization are boolean “flag” variables, each of which can be written by only one process and read by at most one other process. No global bounds in the speeds of processes are assumed. Processes with speed zero are considered dead. However, when their speed is nonzero then they execute their programs correctly. Dead processes do not harm our algorithms’ performance with respect to pairs of other running processes. When the rate of change of the ratio of speeds of neighbour processes (i.e., relative acceleration) is bounded, then any two of these processes will establish communication within a constant number of steps of the slowest process with high likelihood. So, our implementation has the property of achieving relative real time response. We can use our techniques to solve other problems such as resource allocation and implementation of parallel languages such as CSP and Ada. Note that we do not have any probability assumptions about the system behaviour, although our algorithms use the technique of probabilistic choice.

Article The complexity of elementary algebra and geometry Share on Authors: Michael Ben-Or View Profile , Dexter Kozen View Profile , John Reif View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 457–464https://doi.org/10.1145/800057.808712Online:01 December 1984Publication History 26citation516DownloadsMetricsTotal Citations26Total Downloads516Last 12 Months31Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper introduces a new class of games called symmetric complementing games.These games are interesting since their related complexity classes include many well-known graph problems: Finding mlmmum spanning forests; k-connectiwty and k-blocks; and recognition of chordal graphs, comparabdity graphs, interval graphs, spht graphs, permutation graphs, and constant valence planar graphs.For these problems probabihstlc sequential algorithms requiring simultaneously logarithmic space and polynomial time are given Furthermore, probabfllsUc parallelism algorithms requiring simultaneously loganthmic time and a polynomml number of processors are also given.

This paper introduces probabilistic choice to synchronous parallel machine models; in particular parallel RAMs. The power of probabilistic choice in parallel computations is illustrated by parallelizing some known probabilistic sequential algorithms. We characterize the computational complexity of time, space, and processor bounded probabilistic parallel RAMs in terms of the computational complexity of probabilistic sequential RAMs. We show that parallelism uniformly speeds up time bounded probabilistic sequential RAM computations by nearly a quadratic factor. We also show that probabilistic choice can be eliminated from parallel computations by introducing nonuniformity.

This paper considers a fixed (possibly infinite) set of distributed asynchronous processes, which at various times are willing to communicate with each other.Each process has various ports, each of which is used for communication with a distinct neighbor process.Each process can have at most one port open at any time, and its other ports must be closed.Two processes handshake over a time interval A if their respective ports are open for mutual communication during this interval.Note that the handshake relation is a matching.Successful communication requires a handshake of at least one step of each process; during the one-step overlap a message can be transmitted between processes.The problem is to synchronize processes (via a distributed scheduler) so that they can successfully handshake at their will, given that the means of synchronization is some low-level construct that does not guarantee the handshake property if used in an unsophisticated way.Probabilistic distributed algorithms for synchronizing processes so that they can handshake at will are described.A process is considered to be tame over a time interval A if its speed varies within certain arbitrarily fixed nonzero bounds.Our synchronization algorithms are shown to have real-time response: If a pair of processers are mutually willing to communicate within a time interval A of length at least a given constant and the pair are tame on A, then they establish communication within A with high likelihood (for the worst case behavior of the system), and the expected time for establishment of communication is also constant.Our model and algorithms are applied to solve a large class of real-time resource allocation problems, as well as real-time implementation of the synchronization primitives of Hoare's multiprocessing language CSP.

This paper describes circuits for computation of various algebraic functions on polynomials, power series, integers, and reals for which it has been a long standing open problem to compute in depth less then (log n)2. Let R[x] be the polynomials and power series over a commutative ring which supports a fast Fourier transform and let L[x] be the polynomials and power series over the rationals L. For polynomials of degree n-1, we give circuits of depth O(log n) for computing - the m-th power of a polynomial and the product of m polynomials in R[x], where m=nO(1) - the symmetric functions on R[x] - the remainder and quotient of division of polynomials in L[x] - interpolation of a polynomial in L[x]. For power series with n given low order terms, we give circuits of depth O(log n) for computing the first n low order terms of - the m-th power of a power series in R[x] and the product of m power series in R[x] where m=nO(1) - the composition of power series in R[x] - the reciprocal of a power series and the division of two power series in L[x] -the reversion of a power series in L[x] - various elementary functions applied to power series in L[x] such as (fixed) powers, roots, exponentation, logarithm, sin, cos, arctangent, and hyperbolic cosine. For integers represented by n bit binary numbers, we give boolean circuits (whose gates compute the boolean operations ∧, ∨, and ¬) of depth O(log n (loglog n) 2) for computing: - the m-th power of an integer and the product of m = nO(1) integers, - the remainder and quotient of the division of two integers. There are many immediate consequences of this result. For reals on a finite interval [a,b] represented as floating point numbers within relative accuracy o(2-n), we have boolean circuits of depth O (log n(loglog n) 2) for computing within relative accuracy o(2-n): - the m-th power of a real and the product of m = nO(1) reals - the reciprocal of a real and division of reals - various elementary functions on reals. Also, as a consequence of the above, for polynomials and power series in L[x] we have uniform boolean circuits of depth O(log n(loglog n)2) for all the above listed problems for polynomials and power series, and also: - evaluation of a polynomial or power series in L[x] at n points, within relative accuracy o(2-n). All our circuits may be uniformly constructed by a deterministic Turning machine with space O(log n) and have constant indegree.

We give a randomized algorithm that sorts on an N node network with constant valence in 0(log N) time. 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−α.

Let N be a planar undirected network with distinguished vertices s, t, a total of n vertices, and each edge labeled with a positive real (the edge’s cost) from a set L. This paper presents an algorithm for computing a minimum (cost) s-t cut of N. For general L, this algorithm runs in time $O(n\log ^2 (n))$. For the case when L contains only integers$ \leqq n^{O(1)} $, the algorithm runs in time $O(n\log (n)\log \log (n))$. Our algorithm also constructs a minimum s-t cut of a planar graph (i.e., for the case $L = \{ 1\} $) in time $O(n\log (n))$. Our algorithm can also be used to compute a minimum cut for a general undirected planar network. The fastest previous algorithm for computing a minimum s-t cut of a planar undirected network (Itai and Shiloach [SIAM J. Comput., 8 (1979), pp. 135–150]) has time $O(n^2 \log (n))$; the s-t cut is a byproduct of the maximum flow computed by their algorithm. The best previous time bound for minimum s-t cut of a planar graph (Cheston, Probert and Saxton [report, Dept. Computer Science, Univ. Saskatchewan, 1977]) was $O(n^2 )$.

We give a parallel RAM algorithm for simulating a deterministic auxiliary pushdown machine. If the pushdown machine uses space s(n) ≥ log n and time 2O(s(n))then our parallel simulation algorithm takes time O(s(n)) and requires 2processors. Thus any deterministic context free language is accepted in time O(log n) by our parallel RAM algorithm using a polynomial number of processors. (Our algorithm can easily be extended to also accept the LR(k) languages in time O(log n) and 2O(k)Processors. Our simulation algorithm is near optimal for parallel RAMs, since we show that the language accepted in time T(n) by a parallel RAM is accepted by a deterministic auxiliary pushdown machine with space T(n) and time 2O(T(n)2).

In this paper we consider a resource allocation problem which is local in the sense that the maximum number of users competing for a particular resource at any time instant is bounded and also at any time instant the maximum number of resources that a user is willing to get is bounded. The problem may be viewed as that of achieving matchings in dynamically changing hypergraphs, via a distributed algorithm. We show that this problem is related to the fundamental problem of handshake communication (which can be viewed as achieving matchings in a dynamically changing graph, via distributed algorithms) in that an efficient solution to each of them implies an efficient solution to the other. We provide real-time solutions to the resource allocation problem (that is, we give distributed algorithms with real time response). We make essential use of probabilistic techniques as first used by [Rabin, 80b], where processes are allowed to make independent probabilistic choices. On the other hand, no probability assumptions about the system behavior are made. One of our solutions assumes the existence of an underlying real-time handshake communication system, as described in [Reif, Spirakis, 81]. Our other solution is based on efficient synchronization by flag variables, which are written only by one process and read by at most one other process. The special case of equi-speed processes is first examined. Then we generalize to asynchronous processes. Applications are made to dining philosophers, scheduling and two-phase locking in databases.

This paper concerns the fundamental problem of synchronizing communication between distributed processes whose speeds (steps per real time unit) vary dynamically. Communication must be established in matching pairs, which are mutually willing to communicate. We show how to implement a distributed local scheduler to find these pairs. The only means of synchronization are boolean "flag" variables, each of which can be written by only one process and read by at most one other process.No global bounds in the speeds of processes are assumed. Processes with speed zero are considered dead. However, when their speed is nonzero then they execute their programs correctly. Dead processes do not harm our algorithms' performance with respect to pairs of other running processes. When the rate of change of the ratio of speeds of neighbour processes (i.e., relative acceleration) is bounded, then any two of these processes will establish communication within a constant number of steps of the slowest process with high likelihood. Thus our implementation has the property of achieving relative real time response. We can use our techniques to solve other problems such as resource allocation and implementation of parallel languages such as CSP and ADA. Note that we do not have any probability assumptions about the system behavior, although our algorithms use the technique of probabilistic choice.

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 Σ(@@@@) CSYMLOG, which contains the outcome problem of symmetric complementing games with constant complement bound with game positions encoded in log space, and next move relations computable in log space. We show that the decision problem for a restricted quantified Boolean logic Σ(@@@@) [email protected]@@@ is complete in Σ(@@@@) CSYMLOG.

This paper describes an algorithm to construct, for each expression in a given program text, a symbolic expression whose value is equal to the value of the text expression for all executions of the program. We call such a mapping from text expressions to symbolic expressions a cover. Covers are useful in such program optimization techniques as constant propagation and code motion. The particular cover constructed by our methods is in general weaker than the covers obtainable by the methods of [Ki], [FKU], [RL], [R2] but our method has the advantage of being very efficient. It requires $O(m\alpha (m,n) + l)$ operations if extended bit vector operations have unit cost, where n is the number of vertices in the control flow graph of the program, m is the number of edges, l is the length of the program text, and $\alpha $ is related to a functional inverse of Ackermann’s function [T2]. Our method does not require that the program be well-structured nor that the flow graph be reducible.

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. 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 considers a fixed (possibly infinite) set π of distributed asynchronous processes which at various times are willing to communicate with each other.

A crucial property of distributed multiprocessing systems is the lack of complete information by any given process about the states of other processes. The contribution of this paper is a fundamental modal logic, MPL, for multiprocessing with incomplete information. (Section 1.5 gives an informal introduction to MPL; the formal definitions are in Section 2.)By way of this logic, we develop a solid (practical and theoretical) correspondence between distributed multiprocessing and multiplayer games of incomplete information.Fischer and Ladner, [1979] have shown a logspace reduction from the outcome problem for two person games of perfect information to satisfiability of formulas in their propositional dynamic logic (PDL). We provide in Section 3 a log-space reduction from the outcome problem for multiplayer games of incomplete information to satisfiability of formulas in our logic MPL. Although in general satisfiability in out logic is undecidable, the satisfiability problem of formulae with hierarchical visibility structure is shown decidable (using the methods for solving hierarchical games developed in Reif [1979] and Peterson and Reif [1979], and also the model theoretic techniques of Fischer and Ladner [1979] and Pratt [1979b]).At a more practical level, we argue that the game-like semantics of our logic provides a robust paradigm in which to view distributed multiprocessing problems. We apply our logic to describe total correctness properties of multi-process programs with shared variables as well as communicating processes with "handshake"-type message passing.

This paper introduces a logic for probabilistic programming+ PROB-DL (for probabilistic dynamic logic; see Section 2 for a formal definition). This logic has “dynamic” modal operators in which programs appear, as in Pratt's [1976] dynamic logic DL. However the programs of PROB-DL contain constructs for probabilistic branching and looping whereas DL is restricted to nondeterministic programs. The formula {a}σp of PROB-DL denotes “with measure ≥σ, formula p holds after executing program a.”

We introduce a new random structure generalizing matroids. These random matroids allow us to develop general techniques for solving hard combinatorial optimization problems with random inputs.

Code motion is a program optimization concerned with the movement of code as far as possible out of control cycles into new locations where the code may be executed less frequently. This paper describes methods for approximating certain functions which ensure that the relocated code may be computed properly and safely, inducing no errors of computation. The effectiveness of code motion depends on the goodness of our approximation to these functions, as well as on tradeoffs between (1) the primary goal of moving code out of control cycles and (2) the secondary goal of providing that the values resulting from the execution of relocated code are utilized. Two versions of code motion are formulated: the first emphasizes the primary goal, whereas the other insures that the second goal is not compromised. Algorithms are presented for both formulations of code motion; the algorithm for the first version of code motion is restricted to reducible flow graphs, but the other runs on all flow graphs. Both of our algorithms run in almost linear time. Previous algorithms for similar formulations of code motion have time cost lower bounded in the worst case by the length of the program text times the number of nodes of the control flow graph.

We generalize the alternation machines of Chandra, Kozen and Stockmeyer [1] and the private alternation machines of Reif [14] to model multiple person (team) games of incomplete information. The resulting classes of machines are "multiple person alternation machines". The characterization of certain time and space bounded versions of these machines demonstrate interesting relationships between ordinary time and space hierarchies (Table 1). Our results are applied to relative succintness and power questions of finite state machines and to complexity questions of parallel finite state machines. Other machine variants, including private alternating pushdown store automata and Markovian alternation machines, are discussed.

This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles.

Data flow analysis is a technique essential to the compile-time optimization of computer programs, wherein facts relevant to program optimizations are discovered by the global propagation of facts obvious locally.This paper extends flow analysis techniques developed for sequential programs to the analysis of communicating, concurrent processes.

In this paper we present an algorithm which on input a graph G and a positive integer g finds an embedding of G on a surface on genius g, if such an embedding exists. This algorithm runs in (v) O(g) steps where v is the number of vertices of G.

We consider two-person games of incomplete information in which certain portions of positions are private to each player and cannot be viewed by the opponent. We present various games of incomplete information which are universal for all reasonable games. The problem of determining the outcome of these universal games from a given initial position is shown to be complete in doubly-exponential time. We also define “private alternating Turing machines” which are alternating Turing machines with certain tapes and portions of states private to universal states. The time and space complexity of these machines is characterized in terms of the time complexity of deterministic Turing machines, with single and double exponential jumps.

A global flow model is assumed; as usual, the flow of control is represented by a digraph called the control flow graph. The objective of our program analysis is the construction of a mapping (a cover) from program text expressions to symbolic expressions for their value holding over all executions of the program. The particular cover constructed by our methods is in general weaker than the covers obtainable by the methods of [Ki, FKU, R1], but our method has the advantage of being very efficient; requiring O(ℓ + aα(a)) extended bit vector operations (a logical operation or a shift to the first nonzero bit) on all control flow graphs (whether reducible or not), where a is the number of edges of the control flow graph, ℓ is the length of the text of the program, and α is Tarjan's function (an extremely slowly growing function).

This paper is concerned with difficult global flow problems which require the symbolic evaluation of programs. We use, as is common in global flow analysis, a model in which the expressions computed are specified, but the flow of control is indicated only by a directed graph whose nodes are blocks of assignment statements. We show that if such a program model is interpreted in the domain of integer arithmetic then many natural global flow problems are unsolvable. We then develop a direct (non-iterative) method for finding general symbolic values for program expressions. Our method gives results similar to an iterative method due to Kildall and a direct method due to Fong, Kam, and Ullman. By means of a structure called the global value graph which compactly represents both symbolic values and the flow of these values through the program, we are able to obtain results that are as strong as either of these algorithms at a lower time cost, while retaining applicability to all flow graphs.