  Many probabilistic inference tasks involve summations over exponentially
large sets. Recently, it has been shown that these problems can be reduced to
solving a polynomial number of MAP inference queries for a model augmented with
randomly generated parity constraints. By exploiting a connection with
max-likelihood decoding of binary codes, we show that these optimizations are
computationally hard. Inspired by iterative message passing decoding
algorithms, we propose an Integer Linear Programming (ILP) formulation for the
problem, enhanced with new sparsification techniques to improve decoding
performance. By solving the ILP through a sequence of LP relaxations, we get
both lower and upper bounds on the partition function, which hold with high
probability and are much tighter than those obtained with variational methods.
