Junta
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
