BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Hardness magnification near state-of-the-art lower
bounds - Jan Pich\, Oxford
DTSTART;TZID=Europe/London:20190510T140000
DTEND;TZID=Europe/London:20190510T150000
UID:TALK122935AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/122935
DESCRIPTION:Hardness magnification is a strategy for deriving
strong circuit lower bounds by reducing them to a
refined analysis of weaker models proposed by Oliv
eira and Santhanam (2018). I will present several
improvements of their initial results. For example
\, we will consider\na gap version of the meta-com
putational problem MCSP\, which asks to distinguis
h truth-tables of Boolean functions of small circu
it complexity from truth-tables of a slightly larg
er complexity\, and establish that a small improve
ment over the state-of-the-art lower bounds in a v
ariety of computational models for the gap version
of MCSP would imply explicit super-polynomial low
er bounds.\nThis talk is based on a joint work wit
h Igor C. Oliveira and Rahul Santhanam and on an o
ngoing work with Igor C. Oliveira\, Ninad Rajgopal
and Rahul Santhanam.
LOCATION:FW26
CONTACT:Victor Gomes
END:VEVENT
END:VCALENDAR