Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition

DOI10.1137/S0895480191218496MaRDI QIDQ4287934zbMATH OpenFDO

Authors Noga Alon, Jehoshua Bruck

Publication date 12 May 1994

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

threshold functioncomparison functionerror-correcting codesmajority circuitsaddition function

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Recommendations

• Addition is exponentially harder than counting for shallow monotone circuits
• A circuit of depth two with limited input branching for majority functions
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• A note on the power of majority gates and modular gates

Cited in

(11)

• Computing majority by constant depth majority circuits with low fan-in gates
• Threshold circuits of small majority-depth
• Addition is exponentially harder than counting for shallow monotone circuits
• Depth-efficient threshold circuits for multiplication and symmetric function computation
• Computing sparse approximations deterministically
• General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
• Majority Adder Implementation by Competing Patterns in Life-Like Rule B2/S2345
• On small depth threshold circuits
• Counting solutions to polynomial systems via reductions
• Decomposition of threshold functions into bounded fan-in threshold functions
• Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky

This page was built for publication: Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition

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