From Boolean Zoo
Jump to: navigation, search


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.


  • 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] [1].
  • TODO: a description of Majority's Fourier Transform. See 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 AC0, even if we allow using mod q functions as gates for prime [math]q[/math]. [2]
  • Majority is noise stable but is not tame. [3]
  • AC0 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][4].
  • 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]. [5]
  • 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 AC0 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 AC0 [6] or depth d deterministic AC0[[math]\oplus[/math]] [7] 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] [7].


  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. Johan Jonasson, Jeffrey E. Steif, Volatility of Boolean functions, Stochastic Processes and their Applications, Proposition 1.15
  4. Kazuyuki Amano, Bounds on the Size of Small Depth Circuits for Approximating Majority, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, pages 59-70.
  5. 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
  6. Emanuele Viola, Randomness Buys Depth for Approximate Counting. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
  7. 7.0 7.1 Nutan Limaye and Srikanth Srinivasan and Utkarsh Tripathi, More on AC0[math]\oplus[/math] and Variants of the Majority Function. In: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)