Constructions of depth-2 majority circuits for comparison and addition using linear block codes

Noga Alon, Jehoshua Bruck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The authors address the problem of computing the COMPARISON and ADDITION functions of two n-bit numbers using circuits of nonmonotone) MAJORITY gates. Given n Boolean variables as indicated, a nonmonotone MAJORITY gate is a Boolean function whose value is the given sign. We construct an explicit sparse polynomial whose sign computes the COMPARISON function of two integers. Similar polynomials are constructed for computing all the bits of the summation of the two integers. A crucial ingredient in our approach is the construction of a discrete version of a sparse ″delta polynomial″. WE construct sparse delta polynomials using generators matrices of certain linear block codes.

Original languageEnglish (US)
Title of host publicationProceedings of the 1993 IEEE International Symposium on Information Theory
PublisherPubl by IEEE
Number of pages1
ISBN (Print)0780308786
StatePublished - Jan 1 1993
Externally publishedYes
EventProceedings of the 1993 IEEE International Symposium on Information Theory - San Antonio, TX, USA
Duration: Jan 17 1993Jan 22 1993

Publication series

NameProceedings of the 1993 IEEE International Symposium on Information Theory

Other

OtherProceedings of the 1993 IEEE International Symposium on Information Theory
CitySan Antonio, TX, USA
Period1/17/931/22/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Constructions of depth-2 majority circuits for comparison and addition using linear block codes'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Bruck, J. (1993). Constructions of depth-2 majority circuits for comparison and addition using linear block codes. In Proceedings of the 1993 IEEE International Symposium on Information Theory (Proceedings of the 1993 IEEE International Symposium on Information Theory). Publ by IEEE.