Difference between revisions of "Dictator"
(Created page with "== 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>...") |
m |
||
| (9 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == 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) = | + | 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 == | == 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. <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=1153 Theorem 7 in section 7.1]</ref> | + | * The Fourier representation of a dictator function is either <math>f(x) = x_i</math> or <math>f(x) = -x_i</math>. |
| − | * Dictators maximize mutual information: If <math>X,Y</math> are two | + | * 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.<ref>https://math.stackexchange.com/questions/64449/a-boolean-function-with-total-influence-1-must-be-a-dictatorship</ref> |
| + | * The [[decision tree complexity]] of the dictator function is <math>D(f) = 1</math> | ||
| + | * Dictators are a special case of [[Perceptron]]s. | ||
| + | * 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. <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=1153 Theorem 7 in section 7.1]/</ref> | ||
| + | * 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>. <ref>Georg Pichler, Pablo Piantanida, Gerald Matz, [https://arxiv.org/abs/1604.02109 Dictator Functions Maximize Mutual Information].</ref> | ||
| + | * 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. <ref>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. [https://doi.org/10.1016/S0196-8858%2802%2900024-6 doi:10.1016/S0196-8858(02)00024-6.]</ref> | ||
| + | * TODO: someone more knowledgeable should add something about the Unique Games Conjecture. | ||
== References == | == References == | ||
<references/> | <references/> | ||
| + | |||
| + | [[Category:balanced function]] [[Category:evasive function]] [[Category:monotone function]] [[Category:odd function]] [[Category:Noise stable function]] | ||
Latest revision as of 10:27, 20 March 2022
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]
- The decision tree complexity of the dictator function is [math]D(f) = 1[/math]
- 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.
