Monotone Circuits for the Majority Function

DOI10.1007/11830924_38zbMath1155.68572OpenAlexW1607875726MaRDI QIDQ3595404

Avner Magen, Shlomo Hoory, 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)

Related Items (7)

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}\) ⋮ Expander graphs and their applications ⋮ Strengthening convex relaxations of 0/1-sets using Boolean formulas ⋮ Adaptively secure distributed PRFs from \(\mathsf{LWE}\) ⋮ Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings

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