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

DOI10.1515/dma-2019-0022zbMath1439.94116OpenAlexW2968036895MaRDI QIDQ2332856

Igor 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)

Related Items (2)

Asymptotically best synthesis methods for reflexive-recursive circuits ⋮ Multilevel representation and complexity of circuits of unbounded fan-in gates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• General upper bound of circuit complexity in an arbitrary infinite complete base
• Complexity of Boolean functions over bases with unbounded fan-in gates
• On the synthesis and complexity of formulae with bounded depth of alternation
• Asymmetric binary covering codes.
• Complexity Theory

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