# Dictator

## Definition

A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called a **dictator function** if there exists an index [math]i[/math] such that one of the following two is true: Either [math]f(x) = x_i[/math], or [math]f(x) = -x_i[/math]. In other words, the function is a dictator if its output is controlled by only single bit from the input.

Sometimes, the term "dictator" refers only to the function [math]f(x) = x_i[/math], and the function [math]f(x) = -x_i[/math] is called an "anti-dictator".

## Properties

- The Fourier representation of a dictator function is either [math]f(x) = x_i[/math] or [math]f(x) = -x_i[/math].
- In a dictatorship, the [math]i[/math]-th variable has influence 1, while all others have influence 0. Conversely, if a Boolean function [math]f[/math] has total influence 1, then it is a dictator.
^{[1]} - Dictators are a special case of Perceptrons.
- Dictators are locally testable: Given query access to a function [math]f[/math], only a constant number of queries is needed in order to determine if it is a dictator with high probability.
^{[2]} - Dictators maximize mutual information: If [math]X,Y[/math] are two correlated random vectors in [math]\{-1,1\}^n[/math] with iid entries, and [math]f,g[/math] are two Boolean functions, then the mutual information [math]I(f(X), g(Y))[/math] is maximized when [math]f[/math] is a dictator and [math]g = \pm f[/math].
^{[3]} - FKN theorem: If a Boolean function [math]f[/math]'s Fourier representation is close to a degree-1 polynomial, then [math]f[/math] is close to the dictator function.
^{[4]} - TODO: someone more knowledgeable should add something about the Unique Games Conjecture.

## References

- ↑ https://math.stackexchange.com/questions/64449/a-boolean-function-with-total-influence-1-must-be-a-dictatorship
- ↑ Ryan O'Donnell, Analysis of Boolean functions, Theorem 7 in section 7.1/
- ↑ Georg Pichler, Pablo Piantanida, Gerald Matz, Dictator Functions Maximize Mutual Information.
- ↑ Friedgut, Ehud; Kalai, Gil; Naor, Assaf (2002). "Boolean functions whose Fourier transform is concentrated on the first two levels". Adv. Appl. Math. 29 (3): 427–437. doi:10.1016/S0196-8858(02)00024-6.