Circuit complexity of symmetric Boolean functions in antichain basis

DOI10.1515/DMA-2016-0003MaRDI QIDQ314174zbMATH OpenOpenAlexFDO

Authors Olga V. Podolskaya

Publication date 13 September 2016

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

Full work available at URL https://arxiv.org/abs/1410.2456

zbMATH Keywords

Boolean circuitsShannon functionsymmetric Boolean functionsantichain functionsBoolean circuit complexity

Mathematics Subject Classification ID

Abstract: We study the circuit complexity of boolean functions in a certain infinite basis. The basis consists of all functions that take value $1$ on antichains over the boolean cube. We prove that the circuit complexity of the parity function and the majority function of $n$ variables in this basis is $lfloorfracn+12floor$ and $leftlfloorfracn2ightfloor+1$ respectively. We show that the asymptotic of the maximum complexity of $n$-variable boolean functions in this basis equals $n.$

Recommendations

• Complexity of linear and majority functions in the basis of antichain functions
• Lower estimates of circuit complexity in the basis of antichain functions
• On the complexity of circuit realization of Boolean functions in an infinite basis
• Publication:4888933
• scientific article; zbMATH DE number 4035741

Cites work

• scientific article; zbMATH DE number 850321 (Why is no real title available?)
• Circuit complexity of symmetric Boolean functions in antichain basis
• On the complexity of schemes in an infinite basis

Cited in

(10)

• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• scientific article; zbMATH DE number 609985 (Why is no real title available?)
• Lower bound of circuit complexity of parity function in a basis of unbounded fan-in
• Circuit complexity of symmetric Boolean functions in antichain basis
• On the complexity of multivalued logic functions over some infinite basis
• Lower estimates of circuit complexity in the basis of antichain functions
• Bit complexity of breaking and achieving symmetry in chains and rings
• 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
• Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates

This page was built for publication: Circuit complexity of symmetric Boolean functions in antichain basis

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