Quasipolynomial size Frege proofs of Frankl's theorem on the trace of sets

DOI10.1017/JSL.2015.17MaRDI QIDQ3188337zbMATH OpenOpenAlexWikidataFDO

Authors James Aisenberg, Maria Luisa Bonet, Samuel R. Buss

Publication date 19 August 2016

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/100899

zbMATH Keywords

Kruskal-Katona theoremFrege proofstrace of setsextended Frege proofsFrankl's theoremhereditary matrix

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• scientific article; zbMATH DE number 806744
• Polynomial size proofs of the propositional pigeonhole principle
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Exponential lower bounds for the pigeonhole principle
• Quasipolynomial size proofs of the propositional pigeonhole principle

Cites work

• scientific article; zbMATH DE number 3989345 (Why is no real title available?)
• On the trace of finite sets
• Polynomal-size Frege proofs of Bollobás' theorem on the trace of sets
• Propositional consistency proofs
• The provably total NP search problems of weak second order bounded arithmetic

Cited in

(4)

• Characterizing propositional proofs as noncommutative formulas
• Quasipolynomial size proofs of the propositional pigeonhole principle
• Short proofs of the Kneser-Lovász coloring principle
• Propositional proofs in Frege and extended Frege systems (abstract)

This page was built for publication: Quasipolynomial size Frege proofs of Frankl's theorem on the trace of sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188337)