Editing Majority function (section)

== Monotone formulae for majority ==

For ''n'' = 1 the median operator is just the unary identity operation ''x''.  For ''n'' = 3 the ternary median operator can be expressed using conjunction and disjunction as ''xy'' + ''yz'' + ''zx''.

For an arbitrary ''n'' there exists a monotone formula for majority of size O(''n''<sup>5.3</sup>). This is proved using [[probabilistic method]]. Thus, this formula is non-constructive.<ref>{{Cite journal | first = Leslie | last = Valiant | author-link = Leslie Valiant | title = Short monotone formulae for the majority function | journal = Journal of Algorithms | volume = 5 | issue = 3 | year = 1984 | pages = 363–366 | doi = 10.1016/0196-6774(84)90016-6}}</ref>

Approaches exist for an explicit formula for majority of polynomial size:
* Take the median from a [[sorting network]], where each compare-and-swap "wire" is simply an OR gate and an AND gate. The [[Miklós Ajtai|Ajtai]]&ndash;[[János Komlós (mathematician)|Komlós]]&ndash;[[Endre Szemerédi|Szemerédi]] (AKS) construction is an example.
* Combine the outputs of smaller majority circuits.<ref>{{cite journal |last1=Amano |first1=Kazuyuki |title=Depth Two Majority Circuits for Majority and List Expanders |journal=43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) |date=2018 |volume=117 |issue=81 |pages=1–13 |doi=10.4230/LIPIcs.MFCS.2018.81 |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik|doi-access=free }}</ref>
* Derandomize the Valiant proof of a monotone formula.<ref>{{cite book |last1=Hoory |first1=Shlomo |last2=Magen |first2=Avner |last3=Pitassi |first3=Toniann |title=Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |chapter=Monotone Circuits for the Majority Function |series=Lecture Notes in Computer Science |date=2006 |volume=4110 |pages=410–425 |doi=10.1007/11830924_38 |chapter-url=https://www.researchgate.net/publication/221462555 |publisher=Springer |isbn=978-3-540-38044-3 |language=en}}</ref>