[Proof Complexity] Paper available (Frankl Theorem)

Sam Buss sbuss at math.ucsd.edu
Sat Aug 23 01:06:11 CEST 2014

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

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

More information about the Proof-Complexity mailing list