On the complexity of restrictions of Boolean functions

DOI10.1515/DMA.1996.6.3.257MaRDI QIDQ3125953zbMATH OpenOpenAlexFDO

Authors A. V. Chashkin

Publication date 23 March 1997

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma.1996.6.3.257

zbMATH Keywords

Boolean circuitslower bounds on the complexityswitching circuits

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• Lower bounds for the complexity of restrictions of Boolean functions
• On estimates on the complexity of restrictions of Boolean functions
• scientific article; zbMATH DE number 4187721
• scientific article; zbMATH DE number 4012495
• Stochastic Algorithms: Foundations and Applications

Cited in

(29)

• On the computational complexity of some classical equivalence relations on boolean functions
• On estimates on the complexity of restrictions of Boolean functions
• On the complexity of balanced Boolean functions
• Complexity of activity tests for partial Boolean functions
• Critical properties and complexity measures of read-once Boolean functions
• On a hierarchy of Boolean functions hard to compute in constant depth
• On the complexity of the evaluation of transient extensions of Boolean functions
• On the positive and the inversion complexity of Boolean functions
• scientific article; zbMATH DE number 3868606 (Why is no real title available?)
• scientific article; zbMATH DE number 4204280 (Why is no real title available?)
• On the complexity of Boolean functions with small number of ones
• Complexity Based on Partitioning of Boolean Circuits and their Relation to Multivalued Circuits
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• A complexity theory based on Boolean algebra
• scientific article; zbMATH DE number 176868 (Why is no real title available?)
• scientific article; zbMATH DE number 1222848 (Why is no real title available?)
• On the complexity and depth of circuits that realize partial Boolean functions
• Local complexity of Boolean functions
• On domains completely specifying Boolean functions
• scientific article; zbMATH DE number 2174392 (Why is no real title available?)
• On inherited properties of restricted Boolean functions
• scientific article; zbMATH DE number 2123423 (Why is no real title available?)
• scientific article; zbMATH DE number 7310075 (Why is no real title available?)
• Local restrictions from the Furst-Saxe-Sipser paper
• Book review of: S. Jukna, Boolean function complexity. Advances and frontiers.
• Lower bounds for the complexity of restrictions of Boolean functions
• The complexity of Boolean functions in different characteristics
• On the computational power of Boolean decision lists
• On the parity complexity measures of Boolean functions

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

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