Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 45 Issue 1, Jan. 1998

Relational expressive power of constraint query languages
Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong
Pages: 1-34
DOI: 10.1145/273865.273870
The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be...

Implementing sequentially consistent shared objects using broadcast and point-to-point communication
Alan Fekete, M. Frans Kaashoek, Nancy Lynch
Pages: 35-69
DOI: 10.1145/273865.273884
This paper presents and proves correct a distributed algorithm that implements a sequentially consistent collection of shared read/update objects. This algorithm is a generalization of one used in the Orca shared object system. The algorithm...

Probabilistic checking of proofs: a new characterization of NP
Sanjeev Arora, Shmuel Safra
Pages: 70-122
DOI: 10.1145/273865.273901
We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in...

Explicit OR-dispersers with polylogarithmic degree
Michael Saks, Aravind Srinivasan, Shiyu Zhou
Pages: 123-154
DOI: 10.1145/273865.273915
An (N, M, T)-OR-disperser is a bipartite multigraph G=(V, W, E) with |V| = N, and |W| = M, having the following expansion...

Theory of neuromata
Jiří Šíma, Jiří Wiedermann
Pages: 155-178
DOI: 10.1145/273865.273914
A finite automaton—the so-called neuromaton, realized by a finite discrete recurrent neural network, working in parallel computation mode, is considered. Both the size of neuromata (i.e., the number of neurons) and their descriptional...

A new general derandomization method
Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim
Pages: 179-213
DOI: 10.1145/273865.273933
We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set...

Corrigendum: “Reasoning about knowledge and probability”
Ronald Fagin, Joseph Y. Halpern
Page: 214
DOI: 10.1145/273865.274429