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.
• The majority function is evasive so the decision tree complexity is [math]D(f) = n[/math].
• Majority is not in AC⁰, even if we allow using mod q functions as gates for prime [math]q[/math].
• Majority is noise stable but is not tame.
• AC⁰ circuits of depth [math]d \geq 2[/math] even approximating majority (outputting the same value as majority for a constant fraction more than half of the inputs) requires size [math]2^{\Theta(n^{1/(2d-1)})}[/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].
• Majority is [math](r,r/\sqrt{n})[/math]- resilient.

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

This is different from the usual meaning of approximating a boolean function where we require it computes the function on most inputs.

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

If polynomial p has

[math] \Pr_{x \sim \{x \in \{-1, 1\}^n: \sum_i x_i \geq n/\ln(n)^c\}}[p(x) = -1] \leq 1/n [/math]

[math] \Pr_{x \sim \{x \in \{-1, 1\}^n: \sum_i x_i \leq -n/\ln(n)^c\}}[p(x) = 1] \leq 1/10 [/math]

Then p must have degree at least [math]\Omega(\ln(n)^{c+1})[/math].

Loosely, any polynomial p approximately solving the [math]\frac{1}{\ln(n)^c}[/math]-promise majority must have degree [math]\Omega(\ln(n)^{c+1})[/math] .