Arrow Research search

Author name cluster

John H. Reif

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

50 papers
2 author rows

Possible papers

50

TCS Journal 2011 Journal Article

Complexity of graph self-assembly in accretive systems and self-destructible systems

  • John H. Reif
  • Sudheer Sahu
  • Peng Yin

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

Details DOI

TCS Journal 2009 Journal Article

Autonomous programmable DNA nanorobotic devices using DNAzymes

  • John H. Reif
  • Sudheer Sahu

A major challenge in nanoscience is the design of synthetic molecular devices that run autonomously (that is, without externally mediated changes per work-cycle) and are programmable (that is, their behavior can be modified without complete redesign of the device). DNA-based synthetic molecular devices have the advantage of being relatively simple to design and engineer, due to the predictable secondary structure of DNA nanostructures and the well-established biochemistry used to manipulate DNA nanostructures. However, ideally we would like to minimize the use of protein enzymes in the design of a DNA-based synthetic molecular device. We present the design of a class of DNA-based molecular devices using DNAzyme. These DNAzyme-based devices are autonomous, programmable, and further require no protein enzymes. The basic principle involved is inspired by a simple but ingenious molecular device due to Tian et al. [Y. Tian, Y. He, Y. Chen, P. Yin, C. Mao, A DNAzyme that walks processively and autonomously along a one-dimensional track, Angew. Chem. Intl. Ed. 44 (2005) 4355–4358] that used DNAzyme to traverse on a DNA nanostructure, but was not programmable in the sense defined above (it did not execute computations). Our DNAzyme-based designs include (1) a finite state automaton, DNAzyme FSA that executes finite state transitions using DNAzymes, (2) extensions to it including probabilistic automaton and non-deterministic automaton, and (3) its application as a DNAzyme router for programmable routing of nanostructures on a 2D DNA addressable lattice. Furthermore, we give a medical-related application, DNAzyme doctor that provides transduction of nucleic acid expression: it can be programmed to respond to the underexpression or overexpression of various strands of RNA, with a response by the release of an RNA. (The behavior of our nucleic acid transduction devices is similar to those of the prior paper of Benenson [Y. Benenson, B. Gil, U. Ben-Dor, R. Adar, E. Shapiro, An autonomous molecular computer for logical control of gene expression, Nature 429 (2004) 423–429], but ours have the advantage that they operate without the use of any protein enzymes.)

Details DOI

I&C Journal 2007 Journal Article

Efficient and exact quantum compression

  • John H. Reif
  • Sukhendu Chakraborty

We present a divide and conquer based algorithm for optimal quantum compression/decompression, using O(n(log4 n)loglog n) elementary quantum operations. Our result provides the first quasi-linear time algorithm for asymptotically optimal (in size and fidelity) quantum compression and decompression. We also outline the quantum gate array model to bring about this compression in a quantum computer. Our method uses various classical algorithmic tools to significantly improve the bound from the previous best known bound of O(n 3) for this operation.

Details DOI

TCS Journal 2006 Journal Article

On boundaries of highly visible spaces and applications

  • John H. Reif
  • Zheng Sun

The purpose of this paper is to investigate the properties of a certain class of highly visible spaces. For a given geometric space C containing obstacles specified by disjoint subsets of C, the free space F is defined to be the portion of C not occupied by these obstacles. The space is said to be highly visible if at each point in F a viewer can see at least an ε fraction of the entire F. This assumption has been used for robotic motion planning in the analysis of random sampling of points in the robot's configuration space, as well as the upper bound of the minimum number of guards needed for art gallery problems. However, there is no prior result on the implication of this assumption to the geometry of the space under study. For the two-dimensional case, with the additional assumptions that C is bounded within a rectangle of constant aspect ratio and that the volume ratio between F and C is a constant, we use the proof technique of “charging” each obstacle boundary segment by a certain portion of C to show that the total length of all obstacle boundaries in C is O ( n μ ( F ) / ε ), if C contains polygonal obstacles with a total of n boundary edges; or O ( n μ ( F ) / ε ), if C contains n convex obstacles that are piecewise smooth. In both cases, μ ( F ) is the volume of F. For the polygonal case, this bound is tight as we can construct a space whose boundary size is Θ ( n μ ( F ) / ε ). These results can be partially extended to three dimensions. We show that these results can be applied to the analysis of certain probabilistic roadmap planners, as well as a variant of the art gallery problem. We also propose a number of conjectures on the properties of these highly visible spaces.

Details DOI

ICRA Conference 2003 Conference Paper

On energy-minimizing paths on terrains for a mobile robot

  • Zheng Sun 0002
  • John H. Reif

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.

Details

ICRA Conference 2003 Conference Paper

