BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Fragments of approximate counting - Thapen\, N (Academy of Science
 s of the Czech Republic)
DTSTART:20120330T080000Z
DTEND:20120330T090000Z
UID:TALK37192@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We pose the question: are there any simple sentences\, provabl
 e using bounded induction\, that cannot already be proved using approximat
 e counting of simple sets? More precisely\, we study the long-standing ope
 n problem of giving $orall Sigma^b_1$ separations for fragments of bounde
 d arithmetic in the relativized setting\, but rather than considering the 
 usual fragments defined by the amount of induction they allow\, we study J
 erabek's theories for approximate counting and their subtheories. We prove
  separations for some of the subtheories\, and also give new propositional
  translations\, in terms of random resolution refutations\, for the conseq
 uences of $T^1_2$ augmented with a certain weak pigeonhole principle. Join
 t work with Sam Buss and Leszek Kolodziejczyk.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR