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:Isaac Newton Institute Seminar Series
SUMMARY:Proof complexity of circuit lower bounds - Pich\,
J (RWTH Aachen University)
DTSTART;TZID=Europe/London:20120329T160000
DTEND;TZID=Europe/London:20120329T163000
UID:TALK37158AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37158
DESCRIPTION:Techniques that could resolve P vs. NP are conside
rably restricted by well-known barriers in computa
tional complexity. There are several corresponding
results in logic stating that certain fragments o
f arithmetic are not sufficiently strong to prove
that P differs from NP or some similar conjectures
. We investigate possible extensions of these barr
iers to stronger\ntheories. Mainly\, Razborov's c
onjecture about hardness of Nisan-Wigderson genera
tors for Extended Frege systems and natural proofs
in proof systems admitting feasible disjunction p
roperty pointed out by Rudich.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR