On the complexity of slice functions

DOI10.1016/0304-3975(85)90209-9MaRDI QIDQ1066866zbMATH OpenOpenAlexFDO

Authors 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

Boolean circuitsefficient algorithmsmonotone circuit complexityrelations between complexity measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

By results of Razborov negations can be very powerful for Boolean circuits. But for the class of slice functions negations are almost powerless. Hence each hard function has a hard slice. Lower bounds on the monotone circuit complexity of slice functions imply lower bounds on the circuit complexity of these functions. The structure of slice functions is investigated and efficient algorithms for some slice functions are presented.

Recommendations

• scientific article; zbMATH DE number 3889430
• More on the complexity of slice functions
• The complexity of central slice functions
• Graph complexity and slice functions
• scientific article; zbMATH DE number 2006645
• The slice map problem and approximation properties
• On the computational complexity of cut-reduction
• Techniques and applications of computation slicing
• scientific article; zbMATH DE number 3979140
• scientific article; zbMATH DE number 1574595

Cites work

• An n3/2 lower bound on the monotone network complexity of the Boolean convolution
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 3387244 (Why is no real title available?)
• Monotone switching circuits and Boolean matrix product
• Negation is Powerless for Boolean Slice Functions
• Sorting in \(c \log n\) parallel steps
• The complexity of monotone boolean functions

Cited in

(10)

• More on the complexity of slice functions
• The complexity of central slice functions
• On monotone simulations on nonmonotone networks
• The slice map problem and approximation properties
• Graph complexity and slice functions
• \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
• On the mystery of negations in circuits: structure vs power
• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• Negation is Powerless for Boolean Slice Functions
• The conjunctive complexity of quadratic Boolean functions

This page was built for publication: 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 Q1066866)