enter search term and/or author name
Mini-buckets: A general scheme for bounded inference
Rina Dechter, Irina Rish
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
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
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
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...