Quasipolynomial size Frege proofs of frankl’s theorem on the trace of sets

Journal of Symbolic Logic 81 (2):687-710 (2016)
  Copy   BIBTEX

Abstract

We extend results of Bonet, Buss and Pitassi on Bondy’s Theorem and of Nozaki, Arai and Arai on Bollobás’ Theorem by proving that Frankl’s Theorem on the trace of sets has quasipolynomial size Frege proofs. For constant values of the parametert, we prove that Frankl’s Theorem has polynomial size AC0-Frege proofs from instances of the pigeonhole principle.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,509

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Propositional Consistency Proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
A Note on Propositional Proof Complexity of Some Ramsey-Type Statements.Jan Krajíček - 2011 - Archive for Mathematical Logic 50 (1-2):245-255.
Matrix Identities and the Pigeonhole Principle.Michael Soltys & Alasdair Urquhart - 2004 - Archive for Mathematical Logic 43 (3):351-357.
The Translation Theorem.Peter Cholak - 1994 - Archive for Mathematical Logic 33 (2):87-108.
Monotone Proofs of the Pigeon Hole Principle.R. Gavalda, A. Atserias & N. Galesi - 2001 - Mathematical Logic Quarterly 47 (4):461-474.
Some Remarks on Lengths of Propositional Proofs.Samuel R. Buss - 1995 - Archive for Mathematical Logic 34 (6):377-394.
Other Proofs of Old Results.Henryk Kotlarski - 1998 - Mathematical Logic Quarterly 44 (4):474-480.
Frege's Result: Frege's Theorem and Related Matters.Hirotoshi Tabata - 2012 - Frontiers of Philosophy in China 7 (3):351-366.
Extension Without Cut.Lutz Straßburger - 2012 - Annals of Pure and Applied Logic 163 (12):1995-2007.
Cutting Planes, Connectivity, and Threshold Logic.Samuel R. Buss & Peter Clote - 1996 - Archive for Mathematical Logic 35 (1):33-62.

Analytics

Added to PP
2016-06-30

Downloads
20 (#559,181)

6 months
1 (#417,896)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Propositional Consistency Proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.

Add more references