Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 50 Issue 2, March 2003

Mini-buckets: A general scheme for bounded inference
Rina Dechter, Irina Rish
Pages: 107-153
DOI: 10.1145/636865.636866
This article presents a class of approximation algorithms that extend the idea of bounded-complexity inference, inspired by successful constraint propagation algorithms, to probabilistic inference and combinatorial optimization. The idea is to bound...

Time-space trade-off lower bounds for randomized computation of decision problems
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee
Pages: 154-195
DOI: 10.1145/636865.636867
We prove the first time-space lower bound trade-offs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our...

A complete problem for statistical zero knowledge
Amit Sahai, Salil Vadhan
Pages: 196-249
DOI: 10.1145/636865.636868
We present the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called Statistical Difference, is to decide whether two efficiently samplable...

A foundation for designing deadlock-free routing algorithms in wormhole networks
D. N. Jayasimha, Loren Schwiebert, D. Manivannan, Jeff A. May
Pages: 250-275
DOI: 10.1145/636865.636869
This article provides necessary and sufficient conditions for deadlock-free unicast and multicast routing with the path-based routing model in interconnection networks that use the wormhole switching technique. The theory is developed around...