Volume 20, Number 1, February 1991
: Absolute Factorization of Polynomials: A Geometric Approach.
: Deterministic Sampling - A New Technique for Fast Pattern Matching.
, Pei Yuan Yan
: Improved Upper and Lower Time Bounds for Parallel Random Access Machines Without Simultaneous Writes.
Volume 20, Number 2, April 1991
, Jue Xue
: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs.
Ronald V. Book
: Some Observations on Separating Complexity Classes.
: A General Sequential Time-Space Tradeoff for Finding Unique Elements.
B. K. Natarajan
: Probably Approximate Learning of Sets and Functions.
, Eli Gafni
: Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks.
: Erratum: The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses.
Volume 20, Number 3, June 1991
, Michael Clausen
: Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses.
, Micha Sharir
: On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm.
: Nondeterministic Computations in Sublogarithmic Space and Space Constructibility.
: A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions.
Volume 20, Number 4, August 1991
Erich E. Sutter
: The Fast m-Transform: A Fast Computation of Cross-Correlations with Binary m-Sequences.
Michael T. Goodrich
: Intersecting Line Segments in Parallel with an Output-Sensitive Number of Processors.
: Equality-Test and If-Then-Else Algebras: Axiomatization and Specification.
Volume 20, Number 5, October 1991
Mee Yee Chan
: Embedding of Grids into Optimal Hypercubes.
: PP is as Hard as the Polynomial-Time Hierarchy.
: On the Complexity of Learning Minimum Time-Bounded Turing Machines.
: Erratum: Factoring Polynomials Over Algebraic Number Fields.
Volume 20, Number 6, December 1991
: CREW PRAMs and Decision Trees.
Roy S. Rubinstein
: Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set.
: An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph.
John V. Franco
: Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms.