scientific article; zbMATH DE number 1114021

MaRDI QIDQ4375790zbMATH OpenFDO

Authors Xudong Fu

Publication date 8 July 1998

zbMATH Keywords

lower boundperfect matchinglength of cutting planes proof systemsmodular coloring principlessize of monotone Boolean circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1256779
• A rank lower bound for cutting planes proofs of Ramsey's theorem
• A rank lower bound for cutting planes proofs of Ramsey's theorem
• scientific article; zbMATH DE number 1263234
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds on coloring numbers from hardness hypotheses in pcf theory
• Tight lower bounds for the complexity of multicoloring
• Tight lower bounds for the complexity of multicoloring

Cited in

(5)

• Lower bounds on strip discrepancy for nonatomic colorings
• Lower bounds for cutting planes proofs with small coefficients
• scientific article; zbMATH DE number 1263234 (Why is no real title available?)
• A rank lower bound for cutting planes proofs of Ramsey's theorem
• A rank lower bound for cutting planes proofs of Ramsey's theorem

This page was built for publication:

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