Local complexity of Boolean functions

DOI10.1016/S0166-218X(02)00294-9MaRDI QIDQ4443562zbMATH OpenFDO

Authors A. V. Chashkin

Publication date 15 January 2004

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(02)00294-9

zbMATH Keywords

complexityBoolean circuitsBoolean functionsswiching circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 4012495
• scientific article; zbMATH DE number 176868
• On complexity of a particular Boolean functions class
• Approximation of Boolean functions by local search
• Computational complexity of Boolean functions
• On the multiplicative complexity of Boolean functions
• scientific article; zbMATH DE number 4108153
• scientific article; zbMATH DE number 3987204
• On the complexity of restrictions of Boolean functions
• scientific article; zbMATH DE number 4025336

Cites work

• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 51644 (Why is no real title available?)
• Lower bounds for the complexity of restrictions of Boolean functions
• On estimates on the complexity of restrictions of Boolean functions

Cited in

(4)

• scientific article; zbMATH DE number 4025336 (Why is no real title available?)
• Approximation of Boolean functions by local search
• Local restrictions from the Furst-Saxe-Sipser paper
• scientific article; zbMATH DE number 3987204 (Why is no real title available?)

This page was built for publication: Local complexity of Boolean functions

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