Using amplification to compute majority with small majority gates
From MaRDI portal
Publication:677991
DOI10.1007/BF01202041zbMath0870.68064MaRDI QIDQ677991
Sanjeev Mahajan, Arvind Kumar Gupta
Publication date: 7 September 1997
Published in: Computational Complexity (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
The fraction of large random trees representing a given Boolean function in implicational logic ⋮ A characteristic polynomial ⋮ Complexity and Limiting Ratio of Boolean Functions over Implication ⋮ Formula complexity of a linear function in a \(k\)-ary basis ⋮ Associative and commutative tree representations for Boolean functions ⋮ On the complexity of the clone membership problem
Cites Work
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Short monotone formulae for the majority function
- Amplification and percolation (probabilistic Boolean functions)
- Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
- Reliable circuits using less reliable relays
This page was built for publication: Using amplification to compute majority with small majority gates
