## 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

Tagged with: , ,
Posted in Theory