We consider the task of summing (integrating) a non-negative function over a discrete domain, e.g., to compute the partition function of a graphical model. It is known that in a probabilistic approximate sense, summation can be reduced to maximization over random subsets of the domain defined by systems of linear equations modulo 2 (parity constraints). Unfortunately, random parity constraints with many variables are computationally intractable, while random parity constraints with few variables have poor statistical performance.
We introduce two ideas to address these problems, both motivated by the theory of error-correcting codes. The first idea exploits linearity to exponentially reduce the size of the domain. The second idea, closer in spirit to the original approach, is to use systems of linear equations defining Low Density Parity Check (LDPC) codes. Even though the equations in such systems only contain few variables each, their sets of solutions (codewords) have excellent statistical properties. By combining these ideas we achieve dramatic speedup over the original approach and levels of accuracy that were completely unattainable previously.
Watch the presentation online on the WNCG YouTube Channel.