JCSS, Volume 60

Volume 60, Number 1, February 2000

Bin Ma, Lusheng Wang: On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints. 1-12 BibTeX
Wan Fokkink: Rooted Branching Bisimulation as a Congruence. 13-37 BibTeX
Jinde Cao: Global Exponential Stability and Periodic Solutions of Delayed Cellular Neural Networks. 38-46 BibTeX
Tatsuaki Okamoto: On Relationships between Statistical Zero-Knowledge Proofs. 47-108 BibTeX
Klaus-Jörn Lange, Rolf Niedermeier: Data Independence of Read, Write, and Control Structures in PRAM Computations. 109-144 BibTeX
József Békési, Gábor Galambos, Hans Kellerer: A 5/4 Linear Time Bin Packing Algorithm. 145-160 BibTeX
Rocco A. Servedio: Computational Sample Complexity and Attribute-Efficient Learning. 161-178 BibTeX
Jinde Cao, Qing Tao: Estimation of the Domain of Attraction and the Convergence Rate of a Hopfield Associative Memory and an Application. 179-186 BibTeX
Christel Baier, Bettina Engelen, Mila E. Majster-Cederbaum: Deciding Bisimilarity and Similarity for Probabilistic Processes. 187-231 BibTeX

Vijay Raghavan: Editor's Foreword. 233 BibTeX
John Case, Sanjay Jain, Matthias Ott, Arun Sharma, Frank Stephan: Robust Learning Aided by Context. 234-257 BibTeX
Andreas Birkendorf, Norbert Klasner, Christian Kuhlmann, Hans-Ulrich Simon: Structural Results about Exact Learning with Unspecified Attribute Values. 258-277 BibTeX
Christopher D. Rosin: Sample Complexity of Model-Based Search. 278-301 BibTeX
Rüdiger Reischuk, Thomas Zeugmann: An Average-Case Optimal One-Variable Pattern Language Learner. 302-335 BibTeX

José L. Balcázar: Editor's Foreword. 336 BibTeX
Lance Fortnow: Time-Space Tradeoffs for Satisfiability. 337-353 BibTeX
Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp: Reversible Space Equals Deterministic Space. 354-367 BibTeX
Cristopher Moore, Denis Thérien, François Lemieux, Joshua Berman, Arthur Drisko: Circuits and Expressions with Nonassociative Gates. 368-394 BibTeX
Manindra Agrawal, Eric Allender, Samir Datta: On TC⁰, AC⁰, and Arithmetic Circuits. 395-421 BibTeX
Richard Beigel, Bin Fu: Circuits over PP and PL. 422-441 BibTeX
Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin: Inequalities for Shannon Entropy and Kolmogorov Complexity. 442-464 BibTeX
Rodney G. Downey, André Nies: Undecidability Results for Low Complexity Time Classes. 465-479 BibTeX

Fan Chung Graham: Guest Editor's Foreword. 481 BibTeX
William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Adaptive Packet Routing for Bursty Adversarial Traffic. 482-509 BibTeX
Uriel Feige: Approximating the Bandwidth via Volume Respecting Embeddings. 510-539 BibTeX
Oded Goldreich, Shafi Goldwasser: On the Limits of Nonapproximability of Lattice Problems. 540-563 BibTeX
Gruia Calinescu, Howard J. Karloff, Yuval Rabani: An Improved Approximation Algorithm for MULTIWAY CUT. 564-574 BibTeX
Sanjeev Khanna, Shiyu Zhou: On Indexed Data Broadcast. 575-591 BibTeX
Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin: Protecting Data Privacy in Private Information Retrieval Schemes. 592-629 BibTeX
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher: Min-Wise Independent Permutations. 630-659 BibTeX
Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer: The Closure of Monadic NP. 660-716 BibTeX
Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. 717-751 BibTeX