Circuit complexity of symmetric Boolean functions in antichain basis

DOI10.1515/DMA-2016-0003zbMATH Open1347.94081arXiv1410.2456OpenAlexW2340850974MaRDI QIDQ314174FDOQ314174

Authors: Olga V. Podolskaya 

Publication date: 13 September 2016

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

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.$

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

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

zbMATH Keywords

Boolean circuitsShannon functionsymmetric Boolean functionsantichain functionsBoolean circuit complexity

Mathematics Subject Classification ID

Cites Work

• On the complexity of schemes in an infinite basis
• Circuit complexity of symmetric Boolean functions in antichain basis
• Title not available (Why is that?)

Cited In (10)

• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• Title not available (Why is that?)
• 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)