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 [math]f(x) = 1[/math] if and only if [math]x_i = 1[/math]. In other words, the function is a dictator if and only if its output is controlled by only single bit from the input.
Properties
- 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. [1]
- Dictators maximize mutual information: If [math]X,Y[/math] are two iid random vectors in [math]\{-1,1\}^n[/math] 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]. [2]
References
- ↑ Ryan O'Donnell, Analysis of Boolean functions, Theorem 7 in section 7.1
- ↑ Georg Pichler, Pablo Piantanida, Gerald Matz, Dictator Functions Maximize Mutual Information
