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

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

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

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