The bridge test for sampling narrow passages with probabilistic roadmap planners

  • David Hsu
  • Tingting Jiang 0001
  • John H. Reif
  • Zheng Sun 0002

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.

Details

ICRA Conference 2001 Conference Paper

Programmable Assembly at the Molecular Scale: Self-Assembly of DNA Lattices (Invited Paper)

  • John H. Reif
  • Thomas H. LaBean
  • Nadrian C. Seeman

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.

Details

I&C Journal 1996 Journal Article

Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem

  • Ming-Yang Kao
  • John H. Reif
  • Stephen R. Tate

Searching for a goal is a central and extensively studied problem in computer science. In classical searching problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many robotics problems, as well as in problems from other areas, we want to charge a cost proportional to the distance between queries (e. g. , the time required to travel between two query points). With this cost function in mind, the abstract problem known as thew-lane cow-path problem was designed. There are known optimal deterministic algorithms for the cow-path problem; we give the first randomized algorithm in this paper. We show that our algorithm is optimal for two paths (w=2) and give evidence that it is optimal for larger values ofw. Subsequent to the preliminary version of this paper, Kaoet al. (in“Proceedings, 5th ACM–SIAM Symposium on Discrete Algorithm, ” pp. 372–381, 1994) have shown that our algorithm is indeed optimal for allw⩾2. Our randomized algorithm gives expected performance that is almost twice as good as is possible with a deterministic algorithm. For the performance of our algorithm, we also derive the asymptotic growth with respect tow—despite similar complexity results for related problems, it appears that this growth has never been analyzed.

Details DOI

FOCS Conference 1995 Conference Paper

Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems

  • John H. Reif

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.

Details

FOCS Conference 1994 Conference Paper

An O(n^1+epsilon log b) Algorithm for the Complex Roots Problem

  • C. Andrew Neff
  • John H. Reif

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

Details

FOCS Conference 1993 Conference Paper

Using Difficulty of Prediction to Decrease Computation: Fast Sort, Priority Queue and Convex Hull on Entropy Bounded Inputs

  • Shenfeng Chen
  • John H. Reif

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

Details

TCS Journal 1992 Journal Article

Nested annealing: a provable improvement to simulated annealing

  • Sanguthevar Rajasekaran
  • John H. Reif

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

Details DOI

FOCS Conference 1992 Conference Paper

The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms

  • Victor Y. Pan
  • John H. Reif
  • Stephen R. Tate

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

Details

FOCS Conference 1990 Conference Paper

The Computability and Complexity of Optical Beam Tracing

  • John H. Reif
  • J. D. Tygar
  • Akitoshi Yoshida

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

Details

FOCS Conference 1989 Conference Paper

An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract)

  • Vijaya Ramachandran
  • John H. Reif

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

Details

I&C Journal 1989 Journal Article

Parallel processing can be harmful: The unusual behavior of interpolation search

  • Dan E. Willard
  • John H. Reif

Several articles have noted the usefulness of a retrieval algorithm called sequential interpolation search, and Yao and Yao have proven a lower bound log logN−O(1), showing this algorithm is actually optimal up to an additive constant on unindexed files of sizeNgenerated by the uniform probability distribution. We generalize the latter to show log logN− log logP−O(1) lower bounds the complexity of any retrieval algorithm withPparallel processors for searching an unindexed file of sizeN. This result is surprising because we also show how to obtain an upper bound that matches the lower bound up to an additive constant with a procedure that actually usesno parallel processingoutside its last iteration (at which time our proposal turns onPprocessors in parallel). Our first theorem therefore states thatparallel processing before the literally last iterationin the search of an unindexed ordered file hasnearly no usefulness. Two further surprising facts are that the preceding result holds even when communication between the parallel processing units involvesno delayand that the parallel algorithms are actuallyinherently slowerthan their sequential counterparts when each invocation of the SIMD machine invokes a communication step withany typeof nonzerodelay. The presentation in the first two chapters of this paper is quite informal, so that the reader can quickly grasp the underlying intuition.

Details DOI

STOC Conference 1989 Conference Paper

Polling: A New Randomized Sampling Technique for Computational Geometry

  • John H. Reif
  • Sandeep Sen

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 the 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(log 2 n ) random bits and terminate in the claimed time bound with probability 1 - n -α for any α > 0. They are also optimal in P . T product since the sequential time bound for all these problems is Ω( nlogn ). The best known determistic parallel algorithms for 2-D Voronoi-diagram and 3-D Convex hull run in O(log 2 n ) and O(log 2 nlog * n ) time respectively while using O(n) processors.

Details

MFCS Conference 1988 Invited Paper

3-Dimensional Shortest Paths in the Presence of Polyhedral Obstacles

  • John H. Reif
  • James A. Storer

