What is a multivariable Boolean polynomial? When I was reading a paper about optimization, I encountered to multivariable Boolean polynomials which was undefined. What is the exact definition of a multivariable Boolean polynomial and can you give me an examples of non-negative multivariable Boolean polynomial and one that is not non-negative on $\mathbb R[x_1,...,x_n]$?
 A: A multivariable Boolean polynomial $P$ is an element of $\mathbb{F}_2[x_1,\ldots,x_n]$ and in coding theory and cryptography usually taken to represent a map $P:\mathbb{F}_2^n\rightarrow \mathbb{F}_2.$ 
It can also be taken to mean an element $P$ of $\mathbb{Z}[x_1,\ldots,x_n]/(x_1^2-x_1,\ldots,x_n^2-x_n)$
In some computer science applications, it is convenient to think of $P$ as a map $P:\{-1,+1\}^n \rightarrow \{-1,+1\}$ via the correspondence $u\in \mathbb{F_2} \leftrightarrow v\in \{-1,+1\},$ given by $v=(-1)^u,$ which has some advantages in that it allows one to write the Hadamard (sometimes termed Walsh-Hadamard) transform in a way consistent with other Fourier transforms, i.e., without needing to use the function $(-1)^{P(x_1,\ldots,x_n)}$ one can use $P$ directly in the sum defining the transform.
Finally, this last formulation of $P$ can be generalized naturally to look at $P:\{-1,+1\}^n\rightarrow \mathbb{R}$ for optimization applications, voting theorems, influences etc. The book ``Analysis of Boolean Functions'' by Ryan O'Donnell, as well as many papers by Gil Kalai and others heavily use this formulation.
