@article{Benedikt-Dong-Libkin-Wong/98,
AUTHOR = {Benedikt, Michael and Dong, Guozhu and Libkin, Leonid and Wong, Limsoon},
TITLE = {Relational expressive power of constraint query languages},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {1},
PAGES = {1-34},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/273865.273870},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fekete-Kaashoek-Lynch/98,
AUTHOR = {Fekete, Alan and Kaashoek, M. Frans and Lynch, Nancy},
TITLE = {Implementing sequentially consistent shared objects using broadcast and point-to-point communication},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {1},
PAGES = {35-69},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/273865.273884},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Arora-Safra/98,
AUTHOR = {Arora, Sanjeev and Safra, Shmuel},
TITLE = {Probabilistic checking of proofs: A new characterization of $NP$},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {1},
PAGES = {70-122},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/273865.273901},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Saks-Srinivasan-Zhou/98,
AUTHOR = {Saks, Michael and Srinivasan, Aravind and Zhou, Shiyu},
TITLE = {Explicit $OR$-dispersers with polylogarithmic degree},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {1},
PAGES = {123-154},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/273865.273915},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Sma-Wiedermann/98,
AUTHOR = {{\v{S}}{\'{\i}}ma, Ji{\v{r}}{\'{\i}} and Wiedermann, Ji{\v{r}}{\'{\i}}},
TITLE = {Theory of neuromata},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {1},
PAGES = {155-178},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/273865.273914},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Andreev-Clementi-Rolim/98,
AUTHOR = {Andreev, Alexander E. and Clementi, Andrea E.F. and Rolim, Jos{\'{e}} D.P.},
TITLE = {A new general derandomization method},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {1},
PAGES = {179-213},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/273865.273933},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fagin-Halpern/98,
AUTHOR = {Fagin, Ronald and Halpern, Joseph Y.},
TITLE = {Erratum to ''Reasoning about knowledge and probability''},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {1},
PAGES = {214-214},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/273865.274429},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
NOTE = {Originally in J. ACM, Vol. 41, 1994, No. 2, 340-367},
}
@article{Deng-Kameda-Papadimitriou/98,
AUTHOR = {Deng, Xiaotie and Kameda, Tiko and Papadimitriou, Christos},
TITLE = {How to learn an unknown environment I: The rectilinear case},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {2},
PAGES = {215-245},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/274787.274788},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Karger-Motwani-Sudan/98,
AUTHOR = {Karger, David and Motwani, Rajeev and Sudan, Madhu},
TITLE = {Approximate graph coloring by semidefinite programming},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {2},
PAGES = {246-265},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/274787.274791},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Dey-Guha/98,
AUTHOR = {Dey, Tamal K. and Guha, Sumanta},
TITLE = {Computing homology groups of simplicial complexes in $R^3$},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {2},
PAGES = {266-287},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/274787.274810},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Martnez-Roura/98,
AUTHOR = {Mart{\'{\i}}nez, Conrado and Roura, Salvador},
TITLE = {Randomized binary search trees},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {2},
PAGES = {288-323},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/274787.274812},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{MacKenzie-Plaxton-Rajaraman/98,
AUTHOR = {MacKenzie, P.D. and Plaxton, C.G. and Rajaraman, R.},
TITLE = {On contention resolution protocols and associated probabilistic phenomena},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {2},
PAGES = {324-378},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/274787.274816},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fernandes-Plateau-Stewart/98,
AUTHOR = {Fernandes, Paulo and Plateau, Brigitte and Stewart, William J.},
TITLE = {Efficient descriptor-vector multiplications in stochastic automata networks},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {3},
PAGES = {381-414},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/278298.278303},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Aspnes/98,
AUTHOR = {Aspnes, James},
TITLE = {Lower bounds for distributed coin-flipping and randomized consensus},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {3},
PAGES = {415-450},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/278298.278304},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Jayanti-Chandra-Toueg/98,
AUTHOR = {Jayanti, Prasad and Chandra, Tushar Deepak and Toueg, Sam},
TITLE = {Fault-tolerant wait-free shared objects},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {3},
PAGES = {451-500},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/278298.278305},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Arora-Lund-Motwani-Sudan-Szegedy/98,
AUTHOR = {Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and Sudan, Madhu and Szegedy, Mario},
TITLE = {Proof verification and the hardness of approximation problems},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {3},
PAGES = {501-555},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/278298.278306},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Pong-Dubois/98,
AUTHOR = {Pong, Fong and Dubois, Michel},
TITLE = {Formal verification of complex coherence protocols using symbolic state models},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {4},
PAGES = {557-587},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/285055.285057},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kifer/98,
AUTHOR = {Kifer, Michael},
TITLE = {On the decidability and axiomatization of query finiteness in deductive databases},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {4},
PAGES = {588-633},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/285055.285058},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Feige/98,
AUTHOR = {Feige, Uriel},
TITLE = {A threshold of $ln n$ for approximating set cover},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {4},
PAGES = {634-652},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/285055.285059},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Goldreich-Goldwasser-Ron/98,
AUTHOR = {Goldreich, Oded and Goldwasser, Shari and Ron, Dana},
TITLE = {Property testing and its connection to learning and approximation},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {4},
PAGES = {653-750},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/285055.285060},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Arora/98,
AUTHOR = {Arora, Sanjeev},
TITLE = {Polynomial time approximation schemes for Euclidean Traveling Salesman and other geometric problems},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {5},
PAGES = {753-782},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/290179.290180},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Goldberg-Rao/98,
AUTHOR = {Goldberg, Andrew V. and Rao, Satish},
TITLE = {Beyond the flow decomposition barrier},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {5},
PAGES = {783-797},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/290179.290181},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Abiteboul-Kanellakis/98,
AUTHOR = {Abiteboul, Serge and Kanellakis, Paris C.},
TITLE = {Object identity as a query language primitive},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {5},
PAGES = {798-842},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/290179.290182},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fich-Herlihy-Shavit/98,
AUTHOR = {Fich, Faith and Herlihy, Maurice and Shavit, Nir},
TITLE = {On the space complexity of randomized synchronization},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {5},
PAGES = {843-862},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/290179.290183},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bshouty-Goldman-Mathias-Suri-Tamaki/98,
AUTHOR = {Bshouty, Nader H. and Goldman, Sally A. and Mathias, H. David and Suri, Subhash and Tamaki, Hisao},
TITLE = {Noise-tolerant distribution-free learning of general geometric concepts},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {5},
PAGES = {863-890},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/290179.290184},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Arya-Mount-Netanyahu-Silverman-Wu/98,
AUTHOR = {Arya, Sunil and Mount, David M. and Netanyahu, Nathan S. and Silverman, Ruth and Wu, Angela Y.},
TITLE = {An optimal algorithm for approximate nearest neighbor searching fixed dimensions},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {6},
PAGES = {891-923},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/293347.293348},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Pellegrini/98,
AUTHOR = {Pellegrini, Marco},
TITLE = {Electrostatic fields without singularities: Theory, algorithms and error analysis},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {6},
PAGES = {924-964},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/293347.293349},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Chor-Goldreich-Kushilevitz-Sudan/98,
AUTHOR = {Chor, Benny and Goldreich, Oded and Kushilevitz, Eyal and Sudan, Madhu},
TITLE = {Private information retrieval},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {6},
PAGES = {965-982},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/293347.293350},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kearns/98a,
AUTHOR = {Kearns, Michael},
TITLE = {Efficient noise-tolerant learning from statistical queries},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {6},
PAGES = {983-1006},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/293347.293351},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bachmair-Ganzinger/98,
AUTHOR = {Bachmair, Leo and Ganzinger, Harald},
TITLE = {Ordered chaining calculi for first-order theories of transitive relations},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {6},
PAGES = {1007-1049},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/293347.293352},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Karp-Zhang/98,
AUTHOR = {Karp, Richard M. and Zhang, Yangun},
TITLE = {On parallel evaluation of game trees},
JOURNAL = {J. ACM},
VOLUME = {45},
NUMBER = {6},
PAGES = {1050-1075},
YEAR = {1998},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/293347.293353},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}