Abstract We consider the problem of finding a minimum length path between two points in 3-dimensional Euclidean space which avoids a set of (not necessarily convex) polyhedral obstacles; we let n denote the number of the obstacle edges and k denote the number of "islands" in the obstacle space. An island is defined to be a maximal convex obstacle surface such that for any two points contained in the interior of the island, a minimal length path between these two points is strictly contained in the interior of the island; for example, a set of i disconnected convex polyhedra forms a set of i islands, however, a single non-convex polyhedron will constitute more that one island. Prior to this work, the best known algorithm required double-exponential time. We present an algorithm that runs in \(n^{k^{0(1)} }\) time and also one that runs in O ( n log(k) ) space.

Details

FOCS Conference 1988 Conference Paper

On the Complexity of Kinodynamic Planning

  • John F. Canny
  • Bruce Randall Donald
  • John H. Reif
  • Patrick G. Xavier

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.

Details

FOCS Conference 1987 Conference Paper

New Lower Bound Techniques for Robot Motion Planning Problems

  • John F. Canny
  • John H. Reif

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.

Details

FOCS Conference 1986 Conference Paper

An Efficient Parallel Algorithm for Planarity

  • Philip N. Klein
  • John H. Reif

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.

Details

TARK Conference 1986 Conference Paper

The Logic of Distributed Protocols

  • Richard E. Ladner
  • John H. Reif

A propositional logic of distributed protocols is introduced which includes both the logicof knowledge and temporal logic. Phenomena in distributed computing systems such as asynchronous time, incomplete knowledge by the computing agents in the system, and game-like behavior among the computing agents are all modeled in the logic. Two versions of the logic, the linear logic of protocols (LLP) and the tree logic of protocols (TLP) are investigated. The main result is that the set of valid formulas in LLP is undecidable. iResearchsupportedby the NationalScienceFoundationGrant No. DCR-8402566. ~Researchsupportedby the Officeof NavalResearchContractNo. N00014-80~C-0647.

Details

STOC Conference 1985 Conference Paper

A Simple Three-Dimensional Real-Time Reliable Cellular Array

  • Péter Gács
  • John H. Reif

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.

Details

FOCS Conference 1985 Conference Paper

An Optimal Parallel Algorithm for Integer Sorting

  • John H. Reif

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.

Details

STOC Conference 1985 Conference Paper

Efficient Parallel Solution of Linear Systems

  • Victor Y. Pan
  • John H. Reif

The most efficient known parallel algorithms for inversion of a nonsingular n × n matrix A or solving a linear system Ax = b over the rationals require Ο(log n) 2 time and M(n)n 0.5 processors (where M(n) is the number of processors required in order to multiply two n × n rational matrices in time Ο(log n).) Furthermore, all known polylog time algorithms for those problems are unstable : they require the calculation to be done with perfect precision; otherwise they give no results at all.

Details

FOCS Conference 1985 Conference Paper

Motion Planning in the Presence of Moving Obstacles

  • John H. Reif
  • Micha Sharir

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.

Details

FOCS Conference 1983 Conference Paper

Logarithmic Depth Circuits for Algebraic Functions

  • John H. Reif

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.

Details

TCS Journal 1983 Journal Article

The propositional dynamic logic of deterministic, well-structured programs

  • Joseph Y. Halpern
  • John H. Reif

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

Details DOI

FOCS Conference 1982 Conference Paper

Parallel Time O(log N) Acceptance of Deterministic CFLs

  • John H. Reif

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 2 O(s(n)) then our parallel simulation algorithm takes time O(s(n)) and requires 2 processors. 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 2 O(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 2 O(T(n) 2 ).

Details

STOC Conference 1982 Conference Paper

Symmetric Complementation

  • John H. Reif

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 Σ(@@@@) QBF@@@@ is complete in Σ(@@@@) CSYMLOG.

Details

FOCS Conference 1981 Conference Paper

The Propositional Dynamic Logic of Deterministic, Well-Structured Programs (Extended Abstract)

  • Joseph Y. Halpern
  • John H. Reif

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.

Details

STOC Conference 1980 Conference Paper

Logics for Probabilistic Programming (Extended Abstract)

  • John H. Reif

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

Details

FOCS Conference 1979 Conference Paper

Multiple-Person Alternation

  • Gary L. Peterson
  • John H. Reif

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.

Details

STOC Conference 1979 Conference Paper

On Determining the Genus of a Graph in O(v^O(g)) Steps

  • I. S. Filotti
  • Gary L. Miller
  • John H. Reif

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.

Details

STOC Conference 1979 Conference Paper

Universal Games of Incomplete Information

  • John H. Reif

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.

Details
v2026.09.13