On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates

DOI10.1515/DMA-2019-0022MaRDI QIDQ2332856zbMATH OpenOpenAlexFDO

Authors I. S. Sergeev

Publication date 5 November 2019

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

Full work available at URL https://doi.org/10.1515/dma-2019-0022

zbMATH Keywords

complexitybounded-depth circuitsBoolean cube partitions

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• Multilevel representation and complexity of circuits of unbounded fan-in gates
• Complexity of Boolean functions over bases with unbounded fan-in gates
• On the depth of Boolean functions over an arbitrary infinite basis
• On the synthesis and complexity of formulae with bounded depth of alternation
• On the complexity of realizing the powers of a Boolean \((n,n)\)-function

Cites work

• scientific article; zbMATH DE number 4172917 (Why is no real title available?)
• scientific article; zbMATH DE number 3121508 (Why is no real title available?)
• scientific article; zbMATH DE number 3961508 (Why is no real title available?)
• scientific article; zbMATH DE number 850396 (Why is no real title available?)
• scientific article; zbMATH DE number 3285248 (Why is no real title available?)
• scientific article; zbMATH DE number 3319974 (Why is no real title available?)
• scientific article; zbMATH DE number 3348015 (Why is no real title available?)
• scientific article; zbMATH DE number 3419055 (Why is no real title available?)
• Asymmetric binary covering codes.
• Boolean function complexity. Advances and frontiers.
• Complexity Theory
• Complexity of Boolean functions over bases with unbounded fan-in gates
• General upper bound of circuit complexity in an arbitrary infinite complete base
• On the synthesis and complexity of formulae with bounded depth of alternation

Cited in

(20)

• The complexity of the parity function in unbounded fan-in, unbounded depth circuits
• High-accuracy bounds of the Shannon function for formula complexity in bases with direct and iterative variables
• scientific article; zbMATH DE number 3912286 (Why is no real title available?)
• On the synthesis and complexity of formulae with bounded depth of alternation
• Multilevel representation and complexity of circuits of unbounded fan-in gates
• An improved complexity hierarchy on the depth of Boolean functions
• The complexity of depth-two information networks
• On circuits of functional elements of finite depth of branching
• On the depth of the storage access function
• Asymptotically best synthesis methods for reflexive-recursive circuits
• Depth lower bounds for monotone semi-unbounded fan-in circuits.
• On the complexity of realizing the powers of a Boolean \((n,n)\)-function
• scientific article; zbMATH DE number 89639 (Why is no real title available?)
• scientific article; zbMATH DE number 3841817 (Why is no real title available?)
• Computing majority by constant depth majority circuits with low fan-in gates
• On the depth complexity of the counting functions
• Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
• On the depth of Boolean functions over an arbitrary infinite basis
• Rectifier circuits of bounded depth
• scientific article; zbMATH DE number 4095383 (Why is no real title available?)

This page was built for publication: On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates

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