Tag: dictator function

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 …

Hastad Dictator Test for Boolean Functions Read more »