John H. Reif

According to our database, John H. Reif authored at least 225 papers between 1977 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

NeuralCRNs: A Natural Implementation of Learning in Chemical Reaction Networks.

Rajiv Teja Nagipogu, John H. Reif

CoRR, 2024

2021

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

Xin Song, Shalin Shah, John H. Reif

Theor. Comput. Sci., 2021

2020

ExTemp: A computational and image-processing suite for extracting temporal barcodes.

Shalin Shah, Abhishek Kumar Dubey, John H. Reif

Dataset, February, 2020

ExTemp: A computational and image-processing suite for extracting temporal barcodes.

Shalin Shah, Abhishek Kumar Dubey, John H. Reif

J. Open Source Softw., 2020

2019

Implementing Arbitrary CRNs Using Strand Displacing Polymerase.

Shalin Shah, Tianqi Song, Xin Song, Ming Yang, John H. Reif

Proceedings of the DNA Computing and Molecular Programming - 25th International Conference, 2019

Localized DNA Computation.

Hieu Bui, John H. Reif

Proceedings of the From Parallel to Emergent Computing, 1st Edition, 2019

2018

Temporal DNA Barcodes: A Time-Based Approach for Single-Molecule Imaging.

Shalin Shah, John H. Reif

Proceedings of the DNA Computing and Molecular Programming - 24th International Conference, 2018

2017

DNA Hairpin Gate: A Renewable DNA Seesaw Motif Using Hairpins.

Abeer Eshra, Shalin Shah, John H. Reif

CoRR, 2017

2016

Activatable tiles for compact robust programmable molecular assembly and other applications.

Urmi Majumder, Sudhanshu Garg, Thomas H. LaBean, John H. Reif

Nat. Comput., 2016

Energy Complexity of Optical Computations.

Akhilesh Tyagi, John H. Reif

Int. J. Unconv. Comput., 2016

2015

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

Wadee Alhalabi, John H. Reif, Zeineb Elsheikh, Heba Felimban, Majda Fallata, Khalid Thabit, Abdullah Abusorrah

Comput. Hum. Behav., 2015

2014

DNA Computing.

Hieu Bui, Harish Chandran, Sudhanshu Garg, Nikhil Gopalkrishnan, Reem Mokhtar, John H. Reif, Tianqi Song

Proceedings of the Computing Handbook, 2014

2013

Tile Complexity of Approximate Squares.

Harish Chandran, Nikhil Gopalkrishnan, John H. Reif

Algorithmica, 2013

2012

Engineering Natural Computation by Autonomous DNA-Based Biomolecular Devices.

John H. Reif, Thomas H. LaBean

Proceedings of the Handbook of Natural Computing, 2012

Tile Complexity of Linear Assemblies.

Harish Chandran, Nikhil Gopalkrishnan, John H. Reif

SIAM J. Comput., 2012

Local Parallel Biomolecular Computation.

John H. Reif

Int. J. Unconv. Comput., 2012

2011

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

John H. Reif, Sudheer Sahu, Peng Yin

Theor. Comput. Sci., 2011

Design of a biomolecular device that executes process algebra.

Urmi Majumder, John H. Reif

Nat. Comput., 2011

Asymptotically Optimal Kinodynamic Motion Planning for a Class of Modular Self-Reconfigurable Robots.

John H. Reif, Sam Slee

Int. J. Comput. Geom. Appl., 2011

Keynote: DNA-based molecular devices.

John H. Reif

Proceedings of the IEEE 1st International Conference on Computational Advances in Bio and Medical Sciences, 2011

Localized Hybridization Circuits.

Harish Chandran, Nikhil Gopalkrishnan, Andrew Phillips, John H. Reif

Proceedings of the DNA Computing and Molecular Programming - 17th International Conference, 2011

2010

Isothermal reactivating Whiplash PCR for locally programmable molecular computation.

John H. Reif, Urmi Majumder

Nat. Comput., 2010

Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Self-Assembly.

Sudheer Sahu, John H. Reif

Algorithmica, 2010

Robomotion: Scalable, Physically Stable Locomotion for Self-reconfigurable Robots.

Sam Slee, John H. Reif

Proceedings of the Algorithmic Foundations of Robotics IX, 2010

High-Fidelity DNA Hybridization Using Programmable Molecular DNA Devices.

Nikhil Gopalkrishnan, Harish Chandran, John H. Reif

