Monotone Circuits for the Majority Function

DOI10.1007/11830924_38MaRDI QIDQ3595404zbMATHOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(11)

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