# Majority

## Definition

A function $f:\{-1,1\}^n \to \{-1,1\}$ is called a majority function if $f(x)$ returns the most common bit in the input:

 $f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 0 \\ -1 & otherwise \end{cases}$

For even $n$, the above definition breaks ties in favor of 1, although any arbitrary rule may be used instead.

Majority is a special case of the perceptron function.

## Properties

• Among all monotone functions, majority has the largest influence: $\mathrm{Inf}(f) \leq \mathrm{Inf}(\mathrm{Maj})$ for all monotone $f$ [1].
• TODO: a description of Majority's Fourier Transform. See http://www.contrib.andrew.cmu.edu/~ryanod/?p=877 for details.
• Majority is the unique function that is symmetric, monotone and odd function. TODO May's theorem, credit.
• Majority is not in AC0, even if we allow using mod q functions as gates for prime $q$. [2]
• For every $\varepsilon \gt 0$, Majority can be $\varepsilon$-approximated by a DNF of size $2^{O(\sqrt{n})}$. [3]

## References

1. Ryan O'Donnell, Analysis of Boolean functions, Theorem 32 in section 2.3
2. A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (Russian), in Matematicheskie Zametki, Vol. 41, No 4, 1987, pages 598-607. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.
3. O’Donnell R., Wimmer K. (2007) | Approximation by DNF: Examples and Counterexamples. In: Arge L., Cachin C., Jurdziński T., Tarlecki A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg