Short Prime Quadratizations of Cubic Negative Monomials

Pseudo-Boolean functions naturally model problems in a number of different areas such as computer science, statistics, economics, operations research or computer vision, among others. Pseudo-Boolean optimization (PBO) is NP-hard, even for quadratic polynomial objective functions. However, much progress has been done in finding exact and heuristic algorithms for the quadratic case. Quadratizations are techniques aimed at reducing a general PBO problem to a quadratic polynomial one. Quadratizing single monomials is particularly interesting because it allows quadratizing any pseudo-Boolean function by termwise quadratization. A characterization of short quadratizations for negative monomials has been provided. In this report we present a proof of this characterization for the case of cubic monomials, which requires a different analysis than the case of higher degree.