Short monotone formulae for the majority function

1984/09/01 by Leslie G. Valiant, L.G Valiant · 4 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Complexity and Algorithms in Graphs

paper · doi:10.1016/0196-6774(84)90016-6

crossref issued 1984/09/01 · crossref published 1984/09/01 · crossref published-print 1984/09/01 · openalex publication_date 1984/09/01 · crossref created 2005/02/10 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2026/07/24 · openalex updated_date 2026/07/25

Citations

• An 0(n log n) sorting network

Cited by

• Quantum advantage for computations with limited space
• From Discrepancy to Majority
• Thoughts on Noise and Quantum Computation
• Majority function [wikipedia]