Complexity and depth of formulas for symmetric Boolean functions

DOI10.3103/S0027132216030098MaRDI QIDQ334301zbMATH OpenFDO

Authors I. S. Sergeev

Publication date 1 November 2016

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• Upper bounds on the depth of symmetric Boolean functions
• Upper bounds for the formula size of symmetric Boolean functions
• scientific article; zbMATH DE number 3968581
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Upper bounds on the multiplicative complexity of symmetric Boolean functions

Cites work

• scientific article; zbMATH DE number 3644976 (Why is no real title available?)
• scientific article; zbMATH DE number 176877 (Why is no real title available?)
• Efficient oblivious branching programs for threshold and mod functions
• Short monotone formulae for the majority function
• The complexity of the realization of symmetrical functions by formulae
• Upper bounds for the formula size of symmetric Boolean functions
• Upper bounds on the depth of symmetric Boolean functions

Cited in

(8)

• scientific article; zbMATH DE number 4035741 (Why is no real title available?)
• Multiplication
• scientific article; zbMATH DE number 3968581 (Why is no real title available?)
• Formula complexity of a linear function in a \(k\)-ary basis
• Cubic Formula Size Lower Bounds Based on Compositions with Majority
• On the meaning of works by V. M. Khrapchenko
• Upper bounds for the formula size of symmetric Boolean functions
• Upper bounds on the depth of symmetric Boolean functions

This page was built for publication: Complexity and depth of formulas for symmetric Boolean functions

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