Lower estimates of circuit complexity in the basis of antichain functions

DOI10.3103/S0027132213020046MaRDI QIDQ355314zbMATH OpenOpenAlexFDO

Authors Olga V. Podolskaya

Publication date 24 July 2013

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s0027132213020046

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Combinatorial probability (60C99)

Recommendations

• Circuit complexity of symmetric Boolean functions in antichain basis
• Complexity of linear and majority functions in the basis of antichain functions
• On the complexity of circuit realization of Boolean functions in an infinite basis
• On the complexity of schemes in an infinite basis
• On the complexity of realization of the linear function by formulas over finite Boolean bases

Cites work

• scientific article; zbMATH DE number 850321 (Why is no real title available?)
• Additive combinatorics
• On the complexity of schemes in an infinite basis

Cited in

(3)

• Circuit complexity of symmetric Boolean functions in antichain basis
• Complexity of linear and majority functions in the basis of antichain functions
• On the complexity of circuit realization of Boolean functions in an infinite basis

This page was built for publication: Lower estimates of circuit complexity in the basis of antichain functions

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