Volume 69, Number 1, 15 January 1999
: Finding a Minimal 1-DNF Consistent with a Positive Sample is LOGSNP-Complete.
: A Note on the Horton-Strahler Number for Random Binary Search Trees.
Volume 69, Number 2, 29 January 1999
, Guoliang Xue
: Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-Length.
: Relative to a Random Oracle, P/Poly is not Measurable in EXP.
Volume 69, Number 3, 12 February 1999
: On the Complexity of Quality of Service Routing.
: A Separation of Two Randomness Concepts.
Volume 69, Number 4, 26 February 1999
: A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes.
: Depth-Efficient Simulation of Boolean Semi-Unbounded Circuits by Arithmetic Ones.
V. A. Nepomniaschy
: Symbolic Verification Method for Definite Iteration over Data Structures.
Volume 69, Number 5, 12 March 1999
: A Structured Approach for Developing Concurrent Programs in Java.
Volume 69, Number 6, 26 March 1999
: Linear Codes are Hard for Oblivious Read-Once Parity Branching Programs.
: A Rewriting Technique for Universal Polynomial Invariants.
, Chi-Ming Hu
: Inter-Protocol Interleaving Attacks on Some Authentication and Key Distribution Protocols.
: Construction of Halvers.
: Relativized Worlds with an Infinite Hierarchy.