WNCG Seminar Series: Error-Correcting Codes meet Stochastic Integration

Friday, September 25, 2015
UTA 7.532

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. 


University of California in Santa Cruz

Dimitris Achlioptas joined the Department of Computer Science of UC Santa Cruz in 2006, following his Ph.D. from the University of Toronto and a 7 year stint at Microsoft Research, Redmond. In theory, his expertise lies in the interaction between randomness and computation and his work on that topic has appeared in journals including Nature, Science, and the Annals of Mathematics. For that work has received an NSF CAREER award, a Sloan Fellowship, and an ERC Starting Grant. In practice, he likes to think about scalability questions and holds over twenty US patents on topics ranging from load balancing and cache optimization to web search personalization.