Journal of the ACM -- 1998

Volume 45, Number 1, January 1998

Michael Benedikt, Guozhu Dong, Leonid Libkin, and Limsoon Wong. Relational expressive power of constraint query languages. Journal of the ACM, 45(1):1-34, January 1998. References, Citations, etc. [BibTeX entry]
Alan Fekete, M. Frans Kaashoek, and Nancy Lynch. Implementing sequentially consistent shared objects using broadcast and point-to-point communication. Journal of the ACM, 45(1):35-69, January 1998. References, etc. [BibTeX entry]
Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, January 1998. References, Citations, etc. [BibTeX entry]
Michael Saks, Aravind Srinivasan, and Shiyu Zhou. Explicit OR-dispersers with polylogarithmic degree. Journal of the ACM, 45(1):123-154, January 1998. References, Citations, etc. [BibTeX entry]
Ji\v{r}í \v{S}íma and Ji\v{r}í Wiedermann. Theory of neuromata. Journal of the ACM, 45(1):155-178, January 1998. References, etc. [BibTeX entry]
Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim. A new general derandomization method. Journal of the ACM, 45(1):179-213, January 1998. References, Citations, etc. [BibTeX entry]
Ronald Fagin and Joseph Y. Halpern. Corrigendum: Reasoning about knowledge and probability. Journal of the ACM, 45(1):214, January 1998. References. [BibTeX entry]

Xiaotie Deng, Tiko Kameda, and Christos Papadimitriou. How to learn an unknown environment I: The rectilinear case. Journal of the ACM, 45(2):215-245, March 1998. References, etc. [BibTeX entry]
David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246-265, March 1998. References, etc. [BibTeX entry]
Tamal K. Dey and Sumanta Guha. Computing homology groups of simplicial complexes in R^3. Journal of the ACM, 45(2):266-287, March 1998. References, etc. [BibTeX entry]
Conrado Martínez and Salvador Roura. Randomized binary search trees. Journal of the ACM, 45(2):288-323, March 1998. References, etc. [BibTeX entry]
P. D. Mackenzie, C. G. Plaxton, and R. Rajaraman. On contention resolution protocols and associated probabilistic phenomena. Journal of the ACM, 45(2):324-378, March 1998. References, etc. [BibTeX entry]

Joseph Y. Halpern. Time to publication: A progress report. Journal of the ACM, 45(3):379-380, May 1998. [BibTeX entry]
Paulo Fernandes, Brigitte Plateau, and William J. Stewart. Efficient descriptor-vector multiplications in stochastic automata networks. Journal of the ACM, 45(3):381-414, May 1998. References, etc. [BibTeX entry]
James Aspnes. Lower bounds for distributed coin-flipping and randomized consensus. Journal of the ACM, 45(3):415-450, May 1998. References, etc. [BibTeX entry]
Prasad Jayanti, Tushar Deepak Chandra, and Sam Toueg. Fault-tolerant wait-free shared objects. Journal of the ACM, 45(3):451-500, May 1998. References, etc. [BibTeX entry]
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998. References, etc. [BibTeX entry]