Corelab Seminar

Dimitris Achlioptas
New Uses of Error-Correcting Codes

We consider the task of summing (integrating) an arbitrary non-negative function over a discrete domain. This is a ubiquitous task, known as partition function estimation in the context of graphical models. 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.

Based on joint work with Pei Jiang.