JCSS, Volume 39

Volume 39, Number 1, August 1989

Selected Papers of the Structure in Complexity Theory Conference, June 16-19, 1987 - Part 1

Moon-Jung Chung, Bala Ravikumar: Strong Nondeterministic Turing Reduction - A Technique for Proving Intractability. 2-20
Martín Abadi, Joan Feigenbaum, Joe Kilian: On Hiding Information from an Oracle. 21-50
Daniel Leivant: Descriptive Characterizations of Computational Complexity. 51-83
Uwe Schöning: Probabilistic Complexity Classes and Lowness. 84-100
Eric Allender: Some Consequences of the Existence of Pseudorandom Generators. 101-124

Leonidas J. Guibas, John Hershberger: Optimal Shortest Path Queries in a Simple Polygon. 126-152
N. Dadoun, David G. Kirkpatrick: Parallel Construction of Subdivision Hierarchies. 153-165
Joseph C. Culberson, Robert A. Reckhow: Orthogonally Convex Coverings of Orthogonal Polygons without Holes. 166-204
Paul Chew: There are Planar Graphs Almost as Good as the Complete Graph. 205-219
Subhash Suri: Computing Geodesic Furthest Neighbors in Simple Polygons. 220-235
Kokichi Sugihara: On Finite-Precision Representations of Geometric Objects. 236-247

Selected Papers of the Structure in Complexity Theory Conference, June 16-19, 1987 - Part 2

Klaus Ambos-Spies: Honest Polynomial Time Reducibilities and the P = ? NP Problem. 250-281
Jim Kadin: P^(NP[O(log n)]) and Sparse Turing-Complete Sets for NP. 282-298
Lane A. Hemachandra: The Strong Exponential Hierarchy Collapses. 299-322
Raymond Greenlaw: Ordered Vertex Removal and Subgraph Problems. 323-342
Pierre America, Jan J. M. M. Rutten: Solving Reflexive Domain Equations in a Category of Complete Metric Spaces. 343-375
A. G. Robinson, A. J. Goldman: The Set Coincidence Game: Complexity, Attainability, and Symmetric Strategies. 376-387