### Abstract

The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications. A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques. Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials. A desirable property for a quadratization is to introduce small number of auxiliary variables. For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular. However, much less is known for positive monomials. The best lower bound on the number of variables required by a quadratization in the literature is (Formula presented.). We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound. This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact k out-of-n functions, which is a more general class of symmetric functions. Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization. Finally, we provide quadratizations for general symmetric functions using O(n) auxiliary variables. This upper bound nicely matches a lower bound of Ω(n) variables that was recently introduced.

Original language | English (US) |
---|---|

State | Published - Jan 1 2018 |

Event | 2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018 - Fort Lauderdale, United States Duration: Jan 3 2018 → Jan 5 2018 |

### Conference

Conference | 2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018 |
---|---|

Country | United States |

City | Fort Lauderdale |

Period | 1/3/18 → 1/5/18 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Applied Mathematics
- Artificial Intelligence

### Cite this

*Quadratizations of symmetric pseudo-boolean functions: Sub-linear bounds on the number of auxiliary variables*. Paper presented at 2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018, Fort Lauderdale, United States.