Scholars@Duke
John H. Reif

John H. Reif

A. Hollis Edens Distinguished Professor of Computer Science
Computer Science
reif@cs.duke.edu
Box 90129, Durham, NC 27708-0129
LSRC D-229, 308 Research Drive, Dept Comp Sci, Duke U, Durham, NC 27708

Selected Publications

A biomimetic branching signal-passing tile assembly model with dynamic growth and disassembly.

Journal Article Journal of the Royal Society, Interface · August 2024 Natural biological branching processes can form tree-like structures at all scales and, moreover, can perform various functions to achieve specific goals; these include receiving stimuli, performing two-way communication along their branches, and dynamical ... Full text Cite

Leak-resilient enzyme-free nucleic acid dynamical systems through shadow cancellation

Journal Article Journal of the Royal Society Interface · June 19, 2024 DNA strand displacement (DSD) emerged as a prominent reaction motif for engineering nucleic acid-based computational devices with programmable behaviours. However, strand displacement circuits are susceptible to background noise, known as leaks, which disr ... Full text Cite

A survey on molecular-scale learning systems with relevance to DNA computing.

Journal Article Nanoscale · May 2023 DNA computing has emerged as a promising alternative to achieve programmable behaviors in chemistry by repurposing the nucleic acid molecules into chemical hardware upon which synthetic chemical programs can be executed. These chemical programs are capable ... Full text Cite

Social DNA Nanorobots

Chapter · January 1, 2023 We describe social DNA nanorobots, which are autonomous mobile DNA devices that execute a series of pair-wise interactions between simple individual DNA nanorobots, causing a desired overall outcome behavior for the group of nanorobots which can be relativ ... Full text Cite

Automated design of 3D DNA origami with non-rasterized 2D curvature.

Journal Article Science advances · December 2022 Improving the precision and function of encapsulating three-dimensional (3D) DNA nanostructures via curved geometries could have transformative impacts on areas such as molecular transport, drug delivery, and nanofabrication. However, the addition of non-r ... Full text Cite

Data from: Automated design of 3D DNA origami with non-rasterized 2D curvature

Dataset · November 22, 2022 This data set includes molecular dynamics simulation data for DNA nanostructures discussed in the associated publication. Simulations are performed in oxDNA, a coarse-grained molecular dynamics simulator for DNA. Each simulation begins from an initial conf ... Full text Cite

DNA computing

Chapter · May 30, 2022 Full text Cite

A lyophilized colorimetric RT-LAMP test kit for rapid, low-cost, at-home molecular testing of SARS-CoV-2 and other pathogens.

Journal Article Scientific reports · April 2022 Access to fast and reliable nucleic acid testing continues to play a key role in controlling the COVID-19 pandemic, especially in the context of increased vaccine break-through risks due to new variants. We report a rapid, low-cost (~ 2 USD), simple-to-use ... Full text Cite

Multidimensional data organization and random access in large-scale DNA storage systems

Journal Article Theoretical Computer Science · November 26, 2021 With impressive physical density and molecular-scale coding capacity, DNA is a promising substrate for building long-lasting data archival storage systems. To retrieve data from DNA storage, recent implementations typically rely on large libraries of metic ... Full text Cite

An Overview of DNA‐Based Digital Data Storage

Chapter · March 8, 2021 This chapter overviews DNA‐based digital storage, which is a storage medium making use of DNA molecules to store digital data. The chapter describes methods for data encoding into DNA base sequences, data writing into DNA strands, and data storage of DNA w ... Link to item Cite

3d DNA nanostructures: The nanoscale architect

Journal Article Applied Sciences (Switzerland) · March 2, 2021 Structural DNA nanotechnology is a pioneering biotechnology that presents the oppor-tunity to engineer DNA-based hardware that will mediate a profound interface to the nanoscale. To date, an enormous library of shaped 3D DNA nanostructures have been design ... Full text Cite

DNA Origami Transformers

Chapter · January 1, 2021 DNA origami is a DNA nanostructure self-assembled from a long scaffold DNA strand with the use of many additional short staple DNA strands that stitch the nanostructure together. The chapter presents DNA origami transformers, which are novel technique for ... Full text Cite

UV-Micropatterned Miniaturization: Rapid In Situ Photopatterning and Miniaturization of Microscale Features on Shrinkable Thermoplastics

Journal Article Advanced Materials Technologies · June 1, 2020 Shrink lithography is a promising top-down micro/nanofabrication technique capable of miniaturizing patterns/structures to scales much smaller than the initial mold, however, rapid inexpensive fabrication of high-fidelity shrinkable microfeatures remains c ... Full text Cite

Using Strand Displacing Polymerase To Program Chemical Reaction Networks.

Journal Article Journal of the American Chemical Society · May 2020 Chemical reaction networks (CRNs) provide a powerful abstraction to formally represent complex biochemical processes. DNA provides a promising substrate to implement the abstract representation (or programming language) of CRNs due to its programmable natu ... Full text Cite

Autonomous Design of Biomimetic 3D DNA Origami Capsules

Conference 17th Annual Conference on Foundations of Nanoscience, FNANO 2020: Self-Assembled Architectures and Devices · January 1, 2020 Cite

Fast and compact DNA logic circuits based on single-stranded gates using strand-displacing polymerase.

Journal Article Nature nanotechnology · November 2019 DNA is a reliable biomolecule with which to build molecular computation systems. In particular, DNA logic circuits (diffusion-based) have shown good performance regarding scalability and correctness of computation. However, previous architectures of DNA lo ... Full text Cite

Programming DNA-Based Biomolecular Reaction Networks on Cancer Cell Membranes.

Journal Article Journal of the American Chemical Society · October 2019 DNA is a highly programmable biomolecule and has been used to construct biological circuits for different purposes. An important development of DNA circuits is to process the information on receptors on cell membranes. In this Communication, we introduce a ... Full text Cite

Nucleic Acid Databases and Molecular-Scale Computing.

Journal Article ACS nano · June 2019 DNA outperforms most conventional storage media in terms of information retention time, physical density, and volumetric coding capacity. Advances in synthesis and sequencing technologies have enabled implementations of large synthetic DNA databases with i ... Full text Cite

Improved Optical Multiplexing with Temporal DNA Barcodes.

Journal Article ACS synthetic biology · May 2019 Many biochemical events of importance are complex and dynamic. Fluorescence microscopy offers a versatile solution to study the dynamics of biology at the mesoscale. An important challenge in the field is the simultaneous study of several objects of intere ... Full text Cite

Programming Temporal DNA Barcodes for Single-Molecule Fingerprinting.

Journal Article Nano letters · April 2019 Fluorescence microscopy enables simultaneous observation of the dynamics of single molecules in a large region of interest. Most traditional techniques employ either the geometry or the color of single molecules to uniquely identify (or barcode) different ... Full text Cite

Renewable DNA hairpin-based logic circuits

Journal Article IEEE Transactions on Nanotechnology · January 1, 2019 Developing intelligent molecular systems for the desired functions is a significant current research topic in the field of nanoscience. Several materials have been explored to construct interesting systems, such as molecular motors, molecular walkers, and ... Full text Cite

Implementing Arbitrary CRNs Using Strand Displacing Polymerase

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2019 The regulation of cellular and molecular processes typically involves complex biochemical networks. Synthetic nucleic acid reaction networks (both enzyme-based and enzyme-free) can be systematically designed to approximate sophisticated biochemical process ... Full text Cite

Improving the Performance of DNA Strand Displacement Circuits by Shadow Cancellation.

Journal Article ACS nano · November 2018 DNA strand displacement circuits are powerful tools that can be rationally engineered to implement molecular computing tasks because they are programmable, cheap, robust, and predictable. A key feature of these circuits is the use of catalytic gates to amp ... Full text Cite

Renewable Time-Responsive DNA Circuits.

Journal Article Small (Weinheim an der Bergstrasse, Germany) · July 2018 DNA devices have been shown to be capable of evaluating Boolean logic. Several robust designs for DNA circuits have been demonstrated. Some prior DNA-based circuits are use-once circuits since the gate motifs of the DNA circuits get permanently destroyed a ... Full text Cite

Localized DNA Hybridization Chain Reactions on DNA Origami.

Journal Article ACS nano · February 2018 The field of DNA nanoscience has demonstrated many exquisite DNA nanostructures and intricate DNA nanodevices. However, the operation of each step of prior demonstrated DNA nanodevices requires the diffusion of DNA strands, and the speed of these devices i ... Full text Cite

Design and Analysis of Compact DNA Strand Displacement Circuits for Analog Computation Using Autocatalytic Amplifiers.

Journal Article ACS synthetic biology · January 2018 A main goal in DNA computing is to build DNA circuits to compute designated functions using a minimal number of DNA strands. Here, we propose a novel architecture to build compact DNA strand displacement circuits to compute a broad scope of functions in an ... Full text Cite

DNA-Based Analog Computing.

Journal Article Methods in molecular biology (Clifton, N.J.) · January 2018 The field of DNA computation makes use of DNA reactions to do molecular-scale computation. Most works in DNA computation execute digital computations such as evaluation of Boolean circuits. This chapter surveys novel DNA computation methods that execute an ... Full text Cite

Temporal DNA barcodes: A time-based approach for single-molecule imaging

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2018 In the past decade, single-molecule imaging has opened new opportunities to understand reaction kinetics of molecular systems. DNA-PAINT uses transient binding of DNA strands to perform super-resolution fluorescence imaging. An interesting challenge in DNA ... Full text Cite

DNA robots sort as they walk.

Journal Article Science (New York, N.Y.) · September 2017 Full text Cite

Design and Analysis of Localized DNA Hybridization Chain Reactions

Journal Article Small · 2017 Theoretical models of localized DNA hybridization reactions on nanoscale substrates indicate potential benefits over conventional DNA hybridization reactions. Recently, a few approaches have been proposed to speed-up DNA hybridization reactions; however, e ... Full text Cite

Design and analysis of linear cascade DNA hybridization chain reactions using DNA hairpins

Journal Article New Journal of Physics · 2017 DNA self-assembly has been employed non-conventionally to construct nanoscale structures and dynamic nanoscale machines. The technique of hybridization chain reactions by triggered self-assembly has been shown to form various interesting nanoscale structur ... Cite

Renewable DNA seesaw logic circuits enabled by photoregulation of toehold-mediated strand displacement

Journal Article RSC Advances · January 1, 2017 An important achievement in the field of DNA-based computation has been the development of experimental protocols for evaluation of Boolean logic circuits. These protocols for DNA circuits generally take as inputs single-stranded DNA molecules that encode ... Full text Cite

Activatable tiles for compact robust programmable molecular assembly and other applications

Journal Article Natural Computing · December 1, 2016 Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors ... Full text Cite

Analog Computation by DNA Strand Displacement Circuits.

Journal Article ACS synthetic biology · August 2016 DNA circuits have been widely used to develop biological computing devices because of their high programmability and versatility. Here, we propose an architecture for the systematic construction of DNA circuits for analog computation based on DNA strand di ... Full text Cite

Energy complexity of optical computations

Journal Article International Journal of Unconventional Computing · January 1, 2016 This paper provides lower bounds on the energy consumption and demonstrates an energy-time trade-off in optical computations. All the lower bounds are shown to have the matching upper bounds for a transitive function-shifting. Since the energy consumption ... Cite

