Majority

Definition

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

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

For even [math]n[/math], 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: [math]\mathrm{Inf}(f) \leq \mathrm{Inf}(\mathrm{Maj})[/math] for all monotone [math]f[/math] ..
• 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 AC⁰, even if we allow using mod q functions as gates for prime [math]q[/math].
• For every [math]\varepsilon \gt 0 [/math], Majority can be [math]\varepsilon[/math]-approximated by a DNF of size [math]2^{O(\sqrt{n})}[/math].