Journal of the ACM

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 the ...

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 techniques ...

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 ...

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 three ...