Proceedings of the DNA Computing and Molecular Programming - 16th International Conference, 2010

2009

Mechanical Computing: The Computational Complexity of Physical Devices.

John H. Reif

Proceedings of the Encyclopedia of Complexity and Systems Science, 2009

Autonomous programmable DNA nanorobotic devices using DNAzymes.

John H. Reif, Sudheer Sahu

Theor. Comput. Sci., 2009

2008

Formula dissection: A parallel algorithm for constraint satisfaction.

John H. Reif, Simon Kasif, Deepak Sherlekar

Comput. Math. Appl., 2008

A Framework for Designing Novel Magnetic Tiles Capable of Complex Self-assemblies.

Urmi Majumder, John H. Reif

Proceedings of the Unconventional Computing, 7th International Conference, 2008

2007

On Robotic Optimal Path Planning in Polygonal Regions With Pseudo-Euclidean Metrics.

Zheng Sun, John H. Reif

IEEE Trans. Syst. Man Cybern. Part B, 2007

Efficient and exact quantum compression.

John H. Reif, Sukhendu Chakraborty

Inf. Comput., 2007

Autonomous programmable biomolecular devices using self-assembled DNA nanostructures.

John H. Reif, Thomas H. LaBean

Commun. ACM, 2007

Optimal Kinodynamic Motion Planning for 2D Reconfiguration of Self-Reconfigurable Robots.

John H. Reif, Sam Slee

Proceedings of the Robotics: Science and Systems III, 2007

Super-Resolution Video Analysis for Forensic Investigations.

Ashish Gehani, John H. Reif

Proceedings of the Advances in Digital Forensics III, 2007

Autonomous Programmable Nanorobotic Devices Using DNAzymes.

John H. Reif, Sudheer Sahu

Proceedings of the DNA Computing, 13th International Meeting on DNA Computing, 2007

Activatable Tiles: Compact, Robust Programmable Assembly and Other Applications.

Urmi Majumder, Thomas H. LaBean, John H. Reif

Proceedings of the DNA Computing, 13th International Meeting on DNA Computing, 2007

2006

On boundaries of highly visible spaces and applications.

John H. Reif, Zheng Sun

Theor. Comput. Sci., 2006

On finding approximate optimal paths in weighted regions.

Zheng Sun, John H. Reif

J. Algorithms, 2006

Asymptotically Optimal Kinodynamic Motion Planning for Self-reconfigurable Robots.

John H. Reif, Sam Slee

Proceedings of the Algorithmic Foundation of Robotics VII, 2006

Compact Error-Resilient Computational DNA Tilings.

John H. Reif, Sudheer Sahu, Peng Yin

Proceedings of the Nanotechnology: Science and Computation, 2006

A Framework for Modeling DNA Based Molecular Systems.

Sudheer Sahu, Bei Wang, John H. Reif

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.

Sudheer Sahu, John H. Reif

Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006

Design and Simulation of Self-repairing DNA Lattices.

Urmi Majumder, Sudheer Sahu, Thomas H. LaBean, John H. Reif

Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006

2005

On finding energy-minimizing paths on terrains.

Zheng Sun, John H. Reif

IEEE Trans. Robotics, 2005

Narrow passage sampling for probabilistic roadmap planning.

Zheng Sun, David Hsu, Tingting Jiang, Hanna Kurniawati, John H. Reif

IEEE Trans. Robotics, 2005

Efficient parallel factorization and solution of structured and unstructured linear systems.

John H. Reif

J. Comput. Syst. Sci., 2005

Design of Autonomous DNA Cellular Automata.

Peng Yin, Sudheer Sahu, Andrew J. Turberfield, John H. Reif

Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005

A Self-assembly Model of Time-Dependent Glue Strength.

Sudheer Sahu, Peng Yin, John H. Reif

Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005

2004

Movement Planning in the Presence of Flows.

John H. Reif, Zheng Sun

Algorithmica, 2004

Design, Simulation, and Experimental Demonstration of Self-assembled DNA Nanostructures and Motors.

John H. Reif, Thomas H. LaBean, Sudheer Sahu, Hao Yan, Peng Yin

Proceedings of the Unconventional Programming Paradigms, 2004

Design of an Autonomous DNA Nanomechanical Device Capable of Universal Computation and Universal Translational Motion.

Peng Yin, Andrew J. Turberfield, Sudheer Sahu, John H. Reif

Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004

