Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 41 Issue 6, Nov. 1994

Parallel algorithms for evaluating sequences of set-manipulation operations
Mikhail J. Atallah, Michael T. Goodrich, S. Rao Kosaraju
Pages: 1049-1088
DOI: 10.1145/195613.195617
Given an off-line sequence S of n set-manipulation operations, we investigate the parallel complexity of evaluating S (i.e., finding the response to every operation in S and...

Robust sharing of secrets when the dealer is honest or cheating
Tal Rabin
Pages: 1089-1109
DOI: 10.1145/195613.195621
The problem of Verifiable Secret Sharing (VSS) is the following: A dealer, who may be honest or cheating, can share a secret s, among n ≥ 2t + 1 players, where t players at...

Monte Carlo summation and integration applied to multiclass queuing networks
Keith W. Ross, Danny H. K. Tsang, Jie Wang
Pages: 1110-1135
DOI: 10.1145/195613.195630
Although many closed multiclass queuing networks have a product-form solution, evaluating their performance measures remains nontrivial due to the presence of a normalization constant. We propose the application of Monte Carlo summation in order...

Probabilistic recurrence relations
Richard M. Karp
Pages: 1136-1150
DOI: 10.1145/195613.195632

How to forget the past without repeating it
Jeffrey F. Naughton, Raghu Ramakrishnan
Pages: 1151-1177
DOI: 10.1145/195613.195634
Bottom-up evaluation of deductive database programs has the advantage that it avoids repeated computations by storing all intermediate results and replacing recomputation by table lookup. However, in general, storing all intermediate results for...

Mixed integer programming methods for computing nonmonotonic deductive databases
Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian
Pages: 1178-1215
DOI: 10.1145/195613.195637
Though the declarative semantics of both explicit and nonmonotonic negation in logic programs has been studied extensively, relatively little work has been done on computation and implementation of these semantics. In this paper, we study three...

Modular stratification and magic sets for Datalog programs with negation
Kenneth A. Ross
Pages: 1216-1266
DOI: 10.1145/195613.195646
A class of “modularly stratified” logic programs is defined. Modular stratification generalizes stratification and local stratification, while allowing programs that are not expressible as stratified programs. For modularly...

Reliable communication over unreliable channels
Yehuda Afek, Hagit Attiya, Alan Fekete, Michael Fischer, Nancy Lynch, Yishay Mansour, Dai-Wei Wang, Lenore Zuck
Pages: 1267-1297
DOI: 10.1145/195613.195651

Learning Boolean formulas
Michael Kearns, Ming Li, Leslie Valiant
Pages: 1298-1328
DOI: 10.1145/195613.195656
Efficient distribution-free learning of Boolean formulas from positive and negative examples is considered. It is shown that classes of formulas that are efficiently learnable from only positive examples or only negative examples have certain...

Average-case analysis of algorithms for matchings and related problems
Rajeev Motwani
Pages: 1329-1356
DOI: 10.1145/195613.195663