Journal of the ACM, Volume 45, 1998

Volume 45, Number 1, January 1998

• Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong:
  Relational Expressive Power of Constraint Query Languages. 1-34
  
• Alan Fekete, M. Frans Kaashoek, Nancy A. Lynch:
  Implementing Sequentially Consistent Shared Objects using Broadcast and Point-to-Point Communication. 35-69
  
• Sanjeev Arora, Shmuel Safra:
  Probabilistic Checking of Proofs: A New Characterization of NP. 70-122
  
• Michael E. Saks, Aravind Srinivasan, Shiyu Zhou:
  Explicit OR-Dispersers with Polylogarithmic Degree. 123-154
  
• Jirí Síma, Jirí Wiedermann:
  Theory of Neuromata. 155-178
  
• Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
  A New General Derandomization Method. 179-213
  

Volume 45, Number 2, March 1998

• Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou:
  How to Learn an Unknown Environment I: The Rectilinear Case. 215-245
  
• David R. Karger, Rajeev Motwani, Madhu Sudan:
  Approximate Graph Coloring by Semidefinite Programming. 246-265
  
• Tamal K. Dey, Sumanta Guha:
  Computing Homology Groups of Simplicial Complexes in R³. 266-287
  
• Conrado Martínez, Salvador Roura:
  Randomized Binary Search Trees. 288-323
  
• Philip D. MacKenzie, C. Greg Plaxton, Rajmohan Rajaraman:
  On Contention Resolution Protocols and Associated Probabilistic Phenomena. 324-378
  

Volume 45, Number 3, May 1998

• Joseph Y. Halpern:
  Time to Publication: A Progress Report. 379-380
  
• Paulo Fernandes, Brigitte Plateau, William J. Stewart:
  Efficient Descriptor-Vector Multiplications in Stochastic Automata Networks. 381-414
  
• James Aspnes:
  Lower Bounds for Distributed Coin-Flipping and Randomized Consensus. 415-450
  
• Prasad Jayanti, Tushar Deepak Chandra, Sam Toueg:
  Fault-Tolerant Wait-Free Shared Objects. 451-500
  
• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
  Proof Verification and the Hardness of Approximation Problems. 501-555
  

Volume 45, Number 4, July 1998

• Fong Pong, Michel Dubois:
  Formal Verification of Complex Coherence Protocols Using Symbolic State Models. 557-587
  
• Michael Kifer:
  On the Decidability and Axiomatization of Query Finiteness in Deductive Databases. 588-633
  
• Uriel Feige:
  A Threshold of ln n for Approximating Set Cover. 634-652
  
• Oded Goldreich, Shafi Goldwasser, Dana Ron:
  Property Testing and its Connection to Learning and Approximation. 653-750
  

Volume 45, Number 5, September 1998

• Sanjeev Arora:
  Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. 753-782
  
• Andrew V. Goldberg, Satish Rao:
  Beyond the Flow Decomposition Barrier. 783-797
  
• Serge Abiteboul, Paris C. Kanellakis:
  Object Identity as a Query Language Primitive. 798-842
  
• Faith Ellen Fich, Maurice Herlihy, Nir Shavit:
  On the Space Complexity of Randomized Synchronization. 843-862
  
• Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki:
  Noise-Tolerant Distribution-Free Learning of General Geometric Concepts. 863-890
  

Volume 45, Number 6, November 1998

• Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu:
  An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions. 891-923
  
• Marco Pellegrini:
  Electrostatic Fields Without Singularities: Theory, Algorithms and Error Analysis. 924-964
  
• Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan:
  Private Information Retrieval. 965-981
  
• Michael J. Kearns:
  Efficient Noise-Tolerant Learning from Statistical Queries. 983-1006
  
• Leo Bachmair, Harald Ganzinger:
  Ordered Chaining Calculi for First-Order Theories of Transitive Relations. 1007-1049
  
• Richard M. Karp, Yangun Zhang:
  On Parallel Evaluation of Game Trees. 1050-1075