Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Quasipolynomial size frege proofs of Frankl's Theorem on the trace of sets

Autor
Aisenberg, J.; Bonet, M.; Buss, S.
Tipus d'activitat
Article en revista
Revista
Journal of symbolic logic
Data de publicació
2016-06-01
Volum
81
Número
2
Pàgina inicial
687
Pàgina final
710
DOI
https://doi.org/10.1017/jsl.2015.17 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/100899 Obrir en finestra nova
URL
http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=10382588&fileId=S0022481215000171 Obrir en finestra nova
Resum
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.
Paraules clau
Extended Frege proofs, Frankl's theorem, Frege proofs, Hereditary matrix, Kruskal-Katona theorem, Trace of sets
Grup de recerca
LOGPROG - Lògica i Programació

Participants

Arxius