Hermitian sum of squares multipliers on finite subsets of C^n

The study of hypercube nodes is one of the most important topics in computer science, since this set is the domain of Boolean functions. They are the functions that associate each length?n binary vector, or string, into a single binary value, or bit. These functions are present in many fields such as learning theory, coding theory, social choice theory, graph theory and more.The study of the coordinate ring of hypercube nodes constitutes a generalization of the study of Boolean functions. In 2016, Bleckhermann, Gouveia and Pfeifer gave upper and lower bounds to certificate the non-negativeness of polynomials in the coordinate ring of hypercube nodes. In this text, we generalize the conditions exposed in Theorem 1.1[3] by Bleckherman, Gouveia and Pfeiffer for finite subsets of finite dimensional complex vector spaces. Based on their result, we give an upper bound for hermitian sum of squares multipliers related to the finite set U := U_d × · · · × U_d, which is defined as the cartesian product of n copies of U_d, the set of d-th roots of unity. Finally, we present a brief application of this idea to the graph coloring problem.

• Autores: Castro Pulido, Nicolás Andrés
• Fecha de publicación: 2021
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: spa
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/55794
• Acceso en línea: http://hdl.handle.net/1992/55794
• Palabra clave: Nodos del hipercubo; Funciones Booleanas; Cotas superiores; Cotas inferiores; Grados polinomiales; No-negatividad de polinomios; Matemáticas
• Rights: openAccess
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/