Boolean function
\(f:\set{0,1}^{n} \to \set{0, 1}\) or \(\set{\pm1}^{n} \to \set{\pm 1}\). Ones and zeros: \(I^{f} = \set{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}’; 0 \to 1; 1 \to -1 : x_{i} = \frac{1- x_{i}’}{2}\).
For fixing polynomial for change in basis: \(\set{\pm 1} \to \set{0,1} :x_{i} \to (\frac{1+x_{i}}{2})\).
Variables and literals
Consider \(x \in \set{0, 1}^{n}\). Every \(x_i\) is a variable, and \(x_i, \bar{x_i} .. \) are literals.