Difference between revisions of "Partition size"
m (→Properties) |
m (→Properties) |
||
| Line 5: | Line 5: | ||
== Properties == | == Properties == | ||
* The partition size is (trivially) always smaller than the [[decision tree]] size, <math>P(f) \leq DT(f) </math>. | * The partition size is (trivially) always smaller than the [[decision tree]] size, <math>P(f) \leq DT(f) </math>. | ||
| − | * The sum of the singleton [[fourier representation | Fourier coefficients]] is always smaller than the square root of of the partition size: <math>\sum_{i\in [n]} \widehat{f}(\{i\}) \leq \sqrt{P(f)}</math>. In particular, if <math>f</math> is [[monotone function | monotone]], then <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>. | + | * The sum of the singleton [[fourier representation | Fourier coefficients]] is always smaller than the square root of of the partition size: <math>\sum_{i\in [n]} \widehat{f}(\{i\}) \leq \sqrt{\log(P(f))}</math>. In particular, if <math>f</math> is [[monotone function | monotone]], then <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>. |
== References == | == References == | ||
<references/> | <references/> | ||
Latest revision as of 18:18, 2 March 2020
Definition
Let [math]f: \{-1,1\}^n \to \{-1,1\}[/math] be a Boolean function. The partition size of [math]f[/math], often denoted [math]P(f)[/math], is the minimum size of a partition of the Boolean cube [math]\{-1,1\}^n[/math] into disjoint subcubes such that [math]f[/math] is constant on each subcube.
Properties
- The partition size is (trivially) always smaller than the decision tree size, [math]P(f) \leq DT(f) [/math].
- The sum of the singleton Fourier coefficients is always smaller than the square root of of the partition size: [math]\sum_{i\in [n]} \widehat{f}(\{i\}) \leq \sqrt{\log(P(f))}[/math]. In particular, if [math]f[/math] is monotone, then [math]\mathrm{Inf}(f) \leq \sqrt{\log(P(f))}[/math] [1].
References
- ↑ Ryan O'Donnell, Rocco Servedio, Learning Monotone Functions from Random Examples in Polynomial Time
