# Dictator

## Definition

A function $f:\{-1,1\}^n \to \{-1,1\}$ is called a dictator function if there exists an index $i$ such that one of the following two is true: Either $f(x) = x_i$, or $f(x) = -x_i$. 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 $f(x) = x_i$, and the function $f(x) = -x_i$ is called an "anti-dictator".

## Properties

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