The co-learning in the design, simulation and optimization of a solar concentrating system

Journal Article Computers in Human Behavior · October 1, 2015 Due to the significant environmental and economic impact of the solar energy on our life, many solar concentrator systems (SCSs) exist today, the majority of them being very costly to construct. In this paper, an efficient low-cost SCS based on Reif resear ... Full text Cite

Solar-thermal powered desalination: Its significant challenges and potential

Journal Article Renewable and Sustainable Energy Reviews · August 1, 2015 Throughout the world, there are regions of vast extent that have many favorable features, but whose development is principally limited by the lack of fresh water. In arid areas where large-scale development has already occurred, e.g. parts of the Middle Ea ... Full text Cite

Probabilistic Analysis of Localized DNA Hybridization Circuits.

Journal Article ACS synthetic biology · August 2015 Molecular devices made of nucleic acids can perform complex information processing tasks at the nanoscale, with potential applications in biofabrication and smart therapeutics. However, limitations in the speed and scalability of such devices in a well-mix ... Full text Cite

Directed enzymatic activation of 1-D DNA tiles.

Journal Article ACS nano · February 2015 The tile assembly model is a Turing universal model of self-assembly where a set of square shaped tiles with programmable sticky sides undergo coordinated self-assembly to form arbitrary shapes, thereby computing arbitrary functions. Activatable tiles are ... Full text Cite

Meta-DNA: A DNA-based approach to synthetic biology

Journal Article · March 1, 2014 The goal of synthetic biology is to design and assemble synthetic systems that mimic biological systems. One of the most fundamental challenges in synthetic biology is to synthesize artificial biochemical systems, which we will call meta-biochemical system ... Full text Cite

DNA computing

Chapter · January 1, 2014 Full text Cite

Tile Complexity of Approximate Squares

Journal Article Algorithmica · May 1, 2013 The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, 1998) is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly un ... Full text Cite

An autonomously self-assembling dendritic DNA nanostructure for target DNA detection.

Journal Article Biotechnology journal · February 2013 There is a growing need for sensitive and reliable nucleic acid detection methods that are convenient and inexpensive. Responsive and programmable DNA nanostructures have shown great promise as chemical detection systems. Here, we describe a DNA detection ... Full text Cite

DNA nanorobotics

Chapter · January 1, 2013 This chapter overviews the current state of the emerging discipline of DNA nanorobotics that make use of synthetic DNA to self-assemble operational molecular-scale devices. Recently there have been a series of quite astonishing experimental results which h ... Full text Cite

Biomolecular Computing Systems

Journal Article · December 21, 2012 Full text Cite

Local parallel biomolecular computation

Journal Article International Journal of Unconventional Computing · December 1, 2012 Biomolecular Computation (BMC) is computation at the molecular scale, using biotechnology engineering techniques. Most proposed methods for BMC used distributed (molecular) parallelism (DP); where operations are executed in parallel on large numbers of dis ... Cite

Mechanical computing: The computational complexity of physical devices

Chapter · November 1, 2012 Article Outline: Glossary Definition of the Subject Introduction The Computational Complexity of Motion Planning and Simulation of Mechanical Devices Concrete Mechanical Computing Devices Future Directions Acknowledgments Bibliography ... Full text Cite

Tile complexity of linear assemblies

Journal Article SIAM Journal on Computing · September 24, 2012 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 ... Full text Cite

Meta-DNA: synthetic biology via DNA nanostructures and hybridization reactions.

Journal Article Journal of the Royal Society, Interface · July 2012 Can a wide range of complex biochemical behaviour arise from repeated applications of a highly reduced class of interactions? In particular, can the range of DNA manipulations achieved by protein enzymes be simulated via simple DNA hybridization chemistry? ... Full text Cite

Engineering natural computation by autonomous DNA-based biomolecular devices

Chapter · January 1, 2012 This chapter overviews the past and current state of a selected part of the emerging research area of DNA-based biomolecular devices. We particularly emphasize molecular devices that are: autonomous, executing steps with no exterior mediation after startin ... Full text Cite

Self-Assembled DNA Nanostructures and DNA Devices

Chapter · January 1, 2012 The particular molecular-scale constructs that are the topic of this chapter are known as DNA nanostructures. As will be explained, DNA nanostructures have some unique advantages among nanostructures: they are relatively easy to design, fairly predictable ... Full text Cite

Localized hybridization circuits

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · September 29, 2011 Molecular computing executed via local interactions of spatially contiguous sets of molecules has potential advantages of (i) speed due to increased local concentration of reacting species, (ii) generally sharper switching behavior and higher precision due ... Full text Cite

Biochemistry. Scaling up DNA computation.

Journal Article Science (New York, N.Y.) · June 2011 Full text Cite

Keynote: DNA-based molecular devices

Journal Article 2011 IEEE 1st International Conference on Computational Advances in Bio and Medical Sciences, ICCABS 2011 · April 14, 2011 We overview recent work in the field of DNA-based autonomous biomolecular devices. We particularly emphasize molecular assemblies and molecular devices that are (i) self-assembled: that is they assemble into DNA nanostructures in one stage without explicit ... Full text Cite

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

Journal Article Theoretical Computer Science · April 8, 2011 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 fundamen ... Full text Cite

Asymptotically optimal kinodynamic motion planning for a class of modular self-reconfigurable robots

Journal Article International Journal of Computational Geometry and Applications · April 1, 2011 Self-reconfigurable robots are composed of many individual modules that can autonomously move to transform the shape and structure of the robot. The task of self-reconfiguration, transforming a set of modules from one arrangement to another specified arran ... Full text Cite

Design and construction of double-decker tile as a route to three-dimensional periodic assembly of DNA.

Journal Article Journal of the American Chemical Society · March 2011 DNA is a useful material for nanoscale construction. Due to highly specific Watson-Crick base pairing, the DNA sequences can be designed to form small tiles or origami. Adjacent helices in such nanostructures are connected via Holliday junction-like crosso ... Full text Cite

Design of a biomolecular device that executes process algebra

Journal Article Natural Computing · March 1, 2011 Process algebras are widely used for defining the formal semantics of concurrent communicating processes. This paper considers stochastic π-calculus which is a particularly expressive kind of process algebra providing a specification of probabilities of pr ... Full text Cite

High-fidelity DNA hybridization using programmable molecular DNA devices

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · February 1, 2011 The hybridization of complementary nucleic acid strands is the most basic of all reactions involving nucleic acids, but has a major limitation: the specificity of hybridization reactions depends critically on the lengths of the complementary pairs of stran ... Full text Cite

Robomotion: Scalable, physically stable locomotion for self-reconfigurable robots

Journal Article Springer Tracts in Advanced Robotics · December 20, 2010 Self-reconfigurable robots have an intriguingly flexible design, composing a single robot with many small modules that can autonomously move to transform the robot's shape and structure. Scaling to a large number of modules is necessary to achieve great fl ... Full text Cite

Capabilities and limits of compact error resilience methods for algorithmic self-assembly

Journal Article Algorithmica (New York) · April 1, 2010 Winfree's pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly (Winfree and Bekbolatov in DNA Based Computers 9, LNCS, vol. 2943, pp. 126-144, [2004]), but the construction resulted in increase of the size of asse ... Full text Cite

Isothermal reactivating Whiplash PCR for locally programmable molecular computation

Journal Article Natural Computing · January 1, 2010 Whiplash PCR (WPCR; Hagiya et al., in Rubin H, Woods DH (eds) DNA based computers, vol III, pp 55-72. American Mathematical Society, Providence, RI, 1999) is a novel technique for autonomous molecular computation where a state machine is implemented with a ... Full text Cite

Design of a biomolecular device that executes process algebra

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 11, 2009 Process algebras are widely used to define the formal semantics of concurrent communicating processes. In this paper, we implement a particularly expressive form of process algebra, known as stochastic π-calculus, at the molecular scale by providing a desi ... Full text Cite

A dendritic DNA Nanostructure for target DNA detection

Journal Article Extended Abstracts for 6th Annual Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2009 · December 1, 2009 Cite

Target DNA detection by strand displacement and deoxyribozymogen amplification

Journal Article Extended Abstracts for 6th Annual Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2009 · December 1, 2009 Cite

Conference motivation: The challenge of self-assembly of molecular scale structures

Journal Article Extended Abstracts for 6th Annual Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2009 · December 1, 2009 Cite

Isothermal reactivating whiplash PCR for locally programmable molecular computation

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · November 27, 2009 Whiplash PCR (WPCR), due to Hagiya et al. [1], is a novel technique for autonomous molecular computation where a state machine is implemented with a single stranded DNA molecule and state transition is driven by polymerase and thermal cycles. The significa ... Full text Cite

DNA Nanotechnology and its Biological Applications

Journal Article · November 24, 2009 This chapter presents an overview of the emerging research area of DNA nanostructures and biomolecular devices. We discuss work involving the use of synthetic DNA to self-assemble DNA nanostructure devices. Recently, there have been a series of quite aston ... Full text Cite

Quantum Computing

Journal Article · November 24, 2009 Quantum computation (QC) is a type of computation where unitary and measurement operations are executed on linear superpositions of basis states. This chapter provides a brief introduction to QC. We begin with a discussion of basic models for QC such as qu ... Full text Cite

The tile complexity of linear assemblies

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · November 12, 2009 The conventional Tile Assembly Model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. We describe a natural extension to TAM called the Probabilistic Tile Assembl ... Full text Cite

Autonomous programmable DNA nanorobotic devices using DNAzymes

Journal Article Theoretical Computer Science · April 1, 2009 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 ... Full text Cite

A self-assembly model of time-dependent glue strength

Conference Natural Computing Series · January 1, 2009 Self-assembly is a ubiquitous process in which small objects selforganize into larger and complex structures. In 2000, Rothemund and Winfree proposed a Tile Assembly Model as a mathematical model for theoretical studies of self-assembly.We propose a refine ... Full text Cite

Conference motivation: The challenge of self-assembly of molecular scale structures

Journal Article 5th Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2008 · December 1, 2008 Cite

A framework for modeling DNA based molecular systems

Journal Article Journal of Computational and Theoretical Nanoscience · November 1, 2008 Recent successes in building large scale DNA nanostructures and in constructing DNA nanomechanical devices have inspired scientists to design more complex nanoscale systems. The design process can be made considerably more efficient and robust with the hel ... Full text Cite

A DNA nanotransport device powered by polymerase phi29.

Journal Article Nano letters · November 2008 Polymerases are a family of enzymes responsible for copying or replication of nucleic acids (DNA or RNA) templates and hence sustenance of life processes. In this paper, we present a method to exploit a strand-displacing polymerase phi29 as a driving force ... Full text Cite

Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots

Journal Article Springer Tracts in Advanced Robotics · October 20, 2008 Self-reconfigurable robots are composed of many individual modules that can autonomously move to transform the shape and structure of the robot. In this paper we present a kinodynamically optimal algorithm for the following "x-axis to y-axis" reconfigurati ... Full text Cite

A framework for designing novel magnetic tiles capable of complex self-assemblies

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · September 25, 2008 Self-assembly has been immensely successful in creating complex patterns at the molecular scale. However, the use of self-assembly techniques at the macroscopic level has so far been limited to the formation of simple patterns. For example, in a number of ... Full text Cite

