[Proof Complexity] Paper available (Frankl Theorem)

[Sam Buss]

Dear proof complexity mailing list,

James Aisenberg, Maria Luisa Bonet and I have a preprint "Quasipolynomial
Size Frege Proofs of Frankl's Theorem on the Trace of Sets", available at
http://www.math.ucsd.edu/~sbuss/ResearchWeb/Frankl_Tthree/.

Comments, suggestions, corrections are appreciated.

Best regards, Sam

====
Abstract: We extend results of Bonet, Buss and Pitassi on Bondy's Theorem
and of Nozaki, Arai and Arai on Bollob\'as' Theorem by proving that Frankl's
Theorem on the trace of sets has quasipolynomial size Frege proofs.  For
constant values of the parameter~$t$,  we prove that Frankl's Theorem has
polynomial size $\AC^0$-Frege proofs from instances of the pigeonhole
principle.