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

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Bruck, Jehoshua Alon, Noga
Copyright Year	1994
Abstract	All Boolean variables here range over the two-element set $\{ - 1,1 \}$. Given n Boolean variables $x_1 , \ldots ,x_n $, a nonmonotone MAJORITY gate (in the variables $x_i $) is a Boolean function whose value is the sign of $\Sigma _{i = 1}^n \varepsilon _i x_i $, where each $ \varepsilon _i $ is either 1 or $ - 1$. The COMPARISON function is the Boolean function of two n-bits integers X and Y whose value is $ - 1$ if and only if $X\geqq Y$. An explicit sparse polynomial whose sign computes this function is constructed. Similar polynomials are constructed for computing all the bits of the summation of the two numbers X and Y. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only nonmonotone MAJORITY gates. These constructions are optimal in terms of the depth and can be used to obtain the best-known explicit constructions of MAJORITY circuits for other functions like the product of two n-bit numbers and the maximum of nn-bit numbers. A crucial ingredient is the construction of a discrete version of a sparse delta polynomialone that has a large absolute value for a single assignment and extremely small absolute values for all other assignments.
Starting Page	1
Ending Page	8
Page Count	8
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480191218496
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	7
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-08
Access Restriction	Subscribed
Subject Keyword	error-correcting codes threshold function majority circuits addition function comparison function Complexity classes
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Constructions of Depth-2 Majority Circuits for Comparison and Addition using Linear Block Codes

Separating ${AC}^0$ from Depth-2 Majority Circuits

Parallel Quantum Computation and Quantum Codes

IP = PSPACE Using Error-Correcting Codes

Size--Depth Tradeoffs for Threshold Circuits

Separating $AC^{0}$ from depth-2 majority circuits

Computational Hardness and Explicit Constructions of Error Correcting Codes

Repetition Error Correcting Sets: Explicit Constructions and Prefixing Methods

New Classes of Codes for Cryptologists and Computer Scientists

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

Similar Documents

Constructions of Depth-2 Majority Circuits for Comparison and Addition using Linear Block Codes

Separating ${AC}^0$ from Depth-2 Majority Circuits

Parallel Quantum Computation and Quantum Codes

IP = PSPACE Using Error-Correcting Codes

Size--Depth Tradeoffs for Threshold Circuits

Separating $AC^{0}$ from depth-2 majority circuits

Computational Hardness and Explicit Constructions of Error Correcting Codes

Repetition Error Correcting Sets: Explicit Constructions and Prefixing Methods

New Classes of Codes for Cryptologists and Computer Scientists

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