Quasipolynomial size frege proofs of Frankl's Theorem on the trace of sets
Visualitza/Obre
Cita com:
hdl:2117/100899
Tipus de documentArticle
Data publicació2016-06-01
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
We extend results of Bonet, Buss and Pitassi on Bondy's Theorem and of Nozaki, Arai and Arai on Bollobas' 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.
CitacióAisenberg, J., Bonet, M., Buss, S. Quasipolynomial size frege proofs of Frankl's Theorem on the trace of sets. "Journal of symbolic logic", 1 Juny 2016, vol. 81, núm. 2, p. 687-710.
ISSN0022-4812
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
paper.pdf | 268,0Kb | Visualitza/Obre |