A New Rank Technique for Formula Size Lower Bounds

DOI10.1007/978-3-540-70918-3_13zbMATH Open1186.68211OpenAlexW1857141208MaRDI QIDQ3590928FDOQ3590928

Authors Troy Lee

Publication date 3 September 2007

Published in STACS 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70918-3_13

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
• A stronger LP bound for formula size lower bounds via clique constraints
• Breaking the rectangle bound barrier against formula size lower bounds
• The effect of random restrictions on formula size
• A Lower Bound for the Formula Size of Rational Functions

Cited in

(12)

• Average-case lower bounds for formula size
• Improvements on Khrapchenko's theorem
• Breaking the rectangle bound barrier against formula size lower bounds
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• A stronger LP bound for formula size lower bounds via clique constraints
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Complexity of the realization of a linear Boolean function in the class of \(\pi\)-schemes
• Breaking the rectangle bound barrier against formula size lower bounds
• On convex complexity measures

This page was built for publication: A New Rank Technique for Formula Size Lower Bounds

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