Monotone Circuits for the Majority Function

DOI10.1007/11830924_38zbMATH Open1155.68572OpenAlexW1607875726MaRDI QIDQ3595404FDOQ3595404

Authors: Shlomo Hoory, Avner Magen, Toniann Pitassi 

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11830924_38

Recommendations

• Threshold functions and bounded depth monotone circuits
• Efficient monotone circuits for threshold functions
• Short monotone formulae for the majority function
• Addition is exponentially harder than counting for shallow monotone circuits
• Computing majority by constant depth majority circuits with low fan-in gates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cited In (10)

• Adaptively secure distributed PRFs from \(\mathsf{LWE}\)
• Threshold functions and bounded depth monotone circuits
• Adaptively secure distributed PRFs from LWE
• A hierarchy theorem for interactive proofs of proximity
• Threshold linearly homomorphic encryption on \(\mathrm{Z}/2^k\mathrm{Z}\)
• Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings
• Strengthening convex relaxations of 0/1-sets using Boolean formulas
• Optimal explicit small-depth formulas for the coin problem
• Expander graphs and their applications
• Short monotone formulae for the majority function

This page was built for publication: Monotone Circuits for the Majority Function

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