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

• TODO: Write and cite Friedgut Junta theorem
• TODO: Write and cite learning Juntas
• TODO: Testing juntas?