Journal of Computer and System Sciences

EDITORS' FOREWORD
pp. 125-125(1)
Authors: Cai J-Y.; Selman A.

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
pp. 127-143(17)
Authors: Agrawal M.; Allender E.; Rudich S.

Integer Programming as a Framework for Optimization and Approximability
pp. 144-161(18)
Authors: Barland I.; Kolaitis P.G.; Thakur M.N.

Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle
pp. 162-171(10)
Authors: Buss S.R.; Pitassi T.

DNA Models and Algorithms for NP-Complete Problems
pp. 172-186(15)
Authors: Bach E.; Condon A.; Glaser E.; Tanguay C.

Zero Knowledge and the Chromatic Number
pp. 187-199(13)
Authors: Feige U.; Kilian J.

Nondeterministic NC¹ Computation
pp. 200-212(13)
Authors: Caussinus H.; McKenzie P.; Thérien D.; Vollmer H.

Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets
pp. 213-232(20)
Author: van Melkebeek D.