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

DOI10.1515/DMA-2019-0022zbMATH Open1439.94116OpenAlexW2968036895MaRDI QIDQ2332856FDOQ2332856

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

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

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)

Cites Work

• Complexity Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Boolean function complexity. Advances and frontiers.
• Asymmetric binary covering codes.
• General upper bound of circuit complexity in an arbitrary infinite complete base
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of Boolean functions over bases with unbounded fan-in gates
• Title not available (Why is that?)
• On the synthesis and complexity of formulae with bounded depth of alternation
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (20)

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

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)