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].

Promise Majority

Closely associated with the majority function is the promise majority, or approximate majority problem. This is the promise version of the majority problem where the input is promised to either have at least [math]1 + \epsilon[/math] fraction of input bits one, or at most [math]1 - \epsilon[/math] fraction of input bits one.

We say a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] solves the [math]\epsilon[/math]-approximate majority problem if:

[math] f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 2 n \epsilon \\ -1 & if ~ \sum_i x_i \leq - 2 n \epsilon \\ 1 \text{ or } -1 & otherwise \end{cases} [/math]

A randomized AC0 circuit with depth d can solve [math]\frac{1}{\ln(n)^{d-1}}[/math]-approximate majority, but no depth d+1 deterministic AC0 or depth d deterministic AC0[[math]\oplus[/math]] .