BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Proof complexity of circuit lower bounds - Pich\, J (RWTH Aachen U
 niversity)
DTSTART:20120329T150000Z
DTEND:20120329T153000Z
UID:TALK37158@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Techniques that could resolve P vs. NP are considerably restri
 cted by well-known barriers in computational complexity. There are several
  corresponding results in logic stating that certain fragments of arithmet
 ic are not sufficiently strong to prove that P differs from NP or some sim
 ilar conjectures. We investigate possible extensions of these barriers to 
 stronger\ntheories.  Mainly\, Razborov's conjecture about hardness of Nisa
 n-Wigderson generators for Extended Frege systems and natural proofs in pr
 oof systems admitting feasible disjunction property pointed out by Rudich.
 \n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR