On the complexity of slice functions

DOI10.1016/0304-3975(85)90209-9zbMath0578.94031OpenAlexW2054417980MaRDI QIDQ1066866

Ingo Wegener

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90209-9

zbMATH Keywords

efficient algorithmsBoolean circuitsmonotone circuit complexityrelations between complexity measures

Mathematics Subject Classification ID

Related Items (6)

More on the complexity of slice functions ⋮ The complexity of central slice functions ⋮ \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice ⋮ On monotone simulations on nonmonotone networks ⋮ On the mystery of negations in circuits: structure vs power ⋮ The conjunctive complexity of quadratic Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Monotone switching circuits and Boolean matrix product
• An n3/2 lower bound on the monotone network complexity of the Boolean convolution
• The complexity of monotone boolean functions
• Negation is Powerless for Boolean Slice Functions

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