Breaking the rectangle bound barrier against formula size lower bounds

DOI10.1007/978-3-642-15155-2_58MaRDI QIDQ3586121zbMATH OpenOpenAlexFDO

Authors Kenya Ueno

Publication date 3 September 2010

Published in Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15155-2_58

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Breaking the rectangle bound barrier against formula size lower bounds
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
• A stronger LP bound for formula size lower bounds via clique constraints
• A New Rank Technique for Formula Size Lower Bounds
• A note on the quasi-additive bound for Boolean functions

Cited in

(5)

• A note on the quasi-additive bound for Boolean functions
• A stronger LP bound for formula size lower bounds via clique constraints
• Average-case lower bounds for formula size
• Breaking the rectangle bound barrier against formula size lower bounds
• A New Rank Technique for Formula Size Lower Bounds

This page was built for publication: Breaking the rectangle bound barrier against formula size lower bounds

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