  We consider the problem of linearizing a pseudo-Boolean function $f :
\{0,1\}^n \to \mathbb{R}$ by means of $k$ Boolean functions. Such a
linearization yields an integer linear programming formulation with only $k$
auxiliary variables. This motivates the definition of the linarization
complexity of $f$ as the minimum such $k$. Our theoretical contributions are
the proof that random polynomials almost surely have a high linearization
complexity and characterizations of its value in case we do or do not restrict
the set of admissible Boolean functions. The practical relevance is shown by
devising and evaluating integer linear programming models of two such
linearizations for the low auto-correlation binary sequences problem. Still,
many problems around this new concept remain open.
