Dimitris Achlioptas WNCG Seminar: Error-Correcting Codes meet Stochastic Integration

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.

Leave a Comment