BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Stochastic discrete integration - Adrian Weller\;Nilesh Tripuranen
 i (University of Cambridge)
DTSTART:20160114T143000Z
DTEND:20160114T160000Z
UID:TALK62023@talks.cam.ac.uk
CONTACT:Yingzhen Li
DESCRIPTION:We will focus most of our effort on understanding the recently
  proposed WISH algorithm of Ermon\, Selman\, Gomes and Sabharwal for appro
 ximating partition functions and then explain recent extensions of the ori
 ginal work as well as connections to coding theory. The WISH algorithm is 
 a randomized algorithm that\, with high probability\, gives a constant-fac
 tor approximation of a general discrete integral defined over an exponenti
 ally large set. WISH estimates partition functions by piecing together MAP
  solutions to a small number of discrete combinatorial optimization proble
 ms subject to randomly generated parity constraints (effectively convertin
 g a summation problem into a constrained optimization problem).\n\nThe tal
 k will assume no prior background but familiarity with the basics of graph
 ical models (i.e. what is an Ising model) and things like basic concentrat
 ion inequalities (Markov's Inequality\, etc...)/union bounds will be usefu
 l\; some of these will be reviewed as necessary.\n\nRelevant Papers (you d
 on't need to read before coming):\n\nS. Ermon\, C. Gomes\, A. Sabharwal\, 
 B. Selman\, Taming the Curse\nof Dimensionality: Discrete Integration by H
 ashing and\nOptimization. ICML 2013.\n\nD. Achlioptas\, P. Jiang\, Stochas
 tic Integration via Error-Correcting\nCodes. UAI 2015.
LOCATION:Engineering Department\, CBL Room 438
END:VEVENT
END:VCALENDAR