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.
Speaker Bio: 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.