Using amplification to compute majority with small majority gates

DOI10.1007/BF01202041MaRDI QIDQ677991zbMATH OpenFDO

Authors Arvind Kumar Gupta, Sanjeev Mahajan

Publication date 7 September 1997

Published in Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

amplification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cites work

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

Cited in

(9)

• Computing majority by constant depth majority circuits with low fan-in gates
• 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

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)