Activatable tiles: Compact, robust programmable assembly and other applications

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · August 27, 2008 While algorithmic DNA self-assembly is, in theory, capable of forming complex patterns, its experimental demonstration has been limited by significant assembly errors. In this paper we describe a novel protection/deprotection strategy to strictly enforce t ... Full text Cite

Autonomous programmable nanorobotic devices using DNAzymes

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · August 27, 2008 A major challenge in nanoscience is the design of synthetic molecular devices that run autonomously and are programmable. DNA-based synthetic molecular devices have the advantage of being relatively simple to design and engineer, due to the predictable sec ... Full text Cite

BIOT 349-Programming molecular tube circumferences

Conference ABSTRACTS OF PAPERS OF THE AMERICAN CHEMICAL SOCIETY · August 17, 2008 Link to item Cite

Programming DNA tube circumferences.

Journal Article Science (New York, N.Y.) · August 2008 Synthesizing molecular tubes with monodisperse, programmable circumferences is an important goal shared by nanotechnology, materials science, and supermolecular chemistry. We program molecular tube circumferences by specifying the complementarity relations ... Full text Cite

Formula dissection: A parallel algorithm for constraint satisfaction

Journal Article Computers and Mathematics with Applications · March 1, 2008 Many well-known problems in Artificial Intelligence can be formulated in terms of systems of constraints. The problem of testing the satisfiability of propositional formulae (SAT) is of special importance due to its numerous applications in theoretical com ... Full text Cite

Optimal kinodynamic motion planning for 2D reconfiguration of self-reconfigurable robots

Conference Robotics: Science and Systems · January 1, 2008 A self-reconfigurable (SR) robot is one composed of many small modules that autonomously act to change the shape and structure of the robot. In this paper we consider a general class of SR robot modules that have rectilinear shape that can be adjusted betw ... Full text Cite

Stochastic analysis of reversible self-assembly

Journal Article Journal of Computational and Theoretical Nanoscience · January 1, 2008 The theoretical basis of computational self-assembly dates back the idea of Wang tiling models in the early 1960s.1 More recently, it has been recognized that self-assembly is a promising route to nano-scale computation and there have been many experimenta ... Full text Cite

Super-resolution video analysis for forensic investigations

Journal Article IFIP International Federation for Information Processing · December 3, 2007 Super-resolution algorithms typically improve the resolution of a video frame by mapping and performing signal processing operations on data from frames immediately preceding and immediately following the frame of interest. However, these algorithms ignore ... Full text Cite

Reversible self-assembly of squares as a rapidly mixing Markov Chain

Journal Article 4th Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2007 · December 1, 2007 Cite

Activatable DNA tiles for compact error-resilient directional assembly

Journal Article 4th Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2007 · December 1, 2007 Cite

Abstract: Single strand DNA tiles and molecular tubes with precisely programmable circumferences

Journal Article 4th Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2007 · December 1, 2007 Cite

Autonomous programmable biomolecular devices using self-assembled DNA nanostructures

Journal Article Communications of the ACM · September 1, 2007 Recent developments in bio-DNA computer science techniques and methods for the development of autonomous programmable biomolecular devices based on self-assembled DNA nanostructures are reviewed. Molecular-scale devices using DNA nanostructures are enginee ... Full text Cite

On robotic optimal path planning in polygonal regions with pseudo-Euclidean metrics.

Conference IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society · August 2007 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) construct ... Full text Cite

Handbook of parallel computing: Models, algorithms and applications

Book · January 1, 2007 The ability of parallel computing to process large data sets and handle time-consuming operations has resulted in unprecedented advances in biological and scientific computing, modeling, and simulations. Exploring these recent developments, the Handbook of ... Full text Cite

Efficient and exact quantum compression

Journal Article Information and Computation · January 1, 2007 We present a divide and conquer based algorithm for optimal quantum compression/decompression, using O(n(log4 n) log log n) elementary quantum operations. Our result provides the first quasi-linear time algorithm for asymptotically optimal (in size and fid ... Full text Cite

Autonomous programmable biomolecular devices using self-assembled DNA nanostructures

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2007 Full text Cite

A framework for modeling DNA based molecular systems

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2006 In this paper, we propose a framework for a discrete event simulator for simulating the DNA based nano-robotical systems. We describe a physical model that captures the conformational changes of the solute molecules. We also present methods to simulate var ... Full text Cite

Design and simulation of self-repairing DNA lattices

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2006 Self-repair is essential to all living systems, providing the ability to remain functional in spite of gradual damage. In the context of self-assembly of self-repairing synthetic biomolecular systems, recently Winfree developed a method for transforming a ... Full text Cite

Capabilities and limits of compact error resilience methods for algorithmic self-assembly in two and three dimensions

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2006 Winfree's pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly[26], but the construction resulted in increase of the size of assembly. Reif et. al. contributed further in this area with compact error-resilient sch ... Full text Cite

Conference motivation: The challenge of selfassembly of molecular scale structures

Journal Article 3rd Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2006 · December 1, 2006 Cite

A self-assembly model of time-dependent glue strength

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · July 13, 2006 We propose a self-assembly model in which the glue strength between two juxtaposed tiles is a function of the time they have been in neighboring positions. We then present an implementation of our model using strand displacement reactions on DNA tiles. Und ... Full text Cite

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

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · July 13, 2006 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 fundamen ... Full text Cite

Design of autonomous DNA cellular automata

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · July 13, 2006 Recent experimental progress in DNA lattice construction, DNA robotics, and DNA computing provides the basis for designing DNA cellular computing devices, i.e. autonomous nano-mechanical DNA computing devices embedded in DNA lattices. Once assembled, DNA c ... Full text Cite

On boundaries of highly visible spaces and applications

Journal Article Theoretical Computer Science · April 4, 2006 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 b ... Full text Cite

Compact Error-Resilient Computational DNA Tilings.

Conference Nanotechnology: Science and Computation · 2006 Cite

On finding approximate optimal paths in weighted regions

Journal Article Journal of Algorithms · January 1, 2006 The main result of this paper is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The ... Full text Cite

Narrow passage sampling for probabilistic roadmap planning

Journal Article IEEE Transactions on Robotics · December 1, 2005 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 str ... Full text Cite

Self-assembled 1D DNA nanostructures as templates for silver nanowires

Journal Article 2nd Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2005 · December 1, 2005 Cite

Stepwise DNA self-assembly of fixed-size nanostructures

Journal Article 2nd Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2005 · December 1, 2005 Cite

Computation of equilibriain noncooperative games

Journal Article Computers and Mathematics with Applications · September 1, 2005 This paper presents algorithms for finding equilibria of mixed strategy in multistage noncooperative games of incomplete information (like probabilistic blindfold chess, where at every opportunity a player can perform different moves with some probability) ... Full text Cite

Preface

Journal Article Natural Computing · June 1, 2005 Full text Cite

Programmable DNA self-assemblies for nanoscale organization of ligands and proteins.

Journal Article Nano letters · April 2005 We demonstrate the precise control of periodic spacing between individual protein molecules by programming the self-assembly of DNA tile templates. In particular, we report the application of two self-assembled periodic DNA structures, two-dimensional nano ... Full text Cite

Three-Helix Bundle DNA Tiles Self-Assemble into 2D Lattice or 1D Templates for Silver Nanowires.

Journal Article Nano Letters · March 2005 We present a DNA nanostructure, the three- helix bundle (3HB), which consists of three double helical DNA domains connected by six immobile crossover junctions such that the helix axes are not coplanar. The 3HB motif presents a triangular cross-section ... Cite

On finding energy-minimizing paths on terrains

Journal Article IEEE Transactions on Robotics · February 1, 2005 In this paper, 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 im ... Full text Cite

Efficient parallel factorization and solution of structured and unstructured linear systems

Journal Article Journal of Computer and System Sciences · January 1, 2005 This paper gives improved parallel methods for several exact factorizations of some classes of symmetric positive definite (SPD) matrices. Our factorizations also provide us similarly efficient algorithms for exact computation of the solution of the corres ... Full text Cite

Design, simulation, and experimental demonstration of self-assembled DNA nanostructures and motors

Journal Article Lecture Notes in Computer Science · January 1, 2005 Self-assembly is the spontaneous self-ordering of substructures into superstructures, driven by the selective affinity of the substructures. Complementarity of DNA bases renders DNA an ideal material for programmable self-assembly of nanostructures. DNA se ... Full text Cite

Compact error-resilient computational DNA tiling assemblies

Journal Article Lecture Notes in Computer Science · January 1, 2005 The self-assembly process for bottom-up construction of nanostructures is of key importance to the emerging scientific discipline Nanoscience. However, self-assembly at the molecular scale is prone to a quite high rate of error. Such high error rate is a m ... Full text Cite

Design of an autonomous DNA nanomechanical device capable of universal computation and universal translational motion

Journal Article Lecture Notes in Computer Science · January 1, 2005 Intelligent nanomechanical devices that operate in an autonomous fashion are of great theoretical and practical interest. Recent successes in building large scale DNA nano-structures, in constructing DNA mechanical devices, and in DNA computing provide a s ... Full text Cite

Designs of autonomous unidirectional walking DNA devices

Journal Article Lecture Notes in Computer Science · January 1, 2005 Imagine a host of nanoscale DNA robots move autonomously over a microscale DNA nanostructure, each following a programmable route and serving as a nanoparticle and/or an information carrier. The accomplishment of this goal has many applications in nanorobo ... Full text Cite

A unidirectional DNA walker that moves autonomously along a track.

Journal Article Angewandte Chemie (International ed. in English) · September 2004 Full text Cite

Electronic nanostructures templated on self-assembled DNA scaffolds

Journal Article Nanotechnology · July 2004 We report on the self-assembly of one- and two-dimensional DNA scaffolds, which serve as templates for the targeted deposition of ordered nanoparticles and molecular arrays. TheDNAnanostructures are easy to reprogram, and we demonstrate two distinct con ... Link to item Cite

Movement planning in the presence of flows

Journal Article Algorithmica (New York) · February 1, 2004 This paper investigates the problem of time-optimum movement planning in two and three dimensions for a point robot which has bounded control velocity through a set of n polygonal regions of given translational flow velocities. This intriguing geometric pr ... Full text Cite

DNA nanotubes self-assembled from triple-crossover tiles as templates for conductive nanowires.

Journal Article Proceedings of the National Academy of Sciences of the United States of America · January 2004 DNA-based nanotechnology is currently being developed as a general assembly method for nanopatterned materials that may find use in electronics, sensors, medicine, and many other fields. Here we present results on the construction and characterization of D ... Full text Cite

DNA-templated self-assembly of protein and nanoparticle linear arrays.

Journal Article Journal of the American Chemical Society · January 2004 Self-assembling DNA tiling lattices represent a versatile system for nanoscale construction. Self-assembled DNA arrays provide an excellent template for spatially positioning other molecules with increased relative precision and programmability. Here we re ... Full text Cite

Deriving efficient graph algorithms

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2004 Two case studies are presented that demonstrate the systematic derivation of efficient algorithms from simple combinatorial definitions. These case studies contribute to an exploration of evolutionary approaches to the explanation, proof, adaptation, and p ... Cite

DNA-based cryptography

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2004 Recent research has considered DNA as a medium for ultra-scale computation and for ultra-compact information storage. One potential key application is DNA-based, molecular cryptography systems. We present some procedures for DNA-based cryptography based on ... Cite

Self-assembled DNA structures for nanoconstruction

Conference DNA-BASED MOLECULAR ELECTRONICS · January 1, 2004 Link to item Cite

On energy-minimizing paths on terrains for a mobile robot

Journal Article Proceedings - IEEE International Conference on Robotics and Automation · December 9, 2003 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 caus ... Cite

The bridge test for sampling narrow passages with probabilistic roadmap planners

Journal Article Proceedings - IEEE International Conference on Robotics and Automation · December 9, 2003 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 st ... Cite

The design of autonomous DNA nano-mechanical devices: Walking and rolling DNA

Journal Article Natural Computing · December 1, 2003 We provide designs for the first autonomous DNA nanomechanical devices that execute cycles of motion without external environmental changes. These DNA devices translate along a circular strand of ssDNA and rotate simultaneously. The designs use various ene ... Full text Cite

Parallel molecular computations of pairwise exclusive-or (XOR) using DNA "string tile" self-assembly.

Journal Article J Am Chem Soc · November 26, 2003 Self-assembling DNA nanostructures are an efficient means of executing parallel molecular computations. However, previous experimental demonstrations of computations by DNA tile self-assembly only allowed for one set of distinct input to be processed at a ... Full text Link to item Cite

A two-state DNA lattice switched by DNA nanoactuator.

Journal Article Angew Chem Int Ed Engl · September 22, 2003 Full text Link to item Cite

On frictional mechanical systems and their computational power

Journal Article SIAM Journal on Computing · September 1, 2003 A class of mechanical systems connected by frictional contact linkages between surfaces and their computational power were described. A universal Turing machine (TM) was simulated by a universal frictional mechanical system. It was found that the robotic m ... Full text Cite

Guest Editor's Foreword

Journal Article Journal of Computer and System Sciences · September 2003 Full text Cite

Step-wise assembly of DNA tilings and their applications.

Conference ABSTRACTS OF PAPERS OF THE AMERICAN CHEMICAL SOCIETY · September 1, 2003 Link to item Cite

Directed nucleation assembly of DNA tile complexes for barcode-patterned lattices.

Journal Article Proc Natl Acad Sci U S A · July 8, 2003 The programmed self-assembly of patterned aperiodic molecular structures is a major challenge in nanotechnology and has numerous potential applications for nanofabrication of complex structures and useful devices. Here we report the construction of an aper ... Full text Link to item Cite

On boundaries of highly visible spaces and applications

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2003 The purpose of this paper is to investigate the properties of a certain class of highly visible spaces. For a given geometric space S containing obstacles specified by disjoint subsets of S, the free space ℱ is defined to be the portion of S not occupied b ... Full text Cite

Adaptive and compact discretization for weighted region optimal path finding

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2003 This paper presents several results on the weighted region optimal path problem. An often-used approach to approximately solve this problem is to apply a discrete search algorithm to a graph Gε generated by a discretization of the problem; this graph guara ... Full text Cite

DNA nanotubes: Construction and characterization of filaments composed of TX-tile lattice

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2003 DNA-based nanotechnology is currently being developed for use in biomolecular computation, fabrication of 2D tile lattices, and engineering of 3D periodic matter. Here we present recent results on the construction and characterization of DNA nanotubes - a ... Full text Cite

The design of autonomous DNA nanomechanical devices: Walking and rolling DNA

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2003 We provide designs for the first autonomous DNA nanomechanical devices that execute cycles of motion without external environmental changes. These DNA devices translate across a circular strand of ssDNA and rotate simultaneously. The designs use various en ... Full text Cite

Overview of new structures for DNA-Based nanofabrication and computation

Conference PROCEEDINGS OF THE 7TH JOINT CONFERENCE ON INFORMATION SCIENCES · January 1, 2003 Link to item Cite

Computing. Successes and challenges.

Journal Article Science (New York, N.Y.) · April 2002 Full text Cite

Experimental construction of very large scale DNA databases with associative search capability

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2002 We describe on-going experiments for executing associative search queries within synthesized DNA databases. Queries are executed by hybridization of a target database strand with a complementary query strand probe. In our initial annealing experiments for ... Full text Cite

Molecular assembly and Computation: From theory to experimental demonstrations

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2002 While the topic of Molecular Computation would have appeared even a half dozen years ago to be purely conjectural, it now is an emerging subfield of computer science with the development of its theoretical basis and a number of moderate to large-scale expe ... Full text Cite

DNA lattices: A method for molecular-scale patterning and computation

Journal Article Computing in Science and Engineering · January 1, 2002 The developments in the field of DNA lattice research for molecular-scale computation and programmable pattern formation were discussed. Self assembled DNA nanostructures methodology involves the artificial synthesis of single strand DNA molecules that sel ... Full text Cite

Decision algorithms for multiplayer noncooperative games of incomplete information

Journal Article Computers and Mathematics with Applications · January 1, 2002 Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether ... Full text Cite

The emerging discipline of biomolecular computation in the US

Journal Article New Generation Computing · January 1, 2002 This paper provides a description of the recent evolution in the US of an emerging technology known as DNA Computation or more generally as Biomolecular Computation from its early stages to its development and extension into other areas such as nanotechnol ... Full text Cite

Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, 19-21 May 2002: Foreword

Journal Article Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 2002 Cite

BUSHWHACK: An approximation algorithm for minimal paths through pseudo-euclidean spaces

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2001 In this paper we define piecewise pseudo-Euclidean optimal path problems, where each region has a distinct cost metric of a class we call pseudo-Euclidean, that allows the path cost to possibly vary within the region in a predictable and efficiently comput ... Full text Cite

Optimal encoding of non-stationary sources

Journal Article Information Sciences · June 1, 2001 The usual assumption for proofs of the optimality of lossless encoding is a stationary ergodic source. Dynamic sources with non-stationary probability distributions occur in many practical situations where the data source is formed from a composition of di ... Full text Cite

Challenges and applications for self-assembled DNA nanostructures

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2001 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 mat ... Full text Cite

Computationally inspired biotechnologies: Improved DNA synthesis and associative search using error-correcting codes and vector-quantization

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2001 The main theme of this paper is to take inspiration from methods used in computer science and related disciplines, and to apply these to develop improved biotechnology. In particular, our proposed improvements are made by adapting various information theor ... Full text Cite

Parallel output-sensitive algorithms for combinatorial and linear algebra problems

Journal Article Journal of Computer and System Sciences · January 1, 2001 This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n × n matrices over a fixed ground ... Full text Cite

Lower bounds for multiplayer noncooperative games of incomplete information

Journal Article Computers and Mathematics with Applications · January 1, 2001 This paper extends the alternating Turing machine (A-TM) of Chandra, Kozen and Stockmeyer, the private and the blind alternating machines of Reif to model multiplayer games of incomplete information. We use these machines to provide matching lower bounds f ... Full text Cite

Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix

Journal Article Algorithmica (New York) · January 1, 2001 This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications, the matrices are symmetric and sparse: with O(n) non-zero entries. The problem has an efficient sequential solution in this ... Full text Cite

Programmable assembly at the molecular scale: Self-assembly of DNA lattices (invited paper)

Journal Article Proceedings - IEEE International Conference on Robotics and Automation · January 1, 2001 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 mat ... Cite

XOR operations by algorithmic assembly of DNA tiles

Conference BIOPHYSICAL JOURNAL · January 1, 2001 Link to item Cite

An efficient approximation for weighted region shortest path problem

Conference ALGORITHMIC AND COMPUTATIONAL ROBOTICS: NEW DIRECTIONS · January 1, 2001 Link to item Cite

Movement planning in the presence of flows

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2001 This paper investigates the problem of time-optimum movement planning in d = 2, 3 dimensions for a point robot which has bounded control velocity through a set of n polygonal regions of given translational flow velocities. This intriguing geometric problem ... Full text Cite

Nonuniform discretization for kinodynamic motion planning and its applications

Journal Article SIAM Journal on Computing · December 1, 2000 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 acc ... Full text Cite

Fast spatial decomposition and closest pair computation for limited precision input

Journal Article Algorithmica (New York) · November 1, 2000 In this paper we show that if the input points to the geometric closest pair problem are given with limited precision (each coordinate is specified with O(log n) bits), then we can compute the closest pair in O (n log log n) time. We also apply our spatial ... Full text Cite

Logical computation using algorithmic self-assembly of DNA triple-crossover molecules.

Journal Article Nature · September 2000 Recent work has demonstrated the self-assembly of designed periodic two-dimensional arrays composed of DNA tiles, in which the intermolecular contacts are directed by 'sticky' ends. In a mathematical context, aperiodic mosaics may be formed by the self-ass ... Full text Cite

Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes

Journal Article Journal of the American Chemical Society · March 8, 2000 This paper extends the study and prototyping of unusual DNA motifs, unknown in nature, but founded on principles derived from biological structures. Artificially designed DNA complexes show promise as building blocks for the construction of useful nanoscal ... Full text Cite

On the impossibility of interaction-free quantum sensing for small I/O bandwidth

Journal Article Information and Computation · January 1, 2000 A method for (nearly) interaction-free measurement (IFM) specifies the design of a quantum optical sensing system that is able to determine with arbitrarily high likelihood if an obstructing body has been inserted into the system, without moving or modifyi ... Full text Cite

Micro flow bio-molecular computation.

Journal Article Bio Systems · October 1999 In this paper we provide a model for micro-flow based bio-molecular computation (MF-BMC). It provides an abstraction for the design of algorithms which account for the constraints of the model. Our MF-BMC model uses abstractions of both the recombinant DNA ... Full text Cite

Efficient approximate solution of sparse linear systems (vol 36, pg 37, 1998)

Journal Article COMPUTERS & MATHEMATICS WITH APPLICATIONS · July 1, 1999 Link to item Cite

Social potential fields: A distributed behavioral control for autonomous robots

Journal Article Robotics and Autonomous Systems · May 31, 1999 A Very Large Scale Robotic (VLSR) system may consist of from hundreds to perhaps tens of thousands or more autonomous robots. The costs or robots are going down, and the robots are getting more compact, more capable, and more flexible. Hence, in the near f ... Full text Cite

Efficient algorithmic learning of the structure of permutation groups by examples

Journal Article Computers and Mathematics with Applications · January 1, 1999 This paper discusses learning algorithms for ascertaining membership, inclusion, and equality in permutation groups. The main results are randomized learning algorithms which take a random generator set of a fixed group G≤Sn as input. We discuss randomized ... Full text Cite

Approximate complex polynomial evaluation in near constant work per point

Journal Article SIAM Journal on Computing · January 1, 1999 The n complex coefficients of a degree n-1 complex polynomial are given and this polynomial is evaluated 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 algori ... Full text Cite

Parallel biomolecular computation: Models and simulations

Journal Article Algorithmica (New York) · January 1, 1999 This paper is concerned with the development of techniques for massively parallel computation at the molecular scale, which we refer to as molecular parallelism. While this may at first appear to be purely science fiction, Adleman [Ad1] has already employe ... Full text Cite

Synthesizing efficient out-of-core programs for block recursive algorithms using block-cyclic data distributions

Journal Article IEEE Transactions on Parallel and Distributed Systems · January 1, 1999 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 whi ... Full text Cite

Alternative computational models: A comparison of biomolecular and quantum computation extended abstract

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 1998 Molecular Computation (MC) is massively parallel computation where data is stored and processed within objects of molecular size. Biomolecular Computation (BMC) is MC using biotechnology techniques, e.g. recombinant DNA operations. In contrast, Quantum Com ... Full text Cite

High-resolution inset head-mounted display.

Journal Article Applied optics · July 1998 A novel approach to inset superimposition in a high-resolution head-mounted display (HMD) is presented. The approach is innovative in its use of optoelectronic, nonmechanical devices in place of scanning mechanical devices commonly adopted previously. A pa ... Full text Cite

The complexity of the two dimensional curvature-constrained shortest-path problem

Conference ROBOTICS: THE ALGORITHMIC PERSPECTIVE · 1998 Cite

Efficient Approximate Solution of Sparse Linear Systems

Journal Article Computers and Mathematics with Applications · January 1, 1998 We consider the problem of approximate solution cursive Greek chī of of a linear system Acursive Greek chi = b over the reals, such that ∥Acursive Greek chī - b∥ ≤ ej|6||, for a given ∈, 0 < ∈ < 1. This is one of the most fundamental of all computational p ... Full text Cite

Optimal lossless compression of a class of dynamic sources

Journal Article Data Compression Conference Proceedings · January 1, 1998 The usual assumption for proofs of the optimality of lossless encoding is a stationary ergodic source. Dynamic sources with a non-stationary probability distributions occur in many practical situations where the data source is constructed by a composition ... Cite

A Randomized Parallel Algorithm for Planar Graph Isomorphism

Journal Article Journal of Algorithms · January 1, 1998 We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known a ... Full text Cite

Paradigms for biomolecular computation

Journal Article UNCONVENTIONAL MODELS OF COMPUTATION · January 1, 1998 Link to item Cite

The computational power of frictional mechanical systems

Conference ROBOTICS: THE ALGORITHMIC PERSPECTIVE · January 1, 1998 Link to item Cite

Autonomous search by robots and animals: A survey

Journal Article Robotics and Autonomous Systems · November 10, 1997 This paper is a survey of research on autonomous search strategies which originate in engineering and biology. Our motivation is to identify methods of search in an essentially two-dimensional Euclidean space, which can be applied to the area of demining. ... Full text Cite

Efficient parallel algorithms for optical computing with the discrete Fourier transform (DFT) primitive.

Journal Article Applied optics · October 1997 Optical-computing technology offers new challenges to algorithm designers since it can perform an n-point discrete Fourier transform (DFT) computation in only unit time. Note that the DFT is a nontrivial computation in the parallel random-access machine mo ... Full text Cite

Non-uniform discretization approximations for kinodynamic motion planning and its applications

Conference ALGORITHMS FOR ROBOTIC MOTION AND MANIPULATION · 1997 Cite

Error-resilient optimal data compression

Journal Article SIAM Journal on Computing · January 1, 1997 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 invest ... Full text Cite

Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1

Journal Article Algorithmica (New York) · January 1, 1997 We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n) log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, log log n on the CCRW PRAM, f(n) is o(n3 ... Full text Cite

On Dynamic Algorithms for Algebraic Problems

Journal Article Journal of Algorithms · January 1, 1997 In this paper, we examine the problem of incrementally evaluating algebraic functions. In particular, if f(x1, x2, . . . , xn) = (y1, y2, . . . , ym) is an algebraic problem, we consider answering on-line requests of the form "change input xi to value v" o ... Full text Cite

Fast and compact volume rendering in the compressed transform domain

Journal Article Data Compression Conference Proceedings · January 1, 1997 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 t ... Cite

Approximate complex polynomial evaluation in near constant work per point

Journal Article Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 1997 The polynomial at a large number of m≥n of points on the complex plane given the n complex coefficients of a degree n - 1 complex polynomial is evaluated. This problem is required by many algebraic computations and is considered in most basic algorithm tex ... Full text Cite

Low-cost prevention of error-propagation for data compression with dynamic dictionaries

Journal Article Data Compression Conference Proceedings · January 1, 1997 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 provid ... Cite

Optical delay line memory model with efficient algorithms

Journal Article Optical Engineering · January 1, 1997 The extremely high data rates of optical computing technology (100 Mwords/s and upward) present unprecedented challenges in the dynamic memory design. An optical fiber loop used as a delay line is the best candidate for primary, dynamic memory at this time ... Full text Cite

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

Journal Article Information and Computation · November 25, 1996 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 pr ... Full text Cite

A refinement methodology for developing Data-Parallel applications

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1996 Data-parallelism is a relatively well-understood form of parallel computation, yet developing simple applications can involve substantial efforts to express the problem in low-level data-parallel notations. We describe a process of software development for ... Full text Cite

Synthesizing efficient out-of-core programs for block recursive algorithms using block-cyclic data distributions

Conference Proceedings of the International Conference on Parallel Processing · January 1, 1996 This paper presents a framework for synthesizing I/O-efficient out-of-core programs for block recursive algorithms, such as the fast Fourier transform and matrix transpositions. the programs are synthesized from tensor (Kronecker) product representations o ... Full text Cite

An algebraic technique for generating optimal CMOS circuitry in linear time

Journal Article Computers and Mathematics with Applications · January 1, 1996 We explore a method for quickly generating optimal CMOS functional circuits. The method is based upon an algebra we have derived that describes the composition of parallel-series graphs and their duals simultaneously, and as such, exactly describes the lay ... Full text Cite

An efficient algorithm for the complex roots problem

Journal Article Journal of Complexity · January 1, 1996 Given a univariate polynomial f(z) of degree n with complex coefficients, whose norms are less than 2m in magnitude, the root problem is to find all the roots of f(z) up to specified precision 2-μ. Assuming the arithmetic model for computation, we provide ... Full text Cite

Optical design and analysis of a head-mounted display with a high-resolution insert

Journal Article Proceedings of SPIE - The International Society for Optical Engineering · December 1, 1995 In a previous paper by the authors, a High-Resolution Insert Head-Mounted Display (HRI- HMD) that uses only fixed electronic devices was proposed and designed. The design concept is innovative and it is the first and only known such design to implement a h ... Cite

Efficient parallel solution of sparse eigenvalue and eigenvector problems

Journal Article Annual Symposium on Foundations of Computer Science - Proceedings · December 1, 1995 A new algorithm for computing the characteristic polynomial of a symmetric sparse matrix is given. An interesting algebraic version of Nested Dissection is derived, which constructs a sparse factorization of the matrix A - λI where A is the input matrix. W ... Cite

Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1995 This paper introduces average case analysis of fully dynamic graph connectivity (when the operations are edge insertions and deletions). To this end we introduce the model of stochastic graph processes, i.e. dynamically changing random graphs with random e ... Full text Cite

Models and resource metrics for parallel and distributed computation

Conference Proceedings of the Annual Hawaii International Conference on System Sciences · January 1, 1995 Presents a framework of using resource metrics to characterize the various models of parallel computation. Our framework reflects the approach of recent models to abstract architectural details into several generic parameters, which we call resource metric ... Full text Cite

An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains

Journal Article Mathematical and Computer Modelling · January 1, 1995 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. For example, our results apply directly to terrain maps. A distinguishing feature of our ... Full text Cite

The light bulb problem

Journal Article Information and Computation · January 1, 1995 In this paper, we consider the problem of correlational learning and present algorithms to determine correlated objects. © 1995 Academic Press, Inc. ... Full text Cite

Design and applications of a high-resolution insert head-mounted-display

Journal Article Proceedings - Virtual Reality Annual International Symposium · January 1, 1995 In this paper, a new Head Mounted Display (HMD) that provides a large field of view with a high-resolution insert is proposed and designed. Previously, this type of HMD has been designed using mechanical or sequential scanning devices, which are bulky and ... Cite

Parallel molecular computation

Journal Article Annual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1995 Techniques for quickly executing lengthy computations by the use of molecular parallelism are described. It is demonstrated that molecular computations can be done using short DNA strands by more or less conventional biotechnology engineering techniques wi ... Full text Cite

Fast pattern matching for entropy bounded text

Journal Article Data Compression Conference Proceedings · January 1, 1995 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 r ... Cite

Social potential fields: A distributed behavioral control for autonomous robots

Conference ALGORITHMIC FOUNDATIONS OF ROBOTICS · January 1, 1995 Link to item Cite

Directed s-t numberings, Rubber bands, and testing digraph k-vertex connectivity

Journal Article Combinatorica · December 1, 1994 Let G=(V, E) be a directed graph and n denote |V|. We show that G is k-vertex connected iff for every subset X of V with |X| =k, there is an embedding of G in the (k-1)-dimensional space Rk-1, f:V→Rk-1, such that no hyperplane contains k points of {f(v)|v∈ ... Full text Cite

Computability and complexity of ray tracing

Journal Article Discrete & Computational Geometry · December 1, 1994 The ray-tracing problem is, given an optical system and the position and direction of an initial light ray, to decide if the light ray reaches some given final position. For many years ray tracing has been used for designing and analyzing optical systems. ... Full text Cite

Dynamic parallel tree contraction (extended abstract)

Conference Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 · August 1, 1994 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 ... Full text Cite

O(log2n) time efficient parallel factorization of dense, sparse separable, and banded matrices

Conference Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 · August 1, 1994 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 ty ... Full text Cite

A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions

Journal Article Journal of the ACM (JACM) · January 9, 1994 We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with 1994 polyhedral obstacles. Prior to this work, the best known algorithm required double-exponential time. Given that the ... Full text Cite

Shortest Paths in the Plane with Polygonal Obstacles

Journal Article Journal of the ACM (JACM) · January 9, 1994 We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with 1994 polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required (n2 l ... Full text Cite

Motion Planning in the Presence of Moving Obstacles

Journal Article Journal of the ACM (JACM) · January 7, 1994 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 ... Full text Cite

Free space optical message routing for high performance parallel computers

Conference Proceedings of the 1st International Workshop on Massively Parallel Processing Using Optical Interconnections, MPPOI 1994 · January 1, 1994 We survey various electrooptical message routing systems for sending N messages between N processors and discuss the theory and practice of these systems. In particular, we compare these proposed systems with respect to various metrics including time, spac ... Full text Cite

An O(n1+ε log B) algorithm for the complex roots problem

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 1994 Given a univariate polynomial f(z) of degree n with complex coefficients, whose real ana imaginary parts can be expressed as a ratio of two integers less than 2m in magnitude, the root problem is to find all the roots of f(z) up to specified precision 2_μ. ... Full text Cite

Optical Computing Techniques for Image/Video Compression

Journal Article Proceedings of the IEEE · January 1, 1994 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 compressio ... Full text Cite

Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications

Journal Article SIAM Journal on Computing · January 1, 1994 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 t ... Full text Cite

Approximate kinodynamic planning using L2-norm dynamic bounds

Journal Article Computers and Mathematics with Applications · January 1, 1994 In this paper we address the issue of kinodynamic motion planning. Given a point that moves with bounded acceleration and velocity, we wish to find the time-optimal trajectory from a start state to a goal state (a state consists of both a position and a ve ... Full text Cite

Dynamic algebraic algorithms

Journal Article Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 1994 The authors examine the problem of incrementally evaluating algebraic functions. The paper presents both lower bounds and algorithm design techniques for algebraic problems. The first presentation deals with the lower bounds for simply stated algebraic pro ... Cite

Planarity testing in parallel

Journal Article Journal of Computer and System Sciences · January 1, 1994 We present a parallel algorithm based on open ear decomposition to construct an embedding of a graph onto the plane or report that the graph is nonplanar. Our parallel algorithm runs on a CRCW PRAM in logarithmic time with a number of processors bounded by ... Full text Cite

Models and resource metrics for parallel and distributed computation

Journal Article Proceedings of the International Conference on Parallel Processing · January 1, 1994 Various massively parallel computers have emerged in recent years. Each of then have some distinct architecture properties that challenge the computer scientist to develop algorithms and software appropriate to that specified architecture. This is at least ... Cite

Data compression techniques for stock market prediction

Journal Article Proceedings of the Data Compression Conference · January 1, 1994 This paper presents advanced data compression techniques for predicting stock markets behavior under widely accepted market models in finance. Our techniques are applicable to technical analysis, portfolio theory, and nonlinear market models. We find that ... Cite

O(n log3 n) algorithm for the real root problem

Journal Article Annual Symposium on Foundatons of Computer Science (Proceedings) · December 1, 1993 Given a univariate complex polynomial f(x) of degree n with rational coefficients expressed as a ratio of two integers <2m, the root problem is to find all the roots of f(x) up to specified precision 2-μ. In this paper we assume the arithmetic model for co ... Cite

Using difficulty of prediction to decrease computation: Fast sort, priority queue and convex hull on entropy bounded inputs

Journal Article Annual Symposium on Foundatons of Computer Science (Proceedings) · December 1, 1993 There is an upsurge in interest in the Markov model and also more general stationary ergodic stochastic distributions in theoretical computer science community recently (e.g. see [Vitter, Krishnan91], [Karlin, Philips, Raghavan92], [Raghavan92] for use of ... Cite

Continuous alternation: The complexity of pursuit in continuous domains

Journal Article Algorithmica · October 1, 1993 Complexity theory has used a game-theoretic notion, namely alternation, to great advantage in modeling parallelism and in obtaining lower bounds. The usual definition of alternation requires that transitions be made in discrete steps. The study of differen ... Full text Cite

Parallel and output sensitive algorithms for combinatorial and linear algebra problems

Conference Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993 · August 1, 1993 The notion of output sensitive parallel algorithms for linear algebra problems is formalized in this paper, and such algorithms are presented for finding the rank of an n x n matrix in randomized parallel time 0(log n + logR) using 0(n2 + M(R)) processors, ... Full text Cite

Kinodynamic Motion Planning

Journal Article Journal of the ACM (JACM) · January 11, 1993 Kinodynamic planmng 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 ... Full text Cite

The complexity of N-body simulation

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1993 The n-body simulation problem is stated as follows: Given initial positions and velocities of n particles that have pair-wise force interactions, simulate the movement of these particles so as to determine the positions of the particles at a future time. I ... Full text Cite

A dynamic separator algorithm

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1993 Our work is based on the pioneering work in sphere separators of Miller, Teng, Vavasis et al, [8, 12], who gave efficient static algorithms for finding sphere separators of size s(n)=O(Formula Presented) for a set of points in Rd. We present randomized, dy ... Full text Cite

Multispectral image compression algorithms

Conference Data Compression Conference Proceedings · January 1, 1993 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 compre ... Full text Cite

Fast and efficient parallel solution of sparse linear systems

Journal Article SIAM Journal on Computing · January 1, 1993 This paper presents a parallel algorithm for the solution of a linear system Ax = b with a sparse n × 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 ... Full text Cite

Probabilistic parallel prefix computation

Journal Article Computers and Mathematics with Applications · January 1, 1993 Given inputs x1,...,xn, which are independent identically distributed random variables over a domain D, and an associative operation \to;, the probabilistic prefix computation problem is to compute the product x1 \to; x2 \to; ... \to; xn and its n - 1 pref ... Full text Cite

On the Design and Implementation of a Lossless Data Compression and Decompression Chip

Journal Article IEEE Journal of Solid-State Circuits · January 1, 1993 A lossless data compression and decompression (LDCD) algorithm based on the notion of textual substitution has been implemented in silicon using a linear systolic array architecture. This algorithm employs a model where the encoder and decoder each have a ... Full text Cite

Generalized compact multi-grid

Journal Article Computers and Mathematics with Applications · January 1, 1993 Extending our recent work, based on the ideas of the multi-grid iteration, we decrease the storage space for a smooth solution of a nonlinear PDE and, furthermore, for any smooth function on a multi-dimensional grid and on discretization sets other than gr ... Full text Cite

Optical expanders with applications in optical computing.

Journal Article Applied optics · January 1993 An optical system called the optical expander is described and investigated. The optical expander electro-optically expands an optical Boolean pattern encoded in d bits into an optical pattern of size N bits. It is assumed that d is equal to c log(2)N for ... Full text Cite

Efficient VLSI fault simulation

Journal Article Computers and Mathematics with Applications · January 1, 1993 Let C be an acyclic Boolean circuit with n gates and ≤ n inputs. A circuit manufacture error may result in a "Stuck-at" (S-A) fault in a circuit identical to C except a gate v only outputs a fixed Boolean value. The S-A fault simulation problem for C is to ... Full text Cite

Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem

Journal Article Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 1993 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 pr ... Cite

AN O(N LOG3N) ALGORITHM FOR THE REAL ROOT PROBLEM

Conference 34TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: PROCEEDINGS · 1993 Cite

Prototyping N-body simulation in Proteus

Journal Article Proceedings of the International Conference on Parallel Processing · December 1, 1992 This paper explores the use of Proteus, an architecture-independent language suitable for prototyping parallel and distributed programs. Proteus is a high-level imperative notation based on sets and sequences with a single construct for the parallel compos ... Cite

Optimal randomized parallel algorithms for computational geometry

Journal Article Algorithmica · June 1, 1992 We present parallel algorithms for some fundamental problems in computational geometry which have a running time of O(log n) using n processors, with very high probability (approaching 1 as n → ∞). These include planar-point location, triangulation, and tr ... Full text Cite

Nested annealing: a provable improvement to simulated annealing

Journal Article Theoretical Computer Science · June 1, 1992 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 problem ... Full text Cite

Quad tree structures for image compression applications

Journal Article Information Processing and Management · January 1, 1992 Traditionally, lossy compression schemes have focused on compressing data at fixed bit rates to either communicate information over limited bandwidth communication channels, or to store information in a fixed-size storage media. In this paper we describe a ... Full text Cite

Expected parallel time and sequential space complexity of graph and digraph problems

Journal Article Algorithmica (New York) · 1992 This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum c ... Cite

The power of combining the techniques of algebraic and numerical computing: Improved approximate multipoint polynomial evaluation and improved multipole algorithms

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 1992 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 particl ... Full text Cite

Optical techniques for image compression

Conference Data Compression Conference Proceedings · January 1, 1992 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. We propose optical architectures to execute various image compression techni ... Full text Cite

Compact Multigrid

Journal Article SIAM Journal on Scientific and Statistical Computing · January 1992 Full text Cite

On threshold circuits and polynomial computation

Journal Article SIAM Journal on Computing · January 1, 1992 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 Thre ... Full text Cite

Efficient parallel algorithms for computing all pair shortest paths in directed graphs

Journal Article 4th Annual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1992 We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n)log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, log log n on the CRCW PRAM, f(n) is o(n3) ... Full text Cite

Implementations of randomized sorting on large parallel machines

Journal Article 4th Annual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1992 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 w ... Full text Cite

Space and time efficient implementations of parallel nested dissection

Journal Article 4th Annual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1992 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. Birkhoff and George showed t ... Full text Cite

An exact algorithm for kinodynamic planning in the plane

Journal Article Discrete & Computational Geometry · December 1, 1991 Planning time-optimal motions has been a major focus of research in robotics. In this paper we consider the following problem: given an object in two-dimensional physical space, an initial point, and a final point, plan a time-optimal obstacle-avoiding mot ... Full text Cite

The parallel computation of minimum cost paths in graphs by stream contraction

Journal Article Information Processing Letters · October 25, 1991 We accelerate by a factor of log n and with no increase of the processor bound our previous parallel algorithm for path algebra computation in the case of the minimum cost path computation in an n-vertex graph and, more generally, wherever the path algebra ... Full text Cite

Prototyping parallel and distributed programs in Proteus

Conference Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing 1991 · January 1, 1991 This paper presents Proteus, an architecture-independent language suitable for prototyping parallel and distributed programs. Proteus is a high-level imperative notation based on sets and sequences with a single construct for the parallel composition of pr ... Full text Cite

Image compression methods with distortion controlled capabilities

Conference Data Compression Conference Proceedings · January 1, 1991 Traditionally, lossy compression schemes have focused on compressing data at fixed bit rates in order to communicate information over limited bandwidth communication channels, or to store information in a fixed-size storage media. In this paper we present ... Full text Cite

Parallel tree contraction. Part 2. Further applications

Journal Article SIAM Journal on Computing · January 1, 1991 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 ... Full text Cite

A parallel architecture for high-speed data compression

Journal Article Journal of Parallel and Distributed Computing · January 1, 1991 Data compression is becoming an essential component of high-speed data datmunications and storage. Lossless data compression is when the decompressed data must be identical to the original. Textual substitution methods are among the most powerful approache ... Full text Cite

The computability and complexity of optical beam tracing

Journal Article IEEE Transactions on Industry Applications · January 1, 1991 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 complexit ... Cite

Randomized parallel algorithm for planar graph isomorphism

Journal Article Algorithms and Architectures · December 1, 1990 We present a parallel randomized algorithm for finding if two planar graphs are isomorphic. Assuming that we have a tree of separators for each planar graph, our algorithm takes O(log(n)) time with P = (n1.5·√log(n)) processors with probability to fail of ... Cite

Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications

Journal Article Algorithms and Architectures · December 1, 1990 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 foll ... Cite

A parallel architecture for high speed data compression

Journal Article · December 1, 1990 The authors discuss textual substitution methods. They present a massively parallel architecture for textual substitution that is based on a systolic pipe of 3839 identical processing elements that forms what is essentially an associative memory for string ... Cite

Data flow analysis of distributed communicating processes

Journal Article International Journal of Parallel Programming · February 1, 1990 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 several known technique ... Full text Cite

On the bit-complexity of discrete solutions of PDEs: Compact multigrid

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1990 The topic of Partial Differential Equations (PDEs) is an interesting area where the techniques of discrete mathematics and numerical algorithms can be brought together to solve problems that would normally be considered more properly in the domain of conti ... Full text Cite

Efficient parallel algorithms for optical computing with the DFT primitive

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1990 The optical computing technology offers new challenges to the algorithm designers since it can perform an n-point DFT computation in only unit time. Note that DFT is a non-trivial computation in the PRAM model. We develop two new models, DFT-VLSIO and DFT- ... Full text Cite

Energy complexity of optical computations

Conference Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990 · January 1, 1990 This paper provides lower bounds on the energy consumption and demonstrates an energy-time trade-off in optical computations. All the lower bounds are shown to have the matching upper bounds for a transitive function-shifting. Since the energy consumption ... Full text Cite

Optimal size integer division circuits

Journal Article SIAM Journal on Computing · January 1, 1990 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 com ... Full text Cite

BLITZEN: A highly integrated massively parallel machine

Journal Article Journal of Parallel and Distributed Computing · January 1, 1990 The goal of the BLITZEN project is to construct a physically small, massively parallel, high-performance machine. This paper presents the architecture, organization, and feature set of a highly integrated SIMD array processing chip which has been custom de ... Full text Cite

The bit-complexity of discrete solutions of partial differential equations: Compact multigrid

Journal Article Computers and Mathematics with Applications · January 1, 1990 The topic of partial differential equations (PDEs) is an interesting area where the techniques of discrete mathematics and numerical algorithms can be brought together to solve problems that would normally be considered more properly in the domain of conti ... Full text Cite

Exact algorithm for kinodynamic planning in the plane

Journal Article · January 1, 1990 A long-standing open problem in robotics has been that of devising algorithms for generating time-optimal motions under kinodynamic constraints. This problem has been considered previously in the literature and approximation algorithms have been provided f ... Full text Cite

The light bulb problem

Conference Proceedings of the 2nd Annual Workshop on Computational Learning Theory, COLT 1989 · December 1, 1989 Full text Cite

Holographic routing network for parallel processing machines

Conference Proceedings of SPIE - The International Society for Optical Engineering · January 1, 1989 Dynamic holographic architectures for connecting processors in parallel computers have been generally limited by the response time of the holographic recording media. 1 - 5 In this paper we present a different approach to dynamic optical interconnects invo ... Full text Cite

Optimal parallel algorithm for graph planarity

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1989 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 p ... Full text Cite

Fast and efficient solution of path algebra problems

Journal Article Journal of Computer and System Sciences · January 1, 1989 This paper extends the author's parallel nested dissection algorithm (Pan and Reif, Technical Report 88-18, Computer Science Department, SUNY Albany, 1988) originally devised for solving sparse linear systems. We present a class of new applications of the ... Full text Cite

Optimal and sublogarithmic time randomized parallel sorting algorithms

Journal Article SIAM Journal on Computing · January 1, 1989 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 r ... Full text Cite

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

Journal Article Information and Computation · January 1, 1989 Several articles have noted the usefulness of a retrieval algorithm called sequential interpolation search, and Yao and Yao have proven a lower bound log log N - O(1), showing this algorithm is actually optimal up to an additive constant on unindexed files ... Full text Cite

Optimal size integer division circuits

Journal Article · January 1, 1989 Full text Cite

Fast and efficient parallel solution of dense linear systems

Journal Article Computers and Mathematics with Applications · January 1, 1989 The most efficient previously known parallel algorithms for the inversion of a nonsingular n × n matrix A or solving a linear system Ax = b over the rational numbers require O(log2n) time and M(n) n processors [provided that M(n) processors suffice in orde ... Full text Cite

Randomization in parallel algorithms and its impact on computational geometry

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1989 Randomization offers elegant solutions to some problems in parallel computing. In addition to improved efficiency it often leads to simpler and practical algorithms. In this paper we discuss some of the characteristics of randomized algorithms and also giv ... Full text Cite

BLITZEN: A highly integrated massively parallel machine

Journal Article · December 1, 1988 The design of BLITZEN, a highly integrated chip with 128 processing elements (PEs) is presented. The bit serial processing element is described, and some comparisons with the massively parallel processor (MPP) and the Connection Machine are provided. Local ... Cite

COMPLEXITY OF REACHABILITY IN DISTRIBUTED COMMUNICATING PROCESSES.

Journal Article Acta Informatica · April 1, 1988 A crucial problem in the analysis of communicating processes is the detection of program statements that are unreachable due to communication deadlocks. In this paper, we consider the computational complexity of the reachability problem for various models ... Cite

An efficient output-sensitive hidden-surface removal algorithm and its parallelization

Conference Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988 · January 6, 1988 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 ... Full text Cite

On the complexity of kinodynamic planning

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1988 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 sim ... Full text Cite

An efficient parallel algorithm for planarity

Journal Article Journal of Computer and System Sciences · January 1, 1988 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(log2n) steps on n processors of a parallel RAM. The previous best parallel algorithm for ... Full text Cite

Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM

Journal Article SIAM Journal on Computing · January 1, 1988 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 algo ... Full text Cite

The complexity of reachability in distributed communicating processes

Journal Article Acta Informatica · January 1, 1988 A crucial problem in the analysis of communicating processes is the detection of program statements that are unreachable due to communication deadlocks. In this paper, we consider the computational complexity of the reachability problem for various models ... Full text Cite

A simple three-dimensional real-time reliable cellular array

Journal Article Journal of Computer and System Sciences · January 1, 1988 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 ... Full text Cite

Efficient parallel pseudorandom number generation

Journal Article SIAM Journal on Computing · January 1, 1988 We present a parallel algorithm for pseudorandom number generation. Given a seed of nε truly random bits for any ε>0, our algorithm generates nc pseudorandom bits for any c>1. This takes poly-log time using nε′ processors where ε′=kε for some fixed small c ... Full text Cite

3-dimensional shortest paths in the presence of polyhedral obstacles

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1988 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 "i ... Full text Cite

NESTED ANNEALING - A PROVABLE IMPROVEMENT TO SIMULATED ANNEALING

Journal Article LECTURE NOTES IN COMPUTER SCIENCE · January 1, 1988 Link to item Cite

SOLVING VERY LARGE, SPARSE LINEAR SYSTEMS ON MESH-CONNECTED PARALLEL COMPUTERS.

Journal Article NASA Conference Publication · December 1, 1987 The implementation of Pan and Reif's Parallel Nested Dissection algorithm on mesh-connected parallel computers is described. This is the first known algorithm that allows very large, sparse linear systems of equations to be solved efficiently in polylog ti ... Cite

OPTIMAL RANDOMIZED PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY.

Journal Article Proceedings of the International Conference on Parallel Processing · December 1, 1987 The authors present parallel algorithms for some fundamental problems in computational geometry which have optimal running time with very high probability (approaching 1 as n yields infinity ). These include planar point location, triangulation, trapezoida ... Cite

FORMULA DISSECTION: A PARALLEL ALGORITHM FOR CONSTRAINT SATISFACTION.

Journal Article · December 1, 1987 The authors present a simple and relatively efficient divide-and-conquer method to solve various subclasses of SAT (the problem of testing satisfiability of propositional formulas). The dissection stage of the algorithm splits the original formula into sma ... Cite

Polynomial convolution algorithm for matrix multiplication with application for optical computing.

Journal Article Applied optics · July 1987 First, we describe an algorithm (the polynomial convolution algorithm) for the multiplication of two rectangular matrices A and B. The algorithm codes the matrix elements of A and B into two polynomials in a common indeterminate; the degree of the polynomi ... Full text Cite

A topological approach to dynamic graph connectivity

Journal Article Information Processing Letters · April 20, 1987 A dynamic connectivity problem consists of an initial graph, and a sequence of operations consisting of graph modifications and graph connectivity tests. The size n of the problem is the sum of the maximum number of vertices and edges of the derived graph, ... Full text Cite

Response:solving linear equations.

Journal Article Science (New York, N.Y.) · April 1987 Full text Cite

Lower bounds on the computational efficiency of optical computing systems.

Journal Article Applied optics · March 1987 A general model for determining the computational efficiency of optical computing systems, termed the VLSIO model, is described. It is a 3-D generalization of the wire model of a 2-D VLSI with optical beams (via Gabor's theorem) replacing the wires as comm ... Full text Cite

Minimizing Turns for Discrete Movement in the Interior of a Polygon

Journal Article IEEE Journal on Robotics and Automation · January 1, 1987 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 ... Full text Cite

MINIMIZING TURNS FOR DISCRETE MOVEMENT IN THE INTERIOR OF A POLYGON.

Journal Article IEEE journal of robotics and automation · 1987 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 pa ... Cite

SOME POLYNOMIAL AND TOEPLITZ MATRIX COMPUTATIONS.

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1987 The authors show that for n processors, O(n**2(log**2n plus log b)) arithmetic operations or O(n(log**2n plus log b)) parallel steps suffice in order to approximate with absolute error less than equivalent to 2**m**-**b all the complex zeros of an nth degr ... Full text Cite

NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS.

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1987 Techniques for establishing lower bounds in robot motion planning problems are presented. The method is first applied to the 3-D shortest-path problem and then extended to compliant motion planning with uncertainty in control. Specifically, a point in thre ... Full text Cite

ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION.

Journal Article · January 1, 1987 The author investigates the computational power of threshold circuits. He discovers a relationship with another class of unbounded fan-in circuits which he denotes finite field Z//P//(//n//) circuits, where each node computes either multiple sums or produc ... Cite

A logarithmic time sort for linear size networks

Journal Article Journal of the ACM (JACM) · January 1, 1987 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 ... Full text Cite

Randomized parallel computation

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1987 This paper surveys randomized parallel algorithms found in the literature for various problems in computer science. In particular we will demonstrate the power of randomization as a tool for parallelizing sequential algorithms and introduce the reader to s ... Full text Cite

SURVEY ON ADVANCES IN THE THEORY OF COMPUTATIONAL ROBOTICS.

Journal Article · December 1, 1986 This paper describes work on the computational complexity of various movement planning problems relevant to robotics. This paper is intended only as a survey of previous and current work in this area. The generalized mover's problem is to plan a sequence o ... Cite

Fast and efficient parallel linear programming and linear least squares computations

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1986 We present a new parallel algorithm for computing a least squares solution to a sparse overdetermined system of linear equations Ax=b such that m×n matrix A is sparse and the graph, G = (V,E), of the matrix (Formula presented.) has an s(m+n)-separator fami ... Full text Cite

Efficient Parallel Pseudo-Random Number Generation

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1986 We present a parallel algorithm for pseudo-random number generation. Given a seed of n ε truly random bits for any ε > 0, our algorithm generates n c pseudo-random bits for any c > 1. This takes poly-log time using n ε′ processors where ε′ = κε for some fi ... Full text Cite

Extension of the parallel nested dissection algorithm to path algebra problems

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1986 This paper extends the author's parallel nested dissection algorithm of [PR] originally devised for solving sparse linear systems. We present a class of new applications of the nested dissection method, this time to path algebra computations, (in both case ... Full text Cite

Fast and efficient linear programming and linear least-squares computations

Journal Article Computers and Mathematics with Applications · January 1, 1986 We present a new parallel algorithm for computing a least-squares solution to a sparse overdetermined system of linear equations Ax = b such that the m × n matrix A is sparse and the graph, G = (V, E), of the matrix H= I AT A O has an s(m + n)-separator fa ... Full text Cite

Parallel nested dissection for path algebra computations

Journal Article Operations Research Letters · January 1, 1986 This paper extends the authors' parallel nested dissection algorithm of [13] originally devised for solving sparse linear systems. We present a class of new applications of the nested dissection method, this time to path algebra computations (in both cases ... Full text Cite

Efficient parallel linear programming

Journal Article Operations Research Letters · January 1, 1986 Linear programming and least squares computations are accelerated using author's parallel algorithms for solving linear systems. The implications on the performance of the Karmarkar and the simplex algorithms for dense and sparse linear programs are examin ... Full text Cite

Efficient symbolic analysis of programs

Journal Article Journal of Computer and System Sciences · January 1, 1986 This paper is concerned with constructing, 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. A cover is a mapping from text expressions to such sym ... Full text Cite

The complexity of elementary algebra and geometry

Journal Article Journal of Computer and System Sciences · January 1, 1986 The theory of real closed fields can be decided in exponential space or parallel exponential time. In fixed dimension, the theory can be decided in NC. © 1986. ... Full text Cite

LOGARITHMIC DEPTH CIRCUITS FOR ALGEBRAIC FUNCTIONS.

Journal Article SIAM Journal on Computing · January 1, 1986 This paper describes parallel 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. Furthermore this ... Full text Cite

Arithmetic theories for computational complexity problems

Journal Article Information and Control · January 1, 1986 This paper considers a number of arithmetic theories and shows how the strength of these theories relates to certain open problems in complexity theory concerning the polynomial-time hierarchy. These results are proved quite generally and hold for a wide c ... Full text Cite

EFFICIENT PARALLEL ALGORITHM FOR PLANARITY.

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1986 A parallel algorithm for testing a graph for planarity and for finding an embedding of a planar graph is described. For a graph on n vertices, the algorithm runs in O(log**2 n) steps on n processors of a parallel RAM. The previous best algorithm for planar ... Full text Cite

LINEAR TIME ALGORITHMS FOR OPTIMAL CMOS LAYOUT.

Journal Article · December 1, 1985 We consider the problem of efficient CMOS circuit layout which has been formulated into an interesting graph-theoretical problem. A linear-time algorithm is described for optimal layout of a graph when the circuit topology is fixed. A further linear-time a ... Cite

PARALLEL INTERPOLATION SEARCH.

Journal Article Proceedings - Annual Allerton Conference on Communication, Control, and Computing · December 1, 1985 Several articles have noted the usefulness of a retrieval algorithm called sequential interpolation search, and A. C. Yao and F. F. Yao have proven a lower bound log log N-O(1) showing that this algorithm is actually optimal up to an additive constant on u ... Cite

Depth-first search is inherently sequential

Journal Article Information Processing Letters · June 12, 1985 This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first visited before v in depth-first search order of G. We show that this p ... Full text Cite

Probabilistic algorithms in group theory

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1985 A finite group G is commonly presented by a set of elements which generate G. We argue that for algorithmic purposes a considerably better presentation for a fixed group G is given by random generator set for G: a set of random elements which generate G. W ... Full text Cite

k-connectivity in random undirected graphs

Journal Article Discrete Mathematics · January 1, 1985 This paper concerns vertex connectivity in random graphs. We present results bounding the cardinality of the biggest k-block in random graphs of the Gn,p model, for any constant value of k. Our results extend the work of Erdös and Rényi and Karp and Tarjan ... Full text Cite

A multiprocess network logic with temporal and spatial modalities

Journal Article Journal of Computer and System Sciences · January 1, 1985 A modal logic which can be used to formally reason about synchronous fixed connection multiprocess networks such as of VLSI is introduced. The logic has both temporal and spatial modal operators. The various temporal modal operators can be used to relate t ... Full text Cite

UNBOUNDED SPEED VARIABILITY IN DISTRIBUTED COMMUNICATIONS SYSTEMS.

Journal Article SIAM Journal on Computing · January 1, 1985 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. It ... Full text Cite

OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING.

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1985 A new parallel algorithm is given for integer sorting where the integer keys are restricted to at most polynomial magnitude. The algorithm costs only logarithmic time and is the first known where the product of the time and processor bounds are bounded by ... Full text Cite

PARALLEL TREE CONTRACTION AND ITS APPLICATION.

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1985 The authors give a bottom-up algorithm to handle trees in which all modifications to the tree are done locally. This bottom-up approach, which they call CONTRACT, has two major advantages over the top-down approach: (1) The control structure is straightfor ... Full text Cite

MOTION PLANNING IN THE PRESENCE OF MOVING OBSTACLES.

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1985 The authors investigate 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 ... Full text Cite

SIMPLE THREE-DIMENSIONAL REAL-TIME RELIABLE CELLULAR ARRAY.

Journal Article Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 1985 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 ... Cite

EFFICIENT PARALLEL SOLUTION OF LINEAR SYSTEMS.

Journal Article Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 1985 Full text Cite

The complexity of elementary algebra and geometry (preliminary version)

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · December 1, 1984 Full text Cite

PROBABILISTIC PARALLEL PREFIX COMPUTATION.

Journal Article Proceedings of the International Conference on Parallel Processing · December 1, 1984 Given inputs x//1 ,. . . ,x//n which are independent, identically distributed, random variables over a domain D, and an associative operation *, the probabilistic prefix computation problem is to compute the product x//1 *x//2 *. . . * x//n and its n-1 pre ... Cite

Real-Time Synchronization of Interprocess Communications

Journal Article ACM Transactions on Programming Languages and Systems (TOPLAS) · April 1, 1984 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 ... Full text Cite

Symmetric Complementation

Journal Article Journal of the ACM (JACM) · March 30, 1984 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 rec ... Full text Cite

Deriving efficient graph algorithms (summary)

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1984 Ten years ago Hopcroft and Tarjan discovered a class of very fast algorithms for solving graph problems such as biconnectivity and strong connectivity. While these depth-first-search algorithms are complex and can be difficult to understand, the problems t ... Full text Cite

PROBABILISTIC BIDDING GIVES OPTIMAL DISTRIBUTED RESOURCE-ALLOCATION

Journal Article LECTURE NOTES IN COMPUTER SCIENCE · 1984 Cite

The complexity of two-player games of incomplete information

Journal Article Journal of Computer and System Sciences · January 1, 1984 Two-player games of incomplete information have certain portions of positions which are private to each player and cannot be viewed by the opponent. Asymptotically optimal decision algorithms for space bounded games are provided. Various games of incomplet ... Full text Cite

ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE.

Journal Article SIAM Journal on Computing · January 1, 1984 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. The c ... Full text Cite

ASSIGNING PROCESSES TO PROCESSORS: A FAULT-TOLERANT APPROACH.

Journal Article Digest of Papers - FTCS (Fault-Tolerant Computing Symposium) · January 1, 1984 Cite

LOGARITHMIC TIME SORT FOR LINEAR SIZE NETWORKS.

Journal Article Conference Proceedings of the Annual ACM Symposium on Theory of Computing · December 1, 1983 Cite

MULTIPROCESS NETWORK LOGIC WITH TEMPORAL AND SPATIAL MODALITIES.

Journal Article Lecture Notes in Computer Science · December 1, 1983 Cite

Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time

Journal Article SIAM Journal on Computing · February 1983 Full text Cite

A multiprocess network logic with temporal and spatial modalities

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1983 We introduce a modal logic which can be used to formally reason about synchronous fixed connection multiprocess networks such as of VLSI. Our logic has both temporal and spatial modal operators. The various temporal modal operators allow us to relate prope ... Full text Cite

LOGARITHMIC DEPTH CIRCUITS FOR ALGEBRAIC FUNCTIONS.

Journal Article Annual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1983 Full text Cite

The propositional dynamic logic of deterministic, well-structured programs

Journal Article Theoretical Computer Science · January 1, 1983 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 ... Full text Cite

Real time resource allocation in distributed systems

Conference Proceedings of the Annual ACM Symposium on Principles of Distributed Computing · August 18, 1982 In this paper we consider a resource allocation problem which is local in the sense that the maxim~a 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 ... Full text Cite

Symmetric complementation

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · May 5, 1982 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 reversib ... Full text Cite

Symbolic Program Analysis in Almost-Linear Time

Journal Article SIAM Journal on Computing · February 1982 Full text Cite

Unbounded speed variability in distributed communication systems

Conference Conference Record of the Annual ACM Symposium on Principles of Programming Languages · January 25, 1982 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 communicat ... Full text Cite

On the power of probabilistic choice in synchronous parallel computations

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1982 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 ch ... Full text Cite

PARALLEL TIME O(log N) ACCEPTANCE OF DETERMINISTIC CFLs.

Journal Article Annual Symposium on Foundations of Computer Science - Proceedings · January 1, 1982 Full text Cite

PROPOSITIONAL DYNAMIC LOGIC OF DETERMINISTIC, WELL-STRUCTURED PROGRAM.

Journal Article Annual Symposium on Foundations of Computer Science - Proceedings · December 1, 1981 Cite

Distributed algorithms for synchronizing interprocess communication within real time

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · May 11, 1981 This paper considers a fixed (possibly infinite) set Π of distributed asynchronous processes which at various times are willing to communicate with each other. We describe probabilistic algorithms for synchronizing this communication with boolean "flag" va ... Full text Cite

Minimum s-t cut of a planar undirected network in o(n log2(n)) time

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1981 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 gener ... Full text Cite

Logics for probabilistic programming

Journal Article Proceedings of the Annual ACM Symposium on Theory of Computing · April 28, 1980 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 ... Full text Cite

Random matroids

Journal Article Proceedings of the Annual ACM Symposium on Theory of Computing · April 28, 1980 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. ... Full text Cite

A dynamic logic of multiprocessing with incomplete information

Journal Article Conference Record of the Annual ACM Symposium on Principles of Programming Languages · January 28, 1980 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 in ... Full text Cite

On determining the genus of a graph in 0(V0(g)) steps

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · April 30, 1979 Putting all the procedures together we can obtain our genus algorithm. Procedure. Embedding (G,g) (1) Generate Basic Subgraph (G,g), say Lj. (2) Remove Internal Edges (G,L,I). (3) Partition (G,L,I). (4) Quasiplanar (G,L,I). (5) 2-CNF (G,L,I). We can now an ... Full text Cite

Universal games of incomplete information

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · April 30, 1979 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. ... Full text Cite

Complexity of the mover's problem and generalizations

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 1979 This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles. ... Full text Cite

Multiple-person alternation

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 1979 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 alternatio ... Full text Cite

COMPLEXITY OF THE MOVER'S PROBLEM AND GENERALIZATIONS.

Journal Article Annual Symposium on Foundations of Computer Science - Proceedings · January 1, 1979 The problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles is considered. This work was motivated by problems in robotics. ... Cite

MULTIPLE-PERSON ALTERNATION.

Journal Article Annual Symposium on Foundations of Computer Science - Proceedings · January 1, 1979 The alternation machines of A. K. Chandra et al. , and the private alternation machines of J. H. Reif are generalized to model multiple person (team) games of incomplete information. The resulting classes of machines are ″multiple person alternation machin ... Cite

Data flow analysis of communicating processes - Extended abstract

Journal Article Conference Record of the Annual ACM Symposium on Principles of Programming Languages · January 1, 1979 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 technique ... Full text Cite

Symbolic program analysis in almost linear time

Conference Conference Record of the Annual ACM Symposium on Principles of Programming Languages · January 1, 1978 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 ... Full text Cite

Symbolic evaluation and the global value graph

Conference Conference Record of the Annual ACM Symposium on Principles of Programming Languages · January 1, 1977 This paper is concerned with difficult global flew problems which require the symbolic eva la ati on of programs. life use, as is common in global flew analysis, a model in which the expressions computed are specified, but the flow of control is indicated ... Full text Cite

Numerical solution of the Fokker-Planck equation via chebyschev polynomial approximations with reference to first passage time probability density functions

Journal Article Journal of Computational Physics · January 1, 1977 Chebyschev approximations are employed to solve the one-dimensional, time-dependent Fokker-Planck (forward Kolmogrov) equation in the presence of two barriers a finite "distance" apart. Solutions are presented for the fundamental intervals (-1, +1) and (0, ... Full text Cite