Designs of Autonomous Unidirectional Walking DNA Devices.

Peng Yin, Andrew J. Turberfield, John H. Reif

Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004

Compact Error-Resilient Computational DNA Tiling Assemblies.

John H. Reif, Sudheer Sahu, Peng Yin

Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004

DNA-based Cryptography.

Ashish Gehani, Thomas H. LaBean, John H. Reif

Proceedings of the Aspects of Molecular Computing, 2004

2003

On Frictional Mechanical Systems and Their Computational Power.

John H. Reif, Zheng Sun

SIAM J. Comput., 2003

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

John H. Reif

Nat. Comput., 2003

Guest Editor's Foreword.

John H. Reif

J. Comput. Syst. Sci., 2003

On energy-minimizing paths on terrains for a mobile robot.

Zheng Sun, John H. Reif

Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2003

The bridge test for sampling narrow passages with probabilistic roadmap planners.

David Hsu, Tingting Jiang, John H. Reif, Zheng Sun

Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2003

Adaptive and Compact Discretization for Weighted Region Optimal Path Finding.

Zheng Sun, John H. Reif

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

Deriving Effcient Graph Algorithms.

John H. Reif, William L. Scherlis

Proceedings of the Verification: Theory and Practice, 2003

2002

The Emerging Discipline of Biomolecular Computation in the US.

John H. Reif

New Gener. Comput., 2002

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

John H. Reif

Comput. Sci. Eng., 2002

Molecular Assembly and Computation: From Theory to Experimental Demonstrations.

John H. Reif

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

The Design of Autonomous DNA Nanomechanical Devices: Walking and Rolling DNA.

John H. Reif

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.

Dage Liu, John H. Reif, Thomas H. LaBean

Proceedings of the DNA Computing, 8th International Workshop on DNA Based Computers, 2002

2001

Parallel Output-Sensitive Algorithms for Combinatorial and Linear Algebra Problems.

John H. Reif

J. Comput. Syst. Sci., 2001

Optimal encoding of non-stationary sources.

John H. Reif, James A. Storer

Inf. Sci., 2001

Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix.

John H. Reif

Algorithmica, 2001

BUSHWHACK: An Approximation Algorithm for Minimal Paths through Pseudo-Euclidean Spaces.

Zheng Sun, John H. Reif

Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

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

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

Proceedings of the 2001 IEEE International Conference on Robotics and Automation, 2001

Experimental Construction of Very Large Scale DNA Databases with Associative Search Capability.

John H. Reif, Thomas H. LaBean, Michael Pirrung, Vipul S. Rana, Bo Guo, Carl Kingsford, Gene S. Wickham

Proceedings of the DNA Computing, 7th International Workshop on DNA-Based Computers, 2001

2000

Nonuniform Discretization for Kinodynamic Motion Planning and its Applications.

John H. Reif, Hongyan Wang

SIAM J. Comput., 2000

On the Impossibility of Interaction-Free Quantum Sensing for Small I/O Bandwidth.

John H. Reif

Inf. Comput., 2000

Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input.

John H. Reif

Algorithmica, 2000

Challenges and Applications for Self-Assembled DNA Nanostructures.

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

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.

John H. Reif, Thomas H. LaBean

Proceedings of the DNA Computing, 6th International Workshop on DNA-Based Computers, 2000

Parallel Computational Geometry: An Approach using Randomization.

John H. Reif, Sandeep Sen

Proceedings of the Handbook of Computational Geometry, 2000

1999

Synthesizing Efficient Out-of-Core Programs for Block Recursive Algorithms Using Block-Cyclic Data Distributions.

Zhiyong Li, John H. Reif, Sandeep K. S. Gupta

IEEE Trans. Parallel Distributed Syst., 1999

Approximate Complex Polynomial Evaluation in Near Constant Work Per Point.

John H. Reif

SIAM J. Comput., 1999

Social potential fields: A distributed behavioral control for autonomous robots.

John H. Reif, Hongyan Wang

Robotics Auton. Syst., 1999

Parallel Biomolecular Computation: Models and Simulations.

John H. Reif

Algorithmica, 1999

Experimental progress in computation by self-assembly of DNA tilings.

Thomas H. LaBean, Erik Winfree, John H. Reif

Proceedings of the DNA Based Computers, 1999

1998

A Randomized Parallel Algorithm for Planar Graph Isomorphism.

Hillel Gazit, John H. Reif

J. Algorithms, 1998

Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation.

John H. Reif

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1998

Optimal Lossless Compression of a Class of Dynamic Sources.

John H. Reif, James A. Storer

Proceedings of the Data Compression Conference, 1998

1997

Error-Resilient Optimal Data Compression.

James A. Storer, John H. Reif

SIAM J. Comput., 1997

Autonomous search by robots and animals: A survey.

Erol Gelenbe, Nestor A. Schmajuk, John Staddon, John H. Reif

Robotics Auton. Syst., 1997

On Dynamic Algorithms for Algebraic Problems.

John H. Reif, Stephen R. Tate

J. Algorithms, 1997

Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs.

Yijie Han, Victor Y. Pan, John H. Reif

Algorithmica, 1997

Low-Cost Prevention of Error Propagation for Data Compression with Dynamic Dictionaries.

James A. Storer, John H. Reif

Proceedings of the 7th Data Compression Conference (DCC '97), 1997

Fast and Compact Volume Rendering in the Compressed Transform Domain.

Sefeng Chen, John H. Reif

Proceedings of the 7th Data Compression Conference (DCC '97), 1997

1996

Models and Resource Metrics for Parallel and Distributed Computation.

Zhiyong Li, Peter Mills, John H. Reif

Parallel Algorithms Appl., 1996

An Efficient Algorithm for the Complex Roots Problem.

C. Andrew Neff, John H. Reif

J. Complex., 1996

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

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

Inf. Comput., 1996

A Refinement Methodology for Developing Data-Parallel Applications.

Lars S. Nyland, Jan F. Prins, Allen Goldberg, Peter Mills, John H. Reif, Robert A. Wagner

Proceedings of the Euro-Par '96 Parallel Processing, 1996

Efficient Lossless Compression of Trees and Graphs.

Shenfeng Chen, John H. Reif

Proceedings of the 6th Data Compression Conference (DCC '96), Snowbird, Utah, USA, March 31, 1996

1995

The Light Bulb Problem

Ramamohan Paturi, Sanguthevar Rajasekaran, John H. Reif

Inf. Comput., March, 1995

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

Akitoshi Yoshida, Jannick P. Rolland, John H. Reif

Proceedings of the 1995 Virtual Reality Annual International Symposium, 1995

Work efficient parallel solution of Toeplitz systems and polynomial GCD.

John H. Reif

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Parallel Molecular Computation.

John H. Reif

Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, 1995

Generating Efficient Programs for Two-Level Memories from Tensor-products.

Sandeep K. S. Gupta, Zhiyong Li, John H. Reif

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.

Sotiris E. Nikoletseas, John H. Reif, Paul G. Spirakis, Moti Yung

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems.

John H. Reif

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Fast Pattern Matching for Entropy Bounded Text.

Shenfeng Chen, John H. Reif

Proceedings of the IEEE Data Compression Conference, 1995

1994

Randomized Algorithms for Binary Search and Load Balancing on Fixed Connection Networks with Geometric Applications.

John H. Reif, Sandeep Sen

SIAM J. Comput., 1994

Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems.

John H. Reif, Sandeep Sen

SIAM J. Comput., 1994

Optical computing techniques for image/video compression.

Akitoshi Yoshida, John H. Reif

Proc. IEEE, 1994

Planarity Testing in Parallel.

Vijaya Ramachandran, John H. Reif

J. Comput. Syst. Sci., 1994

Shortest Paths in the Plane with Polygonal Obstacles.

James A. Storer, John H. Reif

J. ACM, 1994

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

John H. Reif, James A. Storer

J. ACM, 1994

Motion Planning in the Presence of Moving Obstacles.

John H. Reif, Micha Sharir

J. ACM, 1994

Computability and Complexity of Ray Tracing.

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

Discret. Comput. Geom., 1994

Directed <i>s-t</i> Numberings, Rubber Bands, and Testing Digraph <i>k</i>-Vertex Connectivity.

Joseph Cheriyan, John H. Reif

Comb., 1994

Dynamic Parallel Tree Contraction (Extended Abstract).

John H. Reif, Stephen R. Tate

Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

O(log² n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices.

John H. Reif

Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Dynamic Algebraic Algorithms.

John H. Reif, Stephen R. Tate

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.

John H. Reif

Proceedings of the 8th International Symposium on Parallel Processing, 1994

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

C. Andrew Neff, John H. Reif

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Specification and Development of Parallel Algorithms with the Proteus System.

Allen Goldberg, Peter Mills, Lars S. Nyland, Jan F. Prins, John H. Reif, James Riely

Proceedings of the Specification of Parallel Algorithms, 1994

Data Compression Techniques for Stock Market Prediction.

Salman Azhar, Greg J. Badros, Arman Glodjo, Ming-Yang Kao, John H. Reif

Proceedings of the IEEE Data Compression Conference, 1994

1993

Fast and Efficient Parallel Solution of Sparse Linear Systems.

Victor Y. Pan, John H. Reif

SIAM J. Comput., 1993

Kinodynamic Motion Planning.

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

J. ACM, 1993

Continuous Alternation: The Complexity of Pursuit in Continuous Domains.

John H. Reif, Stephen R. Tate

Algorithmica, 1993

A Dynamic Separator Algorithm.

Deganit Armon, John H. Reif

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems.

Joseph Cheriyan, John H. Reif

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

The Complexity of N-body Simulation.

John H. Reif, Stephen R. Tate

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

An O(n log ^3 n) Algorithm for the Real Root Problem

John H. Reif

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

Shenfeng Chen, John H. Reif

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Multispectral Image Compression Algorithms.

Tassos Markas, John H. Reif

Proceedings of the IEEE Data Compression Conference, 1993

1992

Nested Annealing: A Provable Improvement to Simulated Annealing.

Sanguthevar Rajasekaran, John H. Reif

Theor. Comput. Sci., 1992

Compact Multigrid.

Victor Y. Pan, John H. Reif

SIAM J. Sci. Comput., 1992

On Threshold Circuits and Polynomial Computation.

John H. Reif, Stephen R. Tate

SIAM J. Comput., 1992

Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems.

John H. Reif, Sandeep Sen

SIAM J. Comput., 1992

Quad Tree Structures for Image Compression Applications.

Tassos Markas, John H. Reif

Inf. Process. Manag., 1992

Expected Parallel Time and Sequential Space Complexity of Graph and Digraph Problems.

John H. Reif, Paul G. Spirakis

Algorithmica, 1992

Optimal Randomized Parallel Algorithms for Computational Geometry.

John H. Reif, Sandeep Sen

Algorithmica, 1992

Implementations of Randomized Sorting on Large Parallel Machines.

William L. Hightower, Jan F. Prins, John H. Reif

Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Space and Time Efficient Implementations of Parallel Nested Dissection.

Deganit Armon, John H. Reif

Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Directed <i>s-t</i> Bumberings, Rubber Bands, and Testing Digraph <i>k</i>-Vertex Connectivity.

Joseph Cheriyan, John H. Reif

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Prototyping N-Body Simulation in Proteus.

Peter Mills, Lars S. Nyland, Jan F. Prins, John H. Reif

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

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

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Optical Techniques for Image Compression.

John H. Reif, Akitoshi Yoshida

Proceedings of the IEEE Data Compression Conference, 1992

1991

Parallel Tree Contraction, Part 2: Further Applications.

Gary L. Miller, John H. Reif

SIAM J. Comput., 1991

A Parallel Architecture for High-Speed Data Compression.

James A. Storer, John H. Reif

J. Parallel Distributed Comput., 1991

The Parallel Computation of Minimum Cost Paths in Graphs by Stream Contraction.

Victor Y. Pan, John H. Reif

Inf. Process. Lett., 1991

An Exact Algorithm for Kinodynamic Planning in the Plane.

John F. Canny, Ashutosh Rege, John H. Reif

Discret. Comput. Geom., 1991

An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs

Hristo N. Djidjev, John H. Reif

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Prototyping parallel and distributed programs in Proteus.

Peter Mills, Lars S. Nyland, Jan F. Prins, John H. Reif, Robert A. Wagner

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.

Alfred Brenner, Richard F. Freund, R. Stockton Gaines, Rob Kelly, Louis Lome, Richard McAndrew, Alexandru Nicolau, Janak H. Patel, Thomas Probert, John H. Reif, Jorge L. C. Sanz, Howard Jay Siegel, Jon A. Webb

Proceedings of the Fifth International Parallel Processing Symposium, Proceedings, Anaheim, California, USA, April 30, 1991

Image Compression Methods with Distortion Controlled Capabilities.

Tassos Markas, John H. Reif

Proceedings of the IEEE Data Compression Conference, 1991

1990

Optimal Size Integer Division Circuits.

John H. Reif, Stephen R. Tate

SIAM J. Comput., 1990

BLITZEN: A Highly Integrated Massively Parallel Machine.

Donald W. Blevins, Edward W. Davis, Robert A. Heaton, John H. Reif

J. Parallel Distributed Comput., 1990

Data flow analysis of distributed communicating processes.

John H. Reif, Scott A. Smolka

Int. J. Parallel Program., 1990

Randomized Algorithms for Binary Search and Load Balancing with Geometric Applications.

John H. Reif, Sandeep Sen

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

On the Bit-Complexity of Discrete Solutions of PDEs: Compact Multigrid.

Victor Y. Pan, John H. Reif

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Efficient Parallel Algorithms for Optical Computing with the DFT Primitive.

John H. Reif, Akhilesh Tyagi

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1990

The Computability and Complexity of Optical Beam Tracing

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

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Parallel Processing Can Be Harmful: The Unusual Behavior of Interpolation Search

Dan E. Willard, John H. Reif

Inf. Comput., June, 1989

Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms.

Sanguthevar Rajasekaran, John H. Reif

SIAM J. Comput., 1989

Fast and Efficient Solution of Path Algebra Problems.

Victor Y. Pan, John H. Reif

J. Comput. Syst. Sci., 1989

Parallel Tree Contraction Part 1: Fundamentals.

Gary L. Miller, John H. Reif

Adv. Comput. Res., 1989

Polling: A New Randomized Sampling Technique for Computational Geometry

John H. Reif, Sandeep Sen

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Randomization in Parallel Algorithms and its Impact on Computational Geometry.

John H. Reif, Sandeep Sen

Proceedings of the Optimal Algorithms, International Symposium, Varna, Bulgaria, May 29, 1989

Randomized Parallel Algorithms.

John H. Reif, Sandeep Sen

Proceedings of the Information Processing 89, Proceedings of the IFIP 11th World Computer Congress, San Francisco, USA, August 28, 1989

An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract)

Vijaya Ramachandran, John H. Reif

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

Efficient Parallel Pseudorandom Number Generation.

John H. Reif, J. D. Tygar

SIAM J. Comput., 1988

Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM.

Philip N. Klein, John H. Reif

SIAM J. Comput., 1988

An Efficient Parallel Algorithm for Planarity.

Philip N. Klein, John H. Reif

J. Comput. Syst. Sci., 1988

A Simple Three-Dimensional Real-Time Reliable Cellular Array.

Péter Gács, John H. Reif

J. Comput. Syst. Sci., 1988

The Complexity of Reachability in Distributed Communicating Processes.

John H. Reif, Scott A. Smolka

Acta Informatica, 1988

3-Dimensional Shortest Paths in the Presence of Polyhedral Obstacles.

John H. Reif, James A. Storer

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

On the Complexity of Kinodynamic Planning

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

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

An Efficient Output-Sensitive Hidden Surface Removal Algorithm and Its Parallelization.

John H. Reif, Sandeep Sen

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987

Minimizing turns for discrete movement in the interior of a polygon.

John H. Reif, James A. Storer

IEEE J. Robotics Autom., 1987

A logarithmic time sort for linear size networks.

John H. Reif, Leslie G. Valiant

J. ACM, 1987

A Topological Approach to Dynamic Graph Connectivity.

John H. Reif

Inf. Process. Lett., 1987

Some Polynomial and Toeplitz Matrix Computations

Victor Y. Pan, John H. Reif

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

New Lower Bound Techniques for Robot Motion Planning Problems

John F. Canny, John H. Reif

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Ranomized Parallel Computation.

Sanguthevar Rajasekaran, John H. Reif

Proceedings of the Fundamentals of Computation Theory, 1987

On threshold circuits and polynomial computation.

John H. Reif

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

Logarithmic Depth Circuits for Algebraic Functions.

John H. Reif

SIAM J. Comput., 1986

Efficient Symbolic Analysis of Programs.

John H. Reif, Harry R. Lewis

J. Comput. Syst. Sci., 1986

The Complexity of Elementary Algebra and Geometry.

Michael Ben-Or, Dexter Kozen, John H. Reif

J. Comput. Syst. Sci., 1986

Arithmetic Theories for Computational Complexity Problems

Steven Homer, John H. Reif

Inf. Control., 1986

The Logic of Distributed Protocols.

Richard E. Ladner, John H. Reif

Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

Extension of the Parallel Nested Dissection Algorithm to Path Algebra Problems.

Victor Y. Pan, John H. Reif

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

Fast and Efficient Parallel Linear Programming and Linear Least Squares Computations.

Victor Y. Pan, John H. Reif

Proceedings of the VLSI Algorithms and Architectures, 1986

1985

Unbounded Speed Variability in Distributed Communications Systems.

John H. Reif, Paul G. Spirakis

SIAM J. Comput., 1985

A Multiprocess Network Logic with Temporal and Spatial Modalities.

John H. Reif, A. Prasad Sistla

J. Comput. Syst. Sci., 1985

Depth-First Search is Inherently Sequential.

John H. Reif

Inf. Process. Lett., 1985

k-connectivity in random undirected graphs.

John H. Reif, Paul G. Spirakis

Discret. Math., 1985

Efficient Parallel Solution of Linear Systems

Victor Y. Pan, John H. Reif

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

An Optimal Parallel Algorithm for Integer Sorting

John H. Reif

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Parallel Tree Contraction and Its Application

Gary L. Miller, John H. Reif

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Probabilistic algorithms in group theory.

John H. Reif

Proceedings of the Fundamentals of Computation Theory, 1985

Efficient Parallel Pseudo-Random Number Generation.

John H. Reif, J. D. Tygar

Proceedings of the Advances in Cryptology, 1985

1984

Real-Time Synchronization of Interprocess Communications.

John H. Reif, Paul G. Spirakis

ACM Trans. Program. Lang. Syst., 1984

On Synchronous Parallel Computations with Independent Probabilistic Choice.

John H. Reif

SIAM J. Comput., 1984

The Complexity of Two-Player Games of Incomplete Information.

John H. Reif

J. Comput. Syst. Sci., 1984

Symmetric Complementation.

John H. Reif

J. ACM, 1984

The Complexity of Elementary Algebra and Geometry (Preliminary Abstract)

Michael Ben-Or, Dexter Kozen, John H. Reif

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Probabilistic Bidding Gives Optimal Distributed Resource Allocation.

John H. Reif, Paul G. Spirakis

Proceedings of the Automata, 1984

1983

The Propositional Dynamic Logic of Deterministic, Well-Structured Programs.

Joseph Y. Halpern, John H. Reif

Theor. Comput. Sci., 1983

Minimum s-t Cut of a Planar Undirected Network in O(n log²(n)) Time.

John H. Reif

SIAM J. Comput., 1983

Deriving Efficient Graph Algorithms (Summary).

John H. Reif, William L. Scherlis

Proceedings of the Logics of Programs, 1983

1982

Symbolic Program Analysis in Almost-Linear Time.

John H. Reif, Robert Endre Tarjan

SIAM J. Comput., 1982

Unbounded Speed Variability in Distributed Communication Systems.

John H. Reif, Paul G. Spirakis

Proceedings of the Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, 1982

Real Time Resource Allocation in Distributed Systems.

John H. Reif, Paul G. Spirakis

Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 1982

On the Power of Probabilistic Choice in Synchronous Parallel Computations.

John H. Reif

Proceedings of the Automata, 1982

Parallel Time O(log N) Acceptance of Deterministic CFLs

John H. Reif

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

Distributed Algorithms for Synchronizing Interprocess Communication within Real Time

John H. Reif, Paul G. Spirakis

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.

John H. Reif

Proceedings of the Automata, 1981

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

Joseph Y. Halpern, John H. Reif

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

Code Motion.

John H. Reif

SIAM J. Comput., 1980

Random Matroids

John H. Reif, Paul G. Spirakis

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

Logics for Probabilistic Programming (Extended Abstract)

John H. Reif

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

A Dynamic Logic of Multiprocessing with Incomplete Information.

John H. Reif, Gary L. Peterson

Proceedings of the Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980

1979

Universal Games of Incomplete Information

John H. Reif

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

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

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Data Flow Analysis of Communicating Processes.

John H. Reif

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)

John H. Reif

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

Multiple-Person Alternation

Gary L. Peterson, John H. Reif

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

Symbolic Programming Analysis in Almost Linear Time.

John H. Reif

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.

John H. Reif, Harry R. Lewis

Proceedings of the Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, 1977