BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Reducibility and Computational Lower Bounds for Problems with Plan
 ted Sparse Structure - Guy Bresler (Massachusetts Institute of Technology)
DTSTART:20180626T080000Z
DTEND:20180626T084500Z
UID:TALK107392@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:The prototypical high-dimensional statistics problem entails f
 inding a structured signal in noise. Many of these problems exhibit a curi
 ous phenomenon: the amount of data needed by all known computationally eff
 icient algorithms far exceeds what is needed for inefficient algorithms th
 at search over all possible structures. A line of work initiated by Berthe
 t and Rigollet in 2013 has aimed to explain these gaps by reducing from co
 njecturally hard problems in computer science. However\, the delicate natu
 re of average-case reductions has limited the applicability of this approa
 ch. In this work we introduce several new techniques to give a web of aver
 age-case reductions showing strong computational lower bounds based on the
  planted clique conjecture. These include tight lower bounds for Planted I
 ndependent Set\, Planted Dense Subgraph\, Sparse Spiked Wigner\, Sparse PC
 A\, as well as for new models that we introduce. Joint work with Matthew B
 rennan and Wasim Huleihel.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR