On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies
From MaRDI portal
Publication:5278196
DOI10.1145/2946801zbMath1407.03073OpenAlexW2518743604WikidataQ61732577 ScholiaQ61732577MaRDI QIDQ5278196
Massimo Lauria, Nicola Galesi, Lorenzo Carlucci
Publication date: 13 July 2017
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11573/902288
Complexity of computation (including implicit computational complexity) (03D15) Generalized Ramsey theory (05C55) Complexity of proofs (03F20)
Cites Work
- Unnamed Item
- A note on propositional proof complexity of some Ramsey-type statements
- Ramsey-Paris-Harrington numbers for graphs
- A note on Ramsey numbers
- Some bounds for the Ramsey-Paris-Harrington numbers
- Rapidly growing Ramsey functions
- Asymptotic lower bounds for Ramsey functions
- Cutting plane and Frege proofs
- Separation results for the size of constant-depth propositional proofs
- On the weak pigeonhole principle
- Graph Theory and Probability. II
- Approximation and Small-Depth Frege Proofs
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Lower bounds to the size of constant-depth propositional proofs
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- The Ramsey number R(3, t) has order of magnitude t2/log t
- Some graph theoretic results associated with Ramsey's theorem
- A new proof of the weak pigeonhole principle
- Concentration of Measure for the Analysis of Randomized Algorithms