Upper bounds for the formula size of symmetric Boolean functions

DOI10.3103/S1066369X14050041zbMath1351.94099MaRDI QIDQ465106

Igor S. Sergeev

Publication date: 31 October 2014

Published in: Russian Mathematics (Search for Journal in Brave)

zbMATH Keywords

multiplicationsymmetric Boolean functionsmajority functionformula size

Mathematics Subject Classification ID

Boolean functions (06E30)

Related Items (3)

Complexity and depth of formulas for symmetric Boolean functions ⋮ Upper bounds for the size and the depth of formulae for MOD-functions ⋮ Formula complexity of a linear function in a \(k\)-ary basis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• New upper bounds on the Boolean circuit complexity of symmetric functions
• The complexity of the realization of symmetrical functions by formulae
• Shallow circuits and concise formulae for multiple addition and multiplication
• $\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas
• On the combinational complexity of certain symmetric Boolean functions

This page was built for publication: Upper bounds for the formula size of symmetric Boolean functions