Difference between revisions of "Junta"
(Created page for junta) |
m (→Properties: Added Friedgut's junta theorem) |
||
| Line 5: | Line 5: | ||
== Properties == | == Properties == | ||
| − | * | + | * Friedgut's Junta theorem: Let <math>f</math> be a [[:category:balanced function|balanced]] Boolean function with total influence <math>\mathrm{Inf}(f) \geq M</math> and let <math>\varepsilon > 0</math>. Then <math>f</math> is <math>\varepsilon</math>-close to a <math>2^{O(M/\varepsilon)}</math> junta. <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=1484 Section 9.6]</ref> |
* TODO: Write and cite learning Juntas | * TODO: Write and cite learning Juntas | ||
* TODO: Testing juntas? | * TODO: Testing juntas? | ||
Latest revision as of 09:17, 18 November 2019
Definition
A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called a k-junta if there exist [math]k[/math] indices [math]i_1, \ldots, i_k[/math] such that the output of [math]f[/math] depends only on the bits [math]x_{i_1}, \ldots, x_{i_k}[/math].
Juntas a generalization of dictators: Every dictator is a 1-junta.
Properties
- Friedgut's Junta theorem: Let [math]f[/math] be a balanced Boolean function with total influence [math]\mathrm{Inf}(f) \geq M[/math] and let [math]\varepsilon \gt 0[/math]. Then [math]f[/math] is [math]\varepsilon[/math]-close to a [math]2^{O(M/\varepsilon)}[/math] junta. [1]
- TODO: Write and cite learning Juntas
- TODO: Testing juntas?
References
- ↑ Ryan O'Donnell, Analysis of Boolean functions, Section 9.6
