On the combinational complexity of certain symmetric Boolean functions

DOI10.1007/BF01683282zbMath0369.94016OpenAlexW1989734466MaRDI QIDQ4146674

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)

Related Items

On the limits of gate elimination, \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice, Models of lower-bounds proofs, A 3n-lower bound on the network complexity of Boolean functions, Improving \(3N\) circuit complexity lower bounds, Feebly secure cryptographic primitives, Circuit complexity of linear functions: gate elimination and feeble security, Gate elimination: circuit size lower bounds and \#SAT upper bounds, Tight bounds for the multiplicative complexity of symmetric functions, Upper bounds for the formula size of symmetric Boolean functions, Nonlinear lower bounds on the number of processors of circuits with sublinear separators, On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\)., Spanning-Tree Games., Gate Elimination for Linear Functions and New Feebly Secure Constructions, Timed vacuity, New upper bounds on the Boolean circuit complexity of symmetric functions, On the complexity of monotone circuits for threshold symmetric Boolean functions, On Negations in Boolean Networks, Unnamed Item, A Boolean function requiring 3n network size, New lower bounds on circuit size of multi-output functions

Cites Work

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