Using amplification to compute majority with small majority gates

DOI10.1007/BF01202041zbMATH Open0870.68064MaRDI QIDQ677991FDOQ677991

Authors: Arvind Kumar Gupta, Sanjeev Mahajan 

Publication date: 7 September 1997

Published in: Computational Complexity (Search for Journal in Brave)

Recommendations

• Amplification by Read-Once Formulas
• Short monotone formulae for the majority function
• Computing majority by constant depth majority circuits with low fan-in gates
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one

zbMATH Keywords

amplification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Reliable circuits using less reliable relays
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Short monotone formulae for the majority function
• Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
• Amplification and percolation (probabilistic Boolean functions)

Cited In (9)

• A characteristic polynomial
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Formula complexity of a linear function in a \(k\)-ary basis
• On the complexity of the clone membership problem
• Associative and commutative tree representations for Boolean functions
• The fraction of large random trees representing a given Boolean function in implicational logic
• Complexity and Limiting Ratio of Boolean Functions over Implication
• Short monotone formulae for the majority function
• Computing majority by constant depth majority circuits with low fan-in gates

This page was built for publication: Using amplification to compute majority with small majority gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q677991)