# Junta

## Definition

A function $f:\{-1,1\}^n \to \{-1,1\}$ is called a k-junta if there exist $k$ indices $i_1, \ldots, i_k$ such that the output of $f$ depends only on the bits $x_{i_1}, \ldots, x_{i_k}$.

Juntas a generalization of dictators: Every dictator is a 1-junta.

## Properties

• Friedgut's Junta theorem: Let $f$ be a balanced Boolean function with total influence $\mathrm{Inf}(f) \geq M$ and let $\varepsilon \gt 0$. Then $f$ is $\varepsilon$-close to a $2^{O(M/\varepsilon)}$ junta. [1]
• TODO: Write and cite learning Juntas
• TODO: Testing juntas?

## References

1. Ryan O'Donnell, Analysis of Boolean functions, Section 9.6