John H. Reif

According to our database1, John H. Reif
  • authored at least 244 papers between 1977 and 2017.
  • has a "Dijkstra number"2 of three.

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 
Other 

Links

Homepages:

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 co-learning 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 DNA-Based 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 self-assembly in accretive systems and self-destructible 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 Self-Reconfigurable Robots.
Int. J. Comput. Geometry Appl., 2011

Keynote: DNA-based 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 Self-Assembly.
Algorithmica, 2010

Robomotion: Scalable, Physically Stable Locomotion for Self-reconfigurable Robots.
Proceedings of the Algorithmic Foundations of Robotics IX, 2010

High-Fidelity 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 Self-assemblies.
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 Pseudo-Euclidean Metrics.
IEEE Trans. Systems, Man, and Cybernetics, Part B, 2007

Efficient and exact quantum compression.
Inf. Comput., 2007

Autonomous programmable biomolecular devices using self-assembled DNA nanostructures.
Commun. ACM, 2007

Autonomous Programmable Biomolecular Devices Using Self-assembled DNA Nanostructures.
Proceedings of the Logic, 2007

Optimal Kinodynamic Motion Planning for 2D Reconfiguration of Self-Reconfigurable Robots.
Proceedings of the Robotics: Science and Systems III, 2007

Super-Resolution 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 Self-reconfigurable Robots.
Proceedings of the Algorithmic Foundation of Robotics VII, 2006

Compact Error-Resilient 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 Self-assembly in Two and Three Dimensions.
Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006

Design and Simulation of Self-repairing DNA Lattices.
Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006

2005
On finding energy-minimizing 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 Self-assembly Model of Time-Dependent Glue Strength.
Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005

Complexity of Graph Self-assembly in Accretive Systems and Self-destructible 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 Self-assembled 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 Error-Resilient Computational DNA Tiling Assemblies.
Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004

DNA-based 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 nano-mechanical devices: Walking and rolling DNA.
Natural Computing, 2003

Guest Editor's Foreword.
J. Comput. Syst. Sci., 2003

On energy-minimizing 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 molecular-scale 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 TX-tile Lattice.
Proceedings of the DNA Computing, 8th International Workshop on DNA Based Computers, 2002

2001
Parallel Output-Sensitive Algorithms for Combinatorial and Linear Algebra Problems.
J. Comput. Syst. Sci., 2001

Optimal encoding of non-stationary 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 Pseudo-Euclidean Spaces.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

Programmable Assembly at the Molecular Scale: Self-Assembly 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 DNA-Based Computers, 2001

2000
Nonuniform Discretization for Kinodynamic Motion Planning and its Applications.
SIAM J. Comput., 2000

On the Impossibility of Interaction-Free 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 Self-Assembled DNA Nanostructures.
Proceedings of the DNA Computing, 6th International Workshop on DNA-Based Computers, 2000

Computationally Inspired Biotechnologies: Improved DNA Synthesis and Associative Search Using Error-Correcting Codes and Vector-Quantization.
Proceedings of the DNA Computing, 6th International Workshop on DNA-Based Computers, 2000

1999
Synthesizing Efficient Out-of-Core Programs for Block Recursive Algorithms Using Block-Cyclic 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 self-assembly of DNA tilings.
Proceedings of the DNA Based Computers, 1999

DNA-based 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
Error-Resilient 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 Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Local parallel biomolecular computation.
Proceedings of the DNA Based Computers, 1997

Low-Cost 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 Cow-Path Problem.
Inf. Comput., 1996

Synthesizing Efficient Out-of-Core Programs for Block Recursive Algorithms Using Block-Cyclic Data Distributions.
Proceedings of the 1996 International Conference on Parallel Processing, 1996

A Refinement Methodology for Developing Data-Parallel Applications.
Proceedings of the Euro-Par '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 high-resolution insert head-mounted-display.
Proceedings of the 1995 Virtual Reality Annual International Symposium, 1995

Work efficient parallel solution of Toeplitz systems and polynomial GCD.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Parallel Molecular Computation.
SPAA, 1995

Generating Efficient Programs for Two-Level Memories from Tensor-products.
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 Poly-Log 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 (HICSS-28), 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 Three-Dimensional 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 Single-Exponential 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 s-t Numberings, Rubber Bands, and Testing Digraph k-Vertex 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 ACM-SIAM Symposium on Discrete Algorithms. 23-25 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 Cow-Path Problem.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

The Complexity of N-body 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 Three-Dimensional 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 s-t Bumberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Prototyping N-Body 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 High-Speed 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 Bit-Complexity 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 Exclusive-Write P-RAM.
SIAM J. Comput., 1988

An Efficient Parallel Algorithm for Planarity.
J. Comput. Syst. Sci., 1988

A Simple Three-Dimensional Real-Time Reliable Cellular Array.
J. Comput. Syst. Sci., 1988

The Complexity of Reachability in Distributed Communicating Processes.
Acta Inf., 1988

3-Dimensional 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 Output-Sensitive 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

Depth-First Search is Inherently Sequential.
Inf. Process. Lett., 1985

k-connectivity 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 Three-Dimensional Real-Time 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 Pseudo-Random Number Generation.
Proceedings of the Advances in Cryptology, 1985

1984
Real-Time 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 Two-Player 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, Well-Structured Programs.
Theor. Comput. Sci., 1983

Minimum s-t Cut of a Planar Undirected Network in O(n log2(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 Almost-Linear 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 SIGACT-SIGOPS 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 S-T Cut of a Planar Undirected Network in O(n log²(n)) Time.
Proceedings of the Automata, 1981

The Propositional Dynamic Logic of Deterministic, Well-Structured 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

Multiple-Person 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


  Loading...