On the theory of polynomial information inequalities

We study the definability of the almost entropic regions by finite sets of polynomial inequalities. Sets defined in this way are called semialgebraic. There is a strong connection between semialgebraic sets and Model Theory, this connection is presented through the so-called Tarski-Seidenberg Theorem. We explore this connection and, for instance, we prove that the set of entropic vectors of order greater than two is not semialgebraic. Moreover, we present strong evidence suggesting that the almost entropic regions of order greater than three are not semialgebraic. First we present an alternative proof of Matus theorem, which states that the almost entropic regions are not polyhedral, then we deal with the problem of finding new sequences of information inequalities and finally we show that the semialgebraicity of the almost entropic regions depends on the essential conditionality of certain class of conditional information inequalities. We also explore some algorithmic consequences of the almost entropic regions being semialgebraic, specifically we study some of the consequences of this fact in Secret Sharing and its relation with Matroid Theory.

• Autores: Gómez Ríos, Arley Ramsés
• Tipo de recurso: Doctoral thesis
• Fecha de publicación: 2018
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/69162
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/69162; http://bdigital.unal.edu.co/70696/
• Palabra clave: 51 Matemáticas / Mathematics; Entropy; Entropic vectors; Information inequalities; Entropic regions; Secret Sharing; Entropía; Vectores entrópicos; Desigualdades de la información; Regiones entrópicas; Repartición de secretos
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional