Hastad Dictator Test for Boolean Functions
A function \(f\colon \{0,1\}^n\to \{0,1\}\) is a dictator function if there exists \(i\in [n]\) such that \(f(x) = x_i\). That is, the function is completely determined by its \(i\)-th input. A function \(f\colon \{0,1\}^n\to \{ \pm 1\}\) is a dictator …