Difference between revisions of "Category:Monotone function"
m (→Properties) |
m (→Properties) |
||
| Line 10: | Line 10: | ||
==Properties== | ==Properties== | ||
* The <math>i</math>-th [[influence]] of a monotone function is equal to its first level [[fourier representation | Fourier coefficient]]: <math>\mathrm{Inf}_i(f) = \widehat{f}(\{i\})</math>. | * The <math>i</math>-th [[influence]] of a monotone function is equal to its first level [[fourier representation | Fourier coefficient]]: <math>\mathrm{Inf}_i(f) = \widehat{f}(\{i\})</math>. | ||
| − | * For monotone functions, the total [[influence]] is bounded by the square root of the [[partition size]]: <math>\mathrm{Inf}(f) \leq \sqrt{P(f)}</math> <ref>Ryan O'Donnell, Rocco Servedio, [https://www.cs.cmu.edu/~odonnell/papers/learn-monotone.pdf Learning Monotone Functions from Random Examples in Polynomial Time]</ref>. | + | * For monotone functions, the total [[influence]] is bounded by the square root of the [[partition size]]: <math>\mathrm{Inf}(f) \leq \sqrt{\log(P(f))}</math> <ref>Ryan O'Donnell, Rocco Servedio, [https://www.cs.cmu.edu/~odonnell/papers/learn-monotone.pdf Learning Monotone Functions from Random Examples in Polynomial Time]</ref>. |
* TODO: Add properties about stability and noise sensitivity. See Mossel and O'Donnell. | * TODO: Add properties about stability and noise sensitivity. See Mossel and O'Donnell. | ||
Latest revision as of 18:18, 2 March 2020
Definition
For two vectors [math]x,y \in \{-1,1\}^n[/math], define a partial order relation by
[math]x \leq y \iff x_i \leq y_i ~~ \forall i = 1\ldots n.[/math]
A monotone Boolean function is a Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] which is monotone in its input:
[math]x \leq y \Rightarrow f(x) \leq f(y) [/math].
Properties
- The [math]i[/math]-th influence of a monotone function is equal to its first level Fourier coefficient: [math]\mathrm{Inf}_i(f) = \widehat{f}(\{i\})[/math].
- For monotone functions, the total influence is bounded by the square root of the partition size: [math]\mathrm{Inf}(f) \leq \sqrt{\log(P(f))}[/math] [1].
- TODO: Add properties about stability and noise sensitivity. See Mossel and O'Donnell.
References
- ↑ Ryan O'Donnell, Rocco Servedio, Learning Monotone Functions from Random Examples in Polynomial Time
Pages in category "Monotone function"
The following 11 pages are in this category, out of 11 total.
