On the combinational complexity of certain symmetric Boolean functions

DOI10.1007/BF01683282MaRDI QIDQ4146674zbMATH OpenOpenAlexFDO

Authors Larry J. Stockmeyer

Publication date 1977

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01683282

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• Lower bounds to the complexity of symmetric Boolean functions
• Upper bounds on the multiplicative complexity of symmetric Boolean functions
• scientific article; zbMATH DE number 4035741
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).

Cites work

• A class of Boolean functions with linear combinational complexity
• Bounds to Complexities of Networks for Sorting and for Switching
• Computational Work and Time on Finite Machines
• The combinational complexity of equivalence
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(29)

• Models of lower-bounds proofs
• A 3n-lower bound on the network complexity of Boolean functions
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• On the complexity of balanced Boolean functions
• On the limits of gate elimination
• Properties of symmetric Boolean functions
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Periodic Boolean functions and a lower bound for the complexity of operators
• \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
• Feebly secure cryptographic primitives
• Circuit complexity of linear functions: gate elimination and feeble security
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• Timed vacuity
• On the complexity of monotone circuits for threshold symmetric Boolean functions
• Upper bounds on the multiplicative complexity of symmetric Boolean functions
• New lower bounds on circuit size of multi-output functions
• Gate elimination for linear functions and new feebly secure constructions
• A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• On Negations in Boolean Networks
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• scientific article; zbMATH DE number 4035741 (Why is no real title available?)
• Upper bounds for the formula size of symmetric Boolean functions
• Spanning-tree games
• Flow games
• Improving \(3N\) circuit complexity lower bounds
• A Boolean function requiring 3n network size
• Lower bounds to the complexity of symmetric Boolean functions
• Tight bounds for the multiplicative complexity of symmetric functions
• New upper bounds on the Boolean circuit complexity of symmetric functions

This page was built for publication: On the combinational complexity of certain symmetric Boolean functions

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