A {\em pseudo-Boolean function} is a real-valued function f(x)=f(x_1,x_2,\ldots,x_n) of n binary variables. It is well-known that every pseudo-Boolean function can be uniquely represented as a multilinear polynomial in its variables.
\emph{Nonlinear binary optimization problems}, or \emph{pseudo-Boolean optimization} (PBO) \emph{problems}, of the form
\min \{ f(x) : x \in \{0,1\}^n \},
where f(x) is a pseudo-Boolean polynomial, have attracted the attention of numerous researchers for more than 50 years. These problems are notoriously difficult, as they naturally encompass a broad variety of models such as maximum satisfiability, max cut, graph coloring, image restoration, and so on.
In this talk, I present recent results (obtained in collaboration with Martin Anthony, Endre Boros, Aritanan Gruber, and Elisabeth Rodriguez-Heck) regarding the size of reformulations of nonlinear PBO problems as quadratic PBO problems.
