Functiond definition

Boolean function

$f:{\{0,1\}}^n\to \{0,1\}$ or ${\{\pm 1\}}^n\to \{\pm 1\}$. Ones and zeros: $I^f=\{x:f(x)=1\}$; $O^f$.

Randomized boolean function

See algebra ref. Maps hypercube points to RV’s taking value 1 with some probability.

Variables and their range

Changing input basis

$x_i\to x_i^{\prime };0\to 1;1\to -1:x_i=\frac{1-x_i^{\prime }}{2}$.

For fixing polynomial for change in basis: $\{\pm 1\}\to \{0,1\}:x_i\to (\frac{1+x_i}{2})$.

Variables and literals

Consider $x\in {\{0,1\}}^n$. Every $x_i$ is a variable, and $x_i,\overline{x_i}..$ are literals.