Difference between revisions of "Wegener's monotone address"
m (Renan moved page Wegners monotone address to Wegener's monotone address: Wrong name) |
m (→Definition) |
||
| (3 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
| − | For even <math>k</math>, let <math>n = k + \binom{k}{2}</math>. '''Wegner's monotone address''' function <math>f:\{-1,1\}^{n} \to \{-1,1\}</math> is defined as follows. Let <math>A = \{S \subseteq \{1,\ldots,k \} : |S| = k/2 \}</math> be the subsets of <math>1\ldots k</math> of size <math>k/2</math>, and let <math>\alpha</math> be an arbitrary one-to-one mapping from <math>A</math> to <math>\{1,\ldots, \binom{k}{2} \}</math>. Denote by <math>h(x)</math> the Hamming weight of <math>x</math>, i.e the number of ones in the vector <math>x</math>. Then <math>f(x)</math> is defined as follows: | + | For even <math>k</math>, let <math>n = k + \binom{k}{k/2}</math>. '''Wegner's monotone address''' function <math>f:\{-1,1\}^{n} \to \{-1,1\}</math> is defined as follows. Let <math>A = \{S \subseteq \{1,\ldots,k \} : |S| = k/2 \}</math> be the subsets of <math>1\ldots k</math> of size <math>k/2</math>, and let <math>\alpha</math> be an arbitrary one-to-one mapping from <math>A</math> to <math>\{1,\ldots, \binom{k}{k/2} \}</math>. Denote by <math>h(x)</math> the Hamming weight of <math>x</math>, i.e the number of ones in the vector <math>x</math>. Then <math>f(x)</math> is defined as follows: |
| − | <math>f(x_1,\ldots,x_k,y_1,\ldots,y_{\binom{k}{2}}) = \begin{cases} | + | :::{| class="wikitable" |
| + | |- | ||
| + | |<math>f(x_1,\ldots,x_k,y_1,\ldots,y_{\binom{k}{k/2}}) = \begin{cases} | ||
-1, & if ~ h(x_1,\ldots,x_k) < k / 2 \\ | -1, & if ~ h(x_1,\ldots,x_k) < k / 2 \\ | ||
+1 & if ~ h(x_1,\ldots,x_k) > k / 2 \\ | +1 & if ~ h(x_1,\ldots,x_k) > k / 2 \\ | ||
y_{\alpha(x_1,\ldots,x_k)} & if ~ h(x_1,\ldots,x_k) = k / 2 \end{cases}. | y_{\alpha(x_1,\ldots,x_k)} & if ~ h(x_1,\ldots,x_k) = k / 2 \end{cases}. | ||
</math> | </math> | ||
| + | |} | ||
In words, if the first <math>k</math> input bits have Hamming weight less than <math>k/2</math>, the function's value is <math>-1</math>. If the Hamming weight is greater than <math>k/2</math>, the value is <math>+1</math>. And if the Hamming weight is exactly <math>k/2</math>, then the <math>n</math> bits serve to select an arbitrary bit from the rest of the input, similar to the [[address | address function]]. | In words, if the first <math>k</math> input bits have Hamming weight less than <math>k/2</math>, the function's value is <math>-1</math>. If the Hamming weight is greater than <math>k/2</math>, the value is <math>+1</math>. And if the Hamming weight is exactly <math>k/2</math>, then the <math>n</math> bits serve to select an arbitrary bit from the rest of the input, similar to the [[address | address function]]. | ||
| Line 13: | Line 16: | ||
* As the name suggests, the function is [[monotone function | monotone]]. | * As the name suggests, the function is [[monotone function | monotone]]. | ||
* The critical complexity of <math>f</math> is <math>k/2 + 1</math>. <ref name="Wegener">Proposition 3 in Ingo Wegener, [https://www.sciencedirect.com/science/article/pii/S001999588580036X The critical complexity of all (monotone) boolean functions and monotone graph properties], Information and control 1985.</ref> | * The critical complexity of <math>f</math> is <math>k/2 + 1</math>. <ref name="Wegener">Proposition 3 in Ingo Wegener, [https://www.sciencedirect.com/science/article/pii/S001999588580036X The critical complexity of all (monotone) boolean functions and monotone graph properties], Information and control 1985.</ref> | ||
| − | * The function <math>f</math> has sensitivity <math>\frac{1}{2}\log n + \frac{1}{4} \log\log n + O(1). TODO: add a word about this: this value should be an extremal sensitivity value | + | * The function <math>f</math> has sensitivity <math>\frac{1}{2}\log n + \frac{1}{4} \log\log n + O(1). </math> <ref name="Wegener" /> TODO: add a word about this: this value should be an extremal sensitivity value |
== References == | == References == | ||
<references/> | <references/> | ||
| − | [[Category:Monotone function]] [[Category:balanced function]] | + | [[Category:Monotone function]] [[Category:balanced function]] [[Category:Noise stable function]] |
Latest revision as of 06:10, 24 January 2023
Definition
For even [math]k[/math], let [math]n = k + \binom{k}{k/2}[/math]. Wegner's monotone address function [math]f:\{-1,1\}^{n} \to \{-1,1\}[/math] is defined as follows. Let [math]A = \{S \subseteq \{1,\ldots,k \} : |S| = k/2 \}[/math] be the subsets of [math]1\ldots k[/math] of size [math]k/2[/math], and let [math]\alpha[/math] be an arbitrary one-to-one mapping from [math]A[/math] to [math]\{1,\ldots, \binom{k}{k/2} \}[/math]. Denote by [math]h(x)[/math] the Hamming weight of [math]x[/math], i.e the number of ones in the vector [math]x[/math]. Then [math]f(x)[/math] is defined as follows:
[math]f(x_1,\ldots,x_k,y_1,\ldots,y_{\binom{k}{k/2}}) = \begin{cases} -1, & if ~ h(x_1,\ldots,x_k) \lt k / 2 \\ +1 & if ~ h(x_1,\ldots,x_k) \gt k / 2 \\ y_{\alpha(x_1,\ldots,x_k)} & if ~ h(x_1,\ldots,x_k) = k / 2 \end{cases}. [/math]
In words, if the first [math]k[/math] input bits have Hamming weight less than [math]k/2[/math], the function's value is [math]-1[/math]. If the Hamming weight is greater than [math]k/2[/math], the value is [math]+1[/math]. And if the Hamming weight is exactly [math]k/2[/math], then the [math]n[/math] bits serve to select an arbitrary bit from the rest of the input, similar to the address function.
Properties
- As the name suggests, the function is monotone.
- The critical complexity of [math]f[/math] is [math]k/2 + 1[/math]. [1]
- The function [math]f[/math] has sensitivity [math]\frac{1}{2}\log n + \frac{1}{4} \log\log n + O(1). [/math] [1] TODO: add a word about this: this value should be an extremal sensitivity value
References
- ↑ 1.0 1.1 Proposition 3 in Ingo Wegener, The critical complexity of all (monotone) boolean functions and monotone graph properties, Information and control 1985.
