A note on the quasi-additive bound for Boolean functions

zbMATH Open1302.90263MaRDI QIDQ2935596FDOQ2935596

Authors: Naoyuki Kamiyama 

Publication date: 30 December 2014

Recommendations

• Breaking the rectangle bound barrier against formula size lower bounds
• 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 \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function

zbMATH Keywords

computational complexityBoolean function complexityprotocol partition number

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60)

Cited In (4)

• Bounds for the number of Boolean functions admitting quadratic approximations of given accuracy
• Breaking the rectangle bound barrier against formula size lower bounds
• Breaking the rectangle bound barrier against formula size lower bounds
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory

This page was built for publication: A note on the quasi-additive bound for Boolean functions

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