Quadratizations of pseudo-Boolean functions

A pseudo-Boolean function is a real-valued function of 0-1 variables. Every pseudo-Boolean function can be represented by various analytical expressions, e.g., as a polynomial in its variables, or as a polynomial in its variables and in their Boolean complements, or as a disjunctive form, or as pointwise minimum of a family of affine functions, and so forth.

Motivated by the problem of minimizing pseudo-Boolean functions, we consider yet another class of representations. Namely, we say that g(x,y) is a quadratization of the pseudo-Boolean function f(x) if g(x,y) is a quadratic pseudo-Boolean function of x and of m auxiliary binary variables y such that, for all x, f(x) = min g(x,y), where the minimum is taken over all possible values of the y-variables.

It can be shown that every pseudo-Boolean function has at least one, and usually, many quadratizations. In recent years, several authors have proposed to reduce the problem of minimizing an arbitrary function f(x) (say, expressed as a high-degree polynomial) to the (presumably easier) problem of minimizing one of its quadratizations.

In this talk, we discuss the size of ``small'' quadratizations, that is, the number of auxiliary variables required in any quadratization. We provide lower and upper bounds on the number of auxiliary variables for the case of an arbitrary function f(x), as well as for the special case where f(x) is a symmetric function of its variables.