BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Toda's theorem in bounded arithmetic with parity quantifiers and b
 ounded depth proof systems with parity gates - Kolodziejczyk\, L (Uniwersy
 tet Warszawski)
DTSTART:20120329T100000Z
DTEND:20120329T103000Z
UID:TALK37156@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:The "first part" of Toda's theorem states that every language 
 in the polynomial hierarchy is probabilistically reducible to a language i
 n $oplus P$. The result also holds for the closure of the polynomial hiera
 rchy under a parity quantifier. \n\nWe use Jerabek's framework for approxi
 mate counting to show that this part of Toda's theorem is provable in a re
 latively weak fragment of bounded arithmetic with a parity quantifier. We 
 discuss the significance of the relativized version of this result for bou
 nded depth propositional proof systems with parity gates. \n\nJoint work w
 ith Sam Buss and Konrad Zdanowski.\n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR