|
|
 |
|
Jeudi 26 Octobre
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle A303, bâtiment A, Université de Villetaneuse |
| Résumé: |
Binary non-negative polynomials and convex certificates |
| Description: |
Liding Xu We consider the problem of certifying the non-negativity of polynomials over the Boolean hypercube.
We propose a new type of binary non-negativity certificate, which involves the signed support vector of the monomials occurring in the given polynomial. We employ known tools such as max flow and extensions of supermodular functions in order to construct our certificates. Especially, we examine the projected and extended LP formulations for the cone of our binary non-negativity certificates.
Based on these tools, we show that a certain family of binary polynomials can be optimized in a fixed-parameter tractable way. |
|
|
