Breaking the rectangle bound barrier against formula size lower bounds

DOI10.1007/978-3-642-15155-2_58zbMATH Open1287.68053OpenAlexW1532729668MaRDI QIDQ3586121FDOQ3586121

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

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

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)

Cited In (3)

• A stronger LP bound for formula size lower bounds via clique constraints
• Average-case lower bounds for formula size
• 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)