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

## Fourier Analysis of Boolean Functions under Random Restriction

Fourier Transform Consider a function $$f\colon \{0,1\}^n \to \{-1, 1\}$$ on $$n$$ boolean variables. This can be viewed as a transform of a boolean function $$g\colon \{0,1\}^n \to \{0, 1\}$$ by letting $$f(x) = (-1)^{g(x)}$$. For $$\alpha \in\{0,1\}^n$$, define the

Tagged with: , ,
Posted in Theory