BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Statistical algorithms and planted satisfiability problems - Will 
 Perkins (Birmingham)
DTSTART:20160205T160000Z
DTEND:20160205T170000Z
UID:TALK63641@talks.cam.ac.uk
CONTACT:Quentin Berthet
DESCRIPTION:I will discuss a general framework originating in learning the
 ory for proving average-case algorithmic lower bounds for the class of “
 statistical algorithms”. I will give an overview of the types of algorit
 hmic approaches that can be implemented in this framework\, and then discu
 ss the example of planted random satisfiability problems\, for which we ca
 n identify a tractability threshold for statistical algorithms.  Based on 
 joint work with Vitaly Feldman and Santosh Vempala.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge.
END:VEVENT
END:VCALENDAR