BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Proof Complexity of Paris-Harrington Tautologies - Galesi\, N (Uni
 versit degli Studi di Roma La Sapienza)
DTSTART:20120326T100000Z
DTEND:20120326T103000Z
UID:TALK37096@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We study the proof complexity of Paris-Harringtons Large Ramse
 y Theorem for bicolorings of graphs. We prove a conditional lower bound in
  Resolution and a upper bound in bounded-depth Frege. The lower bound is c
 onditional on a (very reasonable) hardness assumption for a weak (quasi-po
 lynomial) Pigeonhole principle in Res(2). We show that under such assumpti
 on\, there is no refutation of the Paris-Harrington formulas of size quasi
 -polynomial in the number of propositional variables. The proof technique 
 for the lower bound extends the idea of using a combinatorial principle to
  blow-up a counterexample for another combinatorial principle beyond the t
 hreshold of inconsistency. A strong link with the proof complexity of an u
 nbalanced Ramsey principle for triangles is established. This is obtained 
 by adapting some constructions due to Erdo ̋s and Mills.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR