John H. Reif
According to our database^{1}, John H. Reif
Awards
ACM Fellow
ACM Fellow 1997, "For major and fundamental theoretical contributions to a wide range of emerging areas in computer science, particularly parallel computing and robotics.".
IEEE Fellow
IEEE Fellow 1993, "For contributions to theoretical computer, particularly parallel computing, using innovative techniques such as randomization.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at orcid.org
On csauthors.net:
Bibliography
2017
DNA Hairpin Gate: A Renewable DNA Seesaw Motif Using Hairpins.
CoRR, 2017
2016
Activatable tiles for compact robust programmable molecular assembly and other applications.
Natural Computing, 2016
Energy Complexity of Optical Computations.
IJUC, 2016
2015
The colearning in the design, simulation and optimization of a solar concentrating system.
Computers in Human Behavior, 2015
2014
DNA Computing.
Proceedings of the Computing Handbook, 2014
2013
Tile Complexity of Approximate Squares.
Algorithmica, 2013
2012
Engineering Natural Computation by Autonomous DNABased Biomolecular Devices.
Proceedings of the Handbook of Natural Computing, 2012
Tile Complexity of Linear Assemblies.
SIAM J. Comput., 2012
Local Parallel Biomolecular Computation.
IJUC, 2012
2011
Complexity of graph selfassembly in accretive systems and selfdestructible systems.
Theor. Comput. Sci., 2011
Design of a biomolecular device that executes process algebra.
Natural Computing, 2011
Asymptotically Optimal Kinodynamic Motion Planning for a Class of Modular SelfReconfigurable Robots.
Int. J. Comput. Geometry Appl., 2011
Keynote: DNAbased molecular devices.
Proceedings of the IEEE 1st International Conference on Computational Advances in Bio and Medical Sciences, 2011
Localized Hybridization Circuits.
Proceedings of the DNA Computing and Molecular Programming  17th International Conference, 2011
2010
Isothermal reactivating Whiplash PCR for locally programmable molecular computation.
Natural Computing, 2010
Capabilities and Limits of Compact Error Resilience Methods for Algorithmic SelfAssembly.
Algorithmica, 2010
Robomotion: Scalable, Physically Stable Locomotion for Selfreconfigurable Robots.
Proceedings of the Algorithmic Foundations of Robotics IX, 2010
HighFidelity DNA Hybridization Using Programmable Molecular DNA Devices.
Proceedings of the DNA Computing and Molecular Programming  16th International Conference, 2010
2009
Mechanical Computing: The Computational Complexity of Physical Devices.
Proceedings of the Encyclopedia of Complexity and Systems Science, 2009
Autonomous programmable DNA nanorobotic devices using DNAzymes.
Theor. Comput. Sci., 2009
The Tile Complexity of Linear Assemblies.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009
Design of a Biomolecular Device That Executes Process Algebra.
Proceedings of the DNA Computing and Molecular Programming, 15th International Conference, 2009
2008
Formula dissection: A parallel algorithm for constraint satisfaction.
Computers & Mathematics with Applications, 2008
A Framework for Designing Novel Magnetic Tiles Capable of Complex Selfassemblies.
Proceedings of the Unconventional Computing, 7th International Conference, 2008
Isothermal Reactivating Whiplash PCR for Locally Programmable Molecular Computation.
Proceedings of the DNA Computing, 14th International Meeting on DNA Computing, 2008
2007
On Robotic Optimal Path Planning in Polygonal Regions With PseudoEuclidean Metrics.
IEEE Trans. Systems, Man, and Cybernetics, Part B, 2007
Efficient and exact quantum compression.
Inf. Comput., 2007
Autonomous programmable biomolecular devices using selfassembled DNA nanostructures.
Commun. ACM, 2007
Autonomous Programmable Biomolecular Devices Using Selfassembled DNA Nanostructures.
Proceedings of the Logic, 2007
Optimal Kinodynamic Motion Planning for 2D Reconfiguration of SelfReconfigurable Robots.
Proceedings of the Robotics: Science and Systems III, 2007
SuperResolution Video Analysis for Forensic Investigations.
Proceedings of the Advances in Digital Forensics III, 2007
Autonomous Programmable Nanorobotic Devices Using DNAzymes.
Proceedings of the DNA Computing, 13th International Meeting on DNA Computing, 2007
Activatable Tiles: Compact, Robust Programmable Assembly and Other Applications.
Proceedings of the DNA Computing, 13th International Meeting on DNA Computing, 2007
2006
On boundaries of highly visible spaces and applications.
Theor. Comput. Sci., 2006
On finding approximate optimal paths in weighted regions.
J. Algorithms, 2006
Asymptotically Optimal Kinodynamic Motion Planning for Selfreconfigurable Robots.
Proceedings of the Algorithmic Foundation of Robotics VII, 2006
Compact ErrorResilient Computational DNA Tilings.
Proceedings of the Nanotechnology: Science and Computation, 2006
A Framework for Modeling DNA Based Molecular Systems.
Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006
Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Selfassembly in Two and Three Dimensions.
Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006
Design and Simulation of Selfrepairing DNA Lattices.
Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006
2005
On finding energyminimizing paths on terrains.
IEEE Trans. Robotics, 2005
Narrow passage sampling for probabilistic roadmap planning.
IEEE Trans. Robotics, 2005
Efficient parallel factorization and solution of structured and unstructured linear systems.
J. Comput. Syst. Sci., 2005
Design of Autonomous DNA Cellular Automata.
Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005
A Selfassembly Model of TimeDependent Glue Strength.
Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005
Complexity of Graph Selfassembly in Accretive Systems and Selfdestructible Systems.
Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005
2004
Movement Planning in the Presence of Flows.
Algorithmica, 2004
Design, Simulation, and Experimental Demonstration of Selfassembled DNA Nanostructures and Motors.
Proceedings of the Unconventional Programming Paradigms, 2004
Design of an Autonomous DNA Nanomechanical Device Capable of Universal Computation and Universal Translational Motion.
Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004
Designs of Autonomous Unidirectional Walking DNA Devices.
Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004
Compact ErrorResilient Computational DNA Tiling Assemblies.
Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004
DNAbased Cryptography.
Proceedings of the Aspects of Molecular Computing, 2004
2003
On Frictional Mechanical Systems and Their Computational Power.
SIAM J. Comput., 2003
The design of autonomous DNA nanomechanical devices: Walking and rolling DNA.
Natural Computing, 2003
Guest Editor's Foreword.
J. Comput. Syst. Sci., 2003
On energyminimizing paths on terrains for a mobile robot.
Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2003
The bridge test for sampling narrow passages with probabilistic roadmap planners.
Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2003
Adaptive and Compact Discretization for Weighted Region Optimal Path Finding.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003
On Boundaries of Highly Visible Spaces and Applications.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003
Deriving Effcient Graph Algorithms.
Proceedings of the Verification: Theory and Practice, 2003
2002
The Emerging Discipline of Biomolecular Computation in the US.
New Generation Comput., 2002
DNA lattices: A method for molecularscale patterning and computation.
Computing in Science and Engineering, 2002
Molecular Assembly and Computation: From Theory to Experimental Demonstrations.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002
The Design of Autonomous DNA Nanomechanical Devices: Walking and Rolling DNA.
Proceedings of the DNA Computing, 8th International Workshop on DNA Based Computers, 2002
DNA Nanotubes: Construction and Characterization of Filaments Composed of TXtile Lattice.
Proceedings of the DNA Computing, 8th International Workshop on DNA Based Computers, 2002
2001
Parallel OutputSensitive Algorithms for Combinatorial and Linear Algebra Problems.
J. Comput. Syst. Sci., 2001
Optimal encoding of nonstationary sources.
Inf. Sci., 2001
Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix.
Algorithmica, 2001
Movement Planning in the Presence of Flows.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001
BUSHWHACK: An Approximation Algorithm for Minimal Paths through PseudoEuclidean Spaces.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001
Programmable Assembly at the Molecular Scale: SelfAssembly of DNA Lattices (Invited Paper).
Proceedings of the 2001 IEEE International Conference on Robotics and Automation, 2001
Experimental Construction of Very Large Scale DNA Databases with Associative Search Capability.
Proceedings of the DNA Computing, 7th International Workshop on DNABased Computers, 2001
2000
Nonuniform Discretization for Kinodynamic Motion Planning and its Applications.
SIAM J. Comput., 2000
On the Impossibility of InteractionFree Quantum Sensing for Small I/O Bandwidth.
Inf. Comput., 2000
Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input.
Algorithmica, 2000
Challenges and Applications for SelfAssembled DNA Nanostructures.
Proceedings of the DNA Computing, 6th International Workshop on DNABased Computers, 2000
Computationally Inspired Biotechnologies: Improved DNA Synthesis and Associative Search Using ErrorCorrecting Codes and VectorQuantization.
Proceedings of the DNA Computing, 6th International Workshop on DNABased Computers, 2000
1999
Synthesizing Efficient OutofCore Programs for Block Recursive Algorithms Using BlockCyclic Data Distributions.
IEEE Trans. Parallel Distrib. Syst., 1999
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point.
SIAM J. Comput., 1999
Social potential fields: A distributed behavioral control for autonomous robots.
Robotics and Autonomous Systems, 1999
Parallel Biomolecular Computation: Models and Simulations.
Algorithmica, 1999
Experimental progress in computation by selfassembly of DNA tilings.
Proceedings of the DNA Based Computers, 1999
DNAbased cryptography.
Proceedings of the DNA Based Computers, 1999
1998
A Randomized Parallel Algorithm for Planar Graph Isomorphism.
J. Algorithms, 1998
Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1998
Optimal Lossless Compression of a Class of Dynamic Sources.
Proceedings of the Data Compression Conference, 1998
1997
ErrorResilient Optimal Data Compression.
SIAM J. Comput., 1997
Autonomous search by robots and animals: A survey.
Robotics and Autonomous Systems, 1997
On Dynamic Algorithms for Algebraic Problems.
J. Algorithms, 1997
Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs.
Algorithmica, 1997
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point.
Proceedings of the TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Local parallel biomolecular computation.
Proceedings of the DNA Based Computers, 1997
LowCost Prevention of Error Propagation for Data Compression with Dynamic Dictionaries.
Proceedings of the 7th Data Compression Conference (DCC '97), 1997
Fast and Compact Volume Rendering in the Compressed Transform Domain.
Proceedings of the 7th Data Compression Conference (DCC '97), 1997
1996
Models and Resource Metrics for Parallel and Distributed Computation.
Parallel Algorithms Appl., 1996
An Efficient Algorithm for the Complex Roots Problem.
J. Complexity, 1996
Searching in an Unknown Environment: An Optimal Randomized Algorithm for the CowPath Problem.
Inf. Comput., 1996
Synthesizing Efficient OutofCore Programs for Block Recursive Algorithms Using BlockCyclic Data Distributions.
Proceedings of the 1996 International Conference on Parallel Processing, 1996
A Refinement Methodology for Developing DataParallel Applications.
Proceedings of the EuroPar '96 Parallel Processing, 1996
Efficient Lossless Compression of Trees and Graphs.
Proceedings of the 6th Data Compression Conference (DCC '96), Snowbird, Utah, March 31, 1996
1995
The Light Bulb Problem
Inf. Comput., March, 1995
Design and applications of a highresolution insert headmounteddisplay.
Proceedings of the 1995 Virtual Reality Annual International Symposium, 1995
Work efficient parallel solution of Toeplitz systems and polynomial GCD.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
Parallel Molecular Computation.
SPAA, 1995
Generating Efficient Programs for TwoLevel Memories from Tensorproducts.
Proceedings of the Seventh IASTED/ISMM International Conference on Parallel and Distributed Computing and Systems, 1995
Stochastic Graphs Have Short Memory: Fully Dynamic Connectivity in PolyLog Expected Time.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995
Models and resource metrics for parallel and distributed computation.
Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS28), 1995
Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995
Fast Pattern Matching for Entropy Bounded Text.
Proceedings of the IEEE Data Compression Conference, 1995
1994
Randomized Algorithms for Binary Search and Load Balancing on Fixed Connection Networks with Geometric Applications.
SIAM J. Comput., 1994
Erratum: Optimal Parallel Randomized Algorithms for ThreeDimensional Convex Hulls and Related Problems.
SIAM J. Comput., 1994
Planarity Testing in Parallel.
J. Comput. Syst. Sci., 1994
Shortest Paths in the Plane with Polygonal Obstacles.
J. ACM, 1994
A SingleExponential Upper Bound for Finding Shortest Paths in Three Dimensions.
J. ACM, 1994
Motion Planning in the Presence of Moving Obstacles.
J. ACM, 1994
Computability and Complexity of Ray Tracing.
Discrete & Computational Geometry, 1994
Directed st Numberings, Rubber Bands, and Testing Digraph kVertex Connectivity.
Combinatorica, 1994
Dynamic Parallel Tree Contraction (Extended Abstract).
SPAA, 1994
O(log² n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices.
SPAA, 1994
Dynamic Algebraic Algorithms.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 January 1994, 1994
Models and Resource Metrics for Parallel and Distributed Computation.
Proceedings of the 8th International Symposium on Parallel Processing, 1994
An O(n^1+epsilon log b) Algorithm for the Complex Roots Problem
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
Specification and Development of Parallel Algorithms with the ProteusSystem.
Proceedings of the Specification of Parallel Algorithms, 1994
Data Compression Techniques for Stock Market Prediction.
Proceedings of the IEEE Data Compression Conference, 1994
1993
Fast and Efficient Parallel Solution of Sparse Linear Systems.
SIAM J. Comput., 1993
Kinodynamic Motion Planning.
J. ACM, 1993
Continuous Alternation: The Complexity of Pursuit in Continuous Domains.
Algorithmica, 1993
A Dynamic Separator Algorithm.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993
Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems.
SPAA, 1993
Searching in an Unknown Environment: An Optimal Randomized Algorithm for the CowPath Problem.
Proceedings of the Fourth Annual ACM/SIGACTSIAM Symposium on Discrete Algorithms, 1993
The Complexity of Nbody Simulation.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993
An O(n log ^3 n) Algorithm for the Real Root Problem
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993
Using Difficulty of Prediction to Decrease Computation: Fast Sort, Priority Queue and Convex Hull on Entropy Bounded Inputs
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993
Multispectral Image Compression Algorithms.
Proceedings of the IEEE Data Compression Conference, 1993
1992
Nested Annealing: A Provable Improvement to Simulated Annealing.
Theor. Comput. Sci., 1992
Compact Multigrid.
SIAM J. Scientific Computing, 1992
On Threshold Circuits and Polynomial Computation.
SIAM J. Comput., 1992
Optimal Parallel Randomized Algorithms for ThreeDimensional Convex Hulls and Related Problems.
SIAM J. Comput., 1992
Quad Tree Structures for Image Compression Applications.
Inf. Process. Manage., 1992
Expected Parallel Time and Sequential Space Complexity of Graph and Digraph Problems.
Algorithmica, 1992
Optimal Randomized Parallel Algorithms for Computational Geometry.
Algorithmica, 1992
Implementations of Randomized Sorting on Large Parallel Machines.
SPAA, 1992
Efficient Parallel Algorithms for Computing all Pair Shortest Paths in Directed Graphs.
SPAA, 1992
Space and Time Efficient Implementations of Parallel Nested Dissection.
SPAA, 1992
Directed st Bumberings, Rubber Bands, and Testing Digraph kVertex Connectivity.
Proceedings of the Third Annual ACM/SIGACTSIAM Symposium on Discrete Algorithms, 1992
Prototyping NBody Simulation in Proteus.
Proceedings of the 6th International Parallel Processing Symposium, 1992
The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
Optical Techniques for Image Compression.
Proceedings of the IEEE Data Compression Conference, 1992
1991
Parallel Tree Contraction, Part 2: Further Applications.
SIAM J. Comput., 1991
A Parallel Architecture for HighSpeed Data Compression.
J. Parallel Distrib. Comput., 1991
The Parallel Computation of Minimum Cost Paths in Graphs by Stream Contraction.
Inf. Process. Lett., 1991
An Exact Algorithm for Kinodynamic Planning in the Plane.
Discrete & Computational Geometry, 1991
An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
Prototyping parallel and distributed programs in Proteus.
Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, 1991
How Do We Make Parallel Processing a Reality? Bridging the Gap Between Theory and Practice.
Proceedings of the Fifth International Parallel Processing Symposium, Proceedings, Anaheim, California, USA, April 30, 1991
Image Compression Methods with Distortion Controlled Capabilities.
Proceedings of the IEEE Data Compression Conference, 1991
1990
Optimal Size Integer Division Circuits.
SIAM J. Comput., 1990
BLITZEN: A Highly Integrated Massively Parallel Machine.
J. Parallel Distrib. Comput., 1990
Data flow analysis of distributed communicating processes.
International Journal of Parallel Programming, 1990
Energy complexity of optical computations.
Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, 1990
Randomized Algorithms for Binary Search and Load Balancing with Geometric Applications.
SPAA, 1990
A Randomized Parallel Algorithm for Planar Graph Isomorphism.
SPAA, 1990
On the BitComplexity of Discrete Solutions of PDEs: Compact Multigrid.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990
Efficient Parallel Algorithms for Optical Computing with the DFT Primitive.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1990
The Computability and Complexity of Optical Beam Tracing
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
An Exact Algorithm for Kinodynamic Planning in the Plane.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990
1989
Parallel Processing Can Be Harmful: The Unusual Behavior of Interpolation Search
Inf. Comput., June, 1989
Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms.
SIAM J. Comput., 1989
Fast and Efficient Solution of Path Algebra Problems.
J. Comput. Syst. Sci., 1989
Parallel Tree Contraction Part 1: Fundamentals.
Advances in Computing Research, 1989
Optimal Size Integer Division Circuits
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Polling: A New Randomized Sampling Technique for Computational Geometry
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Randomization in Parallel Algorithms and its Impact on Computational Geometry.
Proceedings of the Optimal Algorithms, International Symposium, Varna, Bulgaria, May 29, 1989
Randomized Parallel Algorithms.
IFIP Congress, 1989
An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
The Light Bulb Problem.
Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989
1988
Efficient Parallel Pseudorandom Number Generation.
SIAM J. Comput., 1988
Parallel Time O(log n) Acceptance of Deterministic CFLs on an ExclusiveWrite PRAM.
SIAM J. Comput., 1988
An Efficient Parallel Algorithm for Planarity.
J. Comput. Syst. Sci., 1988
A Simple ThreeDimensional RealTime Reliable Cellular Array.
J. Comput. Syst. Sci., 1988
The Complexity of Reachability in Distributed Communicating Processes.
Acta Inf., 1988
3Dimensional Shortest Paths in the Presence of Polyhedral Obstacles.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988
Nested Annealing: A Provable Improvement to Simulated Annealing.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988
On the Complexity of Kinodynamic Planning
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988
An Efficient OutputSensitive Hidden Surface Removal Algorithm and Its Parallelization.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988
1987
Minimizing turns for discrete movement in the interior of a polygon.
IEEE J. Robotics and Automation, 1987
A logarithmic time sort for linear size networks.
J. ACM, 1987
A Topological Approach to Dynamic Graph Connectivity.
Inf. Process. Lett., 1987
Optimal Randomized Parallel Algorithms for Computational Geometry.
Proceedings of the International Conference on Parallel Processing, 1987
Some Polynomial and Toeplitz Matrix Computations
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987
New Lower Bound Techniques for Robot Motion Planning Problems
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987
Ranomized Parallel Computation.
Proceedings of the Fundamentals of Computation Theory, 1987
On threshold circuits and polynomial computation.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987
1986
Logarithmic Depth Circuits for Algebraic Functions.
SIAM J. Comput., 1986
Efficient Symbolic Analysis of Programs.
J. Comput. Syst. Sci., 1986
The Complexity of Elementary Algebra and Geometry.
J. Comput. Syst. Sci., 1986
Arithmetic Theories for Computational Complexity Problems
Information and Control, 1986
The Logic of Distributed Protocols.
Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986
Extension of the Parallel Nested Dissection Algorithm to Path Algebra Problems.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986
An Efficient Parallel Algorithm for Planarity
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
Fast and Efficient Parallel Linear Programming and Linear Least Squares Computations.
Proceedings of the VLSI Algorithms and Architectures, 1986
1985
Unbounded Speed Variability in Distributed Communications Systems.
SIAM J. Comput., 1985
A Multiprocess Network Logic with Temporal and Spatial Modalities.
J. Comput. Syst. Sci., 1985
DepthFirst Search is Inherently Sequential.
Inf. Process. Lett., 1985
kconnectivity in random undirected graphs.
Discrete Mathematics, 1985
Efficient Parallel Solution of Linear Systems
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
A Simple ThreeDimensional RealTime Reliable Cellular Array
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
Motion Planning in the Presence of Moving Obstacles
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
An Optimal Parallel Algorithm for Integer Sorting
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
Parallel Tree Contraction and Its Application
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
Probabilistic algorithms in group theory.
Proceedings of the Fundamentals of Computation Theory, 1985
Efficient Parallel PseudoRandom Number Generation.
Proceedings of the Advances in Cryptology, 1985
1984
RealTime Synchronization of Interprocess Communications.
ACM Trans. Program. Lang. Syst., 1984
On Synchronous Parallel Computations with Independent Probabilistic Choice.
SIAM J. Comput., 1984
The Complexity of TwoPlayer Games of Incomplete Information.
J. Comput. Syst. Sci., 1984
Symmetric Complementation.
J. ACM, 1984
The Complexity of Elementary Algebra and Geometry (Preliminary Abstract)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984
Probabilistic Bidding Gives Optimal Distributed Resource Allocation.
Proceedings of the Automata, 1984
1983
The Propositional Dynamic Logic of Deterministic, WellStructured Programs.
Theor. Comput. Sci., 1983
Minimum st Cut of a Planar Undirected Network in O(n log^{2}(n)) Time.
SIAM J. Comput., 1983
A Logarithmic Time Sort for Linear Size Networks
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983
Deriving Efficient Graph Algorithms (Summary).
Proceedings of the Logics of Programs, 1983
A Multiprocess Network Logic with Temporal and Spatial Modalities.
Proceedings of the Automata, 1983
Logarithmic Depth Circuits for Algebraic Functions
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
1982
Symbolic Program Analysis in AlmostLinear Time.
SIAM J. Comput., 1982
Symmetric Complementation
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982
Unbounded Speed Variability in Distributed Communication Systems.
Proceedings of the Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, 1982
Real Time Resource Allocation in Distributed Systems.
Proceedings of the ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing, 1982
On the Power of Probabilistic Choice in Synchronous Parallel Computations.
Proceedings of the Automata, 1982
Parallel Time O(log N) Acceptance of Deterministic CFLs
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982
1981
Distributed Algorithms for Synchronizing Interprocess Communication within Real Time
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981
Minimum ST Cut of a Planar Undirected Network in O(n log²(n)) Time.
Proceedings of the Automata, 1981
The Propositional Dynamic Logic of Deterministic, WellStructured Programs (Extended Abstract)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981
1980
Code Motion.
SIAM J. Comput., 1980
Random Matroids
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980
Logics for Probabilistic Programming (Extended Abstract)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980
A Dynamic Logic of Multiprocessing with Incomplete Information.
Proceedings of the Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980
1979
Universal Games of Incomplete Information
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979
On Determining the Genus of a Graph in O(v^O(g)) Steps
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979
Data Flow Analysis of Communicating Processes.
Proceedings of the Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, 1979
Complexity of the Mover's Problem and Generalizations (Extended Abstract)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979
MultiplePerson Alternation
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979
1978
Symbolic Programming Analysis in Almost Linear Time.
Proceedings of the Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages, 1978
1977
Symbolic Evaluation and the Global Value Graph.
Proceedings of the Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, 1977