When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
type: Item
instance of: scholarly article
title: When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
zbMATH Open document ID: 0829.68058
DOI: 10.1007/BF01263420
published in: Computational Complexity
publication date: 1995-04-06T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 741029
zbMATH Keywords: threshold-gate
zbMATH Keywords: symmetric gate
zbMATH Keywords: Boolean function
author: Richard Beigel
MaRDI profile type: Publication
cites work: Depth reduction for circuits of unbounded fan-in
cites work: Some connections between bounded query classes and non-uniform complexity.
cites work: The expressive power of voting polynomials
cites work: Random oracles separate PSPACE from the polynomial-time hierarchy
cites work: On ACC
cites work: PP is closed under intersection
cites work: With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
cites work: PP is closed under truth-table reductions
cites work: Rational approximation to \(|x|\)
cites work: Approximating threshold circuits by rational functions
cites work: Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
Recommended article: Majority gates vs. general weighted threshold gates
Recommended article: Q4016932
Recommended article: Using amplification to compute majority with small majority gates
Recommended article: A note on the power of majority gates and modular gates
Recommended article: Q3400478
Recommended article: Q4281556
Recommended article: Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
Recommended article: Computing majority by constant depth majority circuits with low fan-in gates
Recommended article: Algorithms and Computation
Recommended article: Q5414574
description: scientific article; zbMATH DE number 741029