A New Rank Technique for Formula Size Lower Bounds
From MaRDI portal
Publication:3590928
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
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)
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Smallest formulas for the parity of \(2^k\) variables are essentially unique
- 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
- Breaking the rectangle bound barrier against formula size lower bounds
- 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)
