scientific article; zbMATH DE number 1114021

MaRDI QIDQ4375790zbMATH OpenFDO

Authors Xudong Fu

Publication date 8 July 1998

zbMATH Keywords

length of cutting planes proof systemslower boundmodular coloring principlesperfect matchingsize of monotone Boolean circuits

Mathematics Subject Classification ID

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

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

(7)

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

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)