A New Rank Technique for Formula Size Lower Bounds

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

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)

Cited In (10)

• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• A stronger LP bound for formula size lower bounds via clique constraints
• Improvements on Khrapchenko's theorem
• Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory
• BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS
• On convex complexity measures
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Average-case lower bounds for formula size
• Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

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)