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

Noga Alon; Jehoshua Bruck

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 proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 1993 IEEE International Symposium on Information Theory
Publisher	Publ by IEEE
Pages	433
Number of pages	1
ISBN (Print)	0780308786
State	Published - 1993
Externally published	Yes
Event	Proceedings of the 1993 IEEE International Symposium on Information Theory - San Antonio, TX, USA Duration: Jan 17 1993 → Jan 22 1993

Publication series

Name	Proceedings of the 1993 IEEE International Symposium on Information Theory

Other

Other	Proceedings of the 1993 IEEE International Symposium on Information Theory
City	San Antonio, TX, USA
Period	1/17/93 → 1/22/93

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@inproceedings{9351d2603f854227bef073df148190be,

title = "Constructions of depth-2 majority circuits for comparison and addition using linear block codes",

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.",

author = "Noga Alon and Jehoshua Bruck",

year = "1993",

language = "English (US)",

isbn = "0780308786",

series = "Proceedings of the 1993 IEEE International Symposium on Information Theory",

publisher = "Publ by IEEE",

pages = "433",

booktitle = "Proceedings of the 1993 IEEE International Symposium on Information Theory",

note = "Proceedings of the 1993 IEEE International Symposium on Information Theory ; Conference date: 17-01-1993 Through 22-01-1993",

}

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, pp. 433, Proceedings of the 1993 IEEE International Symposium on Information Theory, San Antonio, TX, USA, 1/17/93.

Constructions of depth-2 majority circuits for comparison and addition using linear block codes. / Alon, Noga; Bruck, Jehoshua.
Proceedings of the 1993 IEEE International Symposium on Information Theory. Publ by IEEE, 1993. p. 433 (Proceedings of the 1993 IEEE International Symposium on Information Theory).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Alon, Noga

AU - Bruck, Jehoshua

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027221292&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027221292&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027221292

SN - 0780308786

T3 - Proceedings of the 1993 IEEE International Symposium on Information Theory

SP - 433

BT - Proceedings of the 1993 IEEE International Symposium on Information Theory

PB - Publ by IEEE

T2 - Proceedings of the 1993 IEEE International Symposium on Information Theory

Y2 - 17 January 1993 through 22 January 1993

ER -

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this