A note on the quasi-additive bound for Boolean functions

zbMATH Open1302.90263MaRDI QIDQ2935596FDOQ2935596

Authors Naoyuki Kamiyama 

Publication date 30 December 2014

zbMATH Keywords

computational complexityBoolean function complexityprotocol partition number

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60)

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

Cited in

(4)

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

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)