Ashok K. Chandra, Philip M. Merlin
Proceedings of the ninth annual ACM Symposium on Theory of Computing, STOC 1977, 1977
We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. ...
The nearest neighbor problem is the follolving: Given a set of n points P = (PI, . . . ,p,} in some metric space X, preprocess P so as to efficiently answer queries which require finding bhe point in P closest to a query point q E X. We focus on the ...
Oded Goldreich, Silvio Micali, Avi Wigderson
Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987
We present a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the ...
Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, 1982
Two complexity measures for query languages are proposed. Data complexity is the complexity of evaluating a query in the language as a function of the size of the database, and expression complexity is the complexity of evaluating a query in the ...
David R. Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin, Frank Thomson Leighton
We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for use with very large networks such as the Internet, ...
Proceedings of the third annual ACM Symposium on Theory of Computing, STOC 1971, 1971
It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology. Here “reduced” means, roughly ...
Long a matter of folklore, the "small-world phenomenon" -the principle that we are all linked by short chains of acquaintances -was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley ...
Michael Ben-Or, Shafi Goldwasser, Avi Wigderson
Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 1988
Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that: If no faults occur, no set of size t < n/2 of players gets any additional information (other than the function value), Even if ...
Noga Alon, Yossi Matias, Mario Szegedy
The frequency moments of a sequence containing m~ elements of type i, for 1 ~ z ~ n, are the numbers F& = ~~=1 m?. We consider the space complexity of randomized algorithms that approximate the numbers Fk, when the elements of the sequence are ...
Proceedings of the tenth annual ACM Symposium on Theory of Computing, STOC 1978, 1978
A model of computation based on random access machines operating in parallel and sharing a common memory is presented. The computational power of this model is related to that of traditional models. In particular, deterministic parallel RAM's can ...