BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Hardness magnification near state-of-the-art lower bounds - Jan Pi
 ch\, Oxford
DTSTART:20190510T130000Z
DTEND:20190510T140000Z
UID:TALK122935@talks.cam.ac.uk
CONTACT:Victor Gomes
DESCRIPTION:Hardness magnification is a strategy for deriving strong circu
 it lower bounds by reducing them to a refined analysis of weaker models pr
 oposed by Oliveira and Santhanam (2018). I will present several improvemen
 ts of their initial results. For example\, we will consider\na gap version
  of the meta-computational problem MCSP\, which asks to distinguish truth-
 tables of Boolean functions of small circuit complexity from truth-tables 
 of a slightly larger complexity\, and establish that a small improvement o
 ver the state-of-the-art lower bounds in a variety of computational models
  for the gap version of MCSP would imply explicit super-polynomial lower b
 ounds.\nThis talk is based on a joint work with Igor C. Oliveira and Rahul
  Santhanam and on an ongoing work with Igor C. Oliveira\, Ninad Rajgopal a
 nd Rahul Santhanam.
LOCATION:FW26
END:VEVENT
END:VCALENDAR