Computing Boolean functions by polynomials and threshold circuits (Q1293360)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1309693
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Computing Boolean functions by polynomials and threshold circuits |
scientific article; zbMATH DE number 1309693 |
Statements
Computing Boolean functions by polynomials and threshold circuits (English)
0 references
17 April 2000
0 references
The authors investigate the computational complexity of threshold circuits for Boolean functions. A function with small size unbounded weight threshold-AND circuits is presented for which all threshold-XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. The authors also show that unbounded weight threshold gates cannot simulate alternation. Three open problems are formulated.
0 references
polynomial representation
0 references
computational complexity
0 references
threshold circuits
0 references
Boolean functions
0 references
0.8202847242355347
0 references
0.8121281266212463
0 references
