On the Complexity of the Marginal Satisfiability Problem

Abstract. The marginal satisfiability problem (MSP) asks: Given desired marginal distribu-tions DS for every subset S of c variable indices from {1,..., n}, does there exist a distribution D over n-tuples of values in {1,...,m} with those S-marginals DS? Previous authors have studied MSP in fixed dimensions, and have classified the complexity up to certain upper bounds. However, when using general dimensions, it is known that the size of distributions grows exponentially, mak-ing brute force algorithms impractical. This presents an incentive to study more general, tractable variants, which in turn may shed light on the original problem’s structure. Thus, our work seeks to explore MSP and its variants for arbitrary dimension, and pinpoint its complexity more precisely. We solve MSP for n = 2 and completely characterize the complexity of three closely related variants of MSP. In particular, we detail novel greedy and stochastic algorithms that handle exponentially-sized data structures in polynomial time, as well as generate accurate representative samples of these structures in polynomial time. These algorithms are also unique in that they represent possible protocols in data compression for communication purposes. Finally, we posit conjectures related to more generalized MSP variants, as well as the original MSP.