More on the complexity of slice functions

DOI10.1016/0304-3975(86)90176-3MaRDI QIDQ1079365zbMATH OpenOpenAlexFDO

Authors Ingo Wegener

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90176-3

zbMATH Keywords

Boolean functioncircuit complexitymonotone complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3889430
• On the complexity of slice functions
• Negation is Powerless for Boolean Slice Functions
• The complexity of central slice functions
• On monotone simulations on nonmonotone networks

Cites work

• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 3387244 (Why is no real title available?)
• Lower bounds on monotone complexity of the logical permanent
• Negation is Powerless for Boolean Slice Functions
• On the complexity of slice functions
• Sorting in \(c \log n\) parallel steps

Cited in

(7)

• On the complexity of slice functions
• The complexity of central slice functions
• On monotone simulations on nonmonotone networks
• \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• scientific article; zbMATH DE number 1302031 (Why is no real title available?)
• Negation is Powerless for Boolean Slice Functions

This page was built for publication: More on the complexity of slice functions

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