COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Proof Complexity of Paris-Harrington Tautologies

## Proof Complexity of Paris-Harrington TautologiesAdd to your list(s) Download to your calendar using vCal - Galesi, N (Universit degli Studi di Roma La Sapienza)
- Monday 26 March 2012, 11:00-11:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing We study the proof complexity of Paris-Harringtons Large Ramsey 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 conditional on a (very reasonable) hardness assumption for a weak (quasi-polynomial) Pigeonhole principle in Res(2). We show that under such assumption, 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 threshold of inconsistency. A strong link with the proof complexity of an unbalanced Ramsey principle for triangles is established. This is obtained by adapting some constructions due to Erdo ̋s and Mills. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsFirst Intestinal Epithelial Research Symposium Giving What We Can: Cambridge Mineral Sciences Seminars## Other talksMigration in Science Modelling mitochondrial dysfunction in Parkinson’s disease: mitophagy, calcium and beyond Babraham Lecture - Understanding how the p53 onco-suppressor gene works: hints from the P2X7 ATP receptor Predictive modeling of hydrogen assisted cracking – a Micromechanics conquest Primary liver tumor organoids: a new pre-clinical model for drug sensitivity analysis Cambridge-Lausanne Workshop 2018 - Day 2 Café Synthetique: Graduate Talks! Computing High Resolution Health(care) Glucagon like peptide-1 receptor - a possible role for beta cell physiology in susceptibility to autoimmune diabetes Single Cell Seminars (November) |