Lower estimates of circuit complexity in the basis of antichain functions

DOI10.3103/S0027132213020046zbMATH Open1298.68104OpenAlexW1975727709MaRDI QIDQ355314FDOQ355314

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

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

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)

Cites Work

• Additive combinatorics
• On the complexity of schemes in an infinite basis
• Title not available (Why is that?)

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)