Shallow circuits and concise formulae for multiple addition and multiplication

DOI10.1007/BF01271371zbMath0801.68092OpenAlexW2094817392MaRDI QIDQ1312182

Uri Zwick, Michael S. Paterson

Publication date: 29 November 1994

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01271371

zbMATH Keywords

Boolean functionscircuitsmultiplicationformulaecarry-save addition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Boolean functions (06E30)

Related Items (6)

Upper bounds on the depth of symmetric Boolean functions ⋮ Complexity of computation in finite fields ⋮ On the depth complexity of the counting functions ⋮ Upper bounds for the formula size of symmetric Boolean functions ⋮ ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO ⋮ Unnamed Item

Cites Work

• $\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas
• On the Addition of Binary Numbers
• Majority Gate Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Shallow circuits and concise formulae for multiple addition and multiplication