On the Theory of Linear Rank Inequalities
Cargando...
Autores
Mejía Moreno, Carolina
Director
Tipo de contenido
Document language:
Español
Fecha
Título de la revista
ISSN de la revista
Título del volumen
Documentos PDF
Resumen
En este trabajo estudiamos los polimatroides lineales y las desigualdades rango lineales. Nos enfocamos en el problema de determinar si elMétodo de la Información Común puede generar todas las desigualdades rango lineales, que son las desigualdades satisfechas por todos los polimatroides lineales. Se sabe que existen conexiones profundas entre la Teoría de desigualdades rango lineales y el Problema de Repartición Lineal de Secretos. En este texto estudiamos estas conexiones. Primero, estudiamos el problema de estimar las ratas de información que pueden ser alcanzadas por soluciones lineales al Problema de Repartición de Secretos. Luego, llegamos a la nueva noción de Repartición Abeliana de Secretos. Probamos que si las soluciones abelianas al Problema de Repartición de Secretos superan a las soluciones lineales, entonces el Método de la Información Común es incompleto. Por lo tanto, nos enfocamos en el problema de comparar las representaciones de esquemas abelianos y lineales. Nosotros probamos que este último problema está relacionado con la Teoría de Representación de Matroides (Texto tomado de la fuente).
Abstract
In this work, we study linear polymatroids and linear rank inequalities. We focus on the
problem of determining if the Common Information Method can generate all the linear
inequalities satisÖed by all linear polymatroids. It is well known that there exist deep
connections between the Theory of Linear Rank Inequalities and Linear Secret Sharing.
We study those connections. First, we study the problem of estimating the information
rates that can be achieved by Linear Secret Sharing. Then, we arrive to the novel notion
of Abelian Secret Sharing. We prove that if Abelian Secret Sharing outperforms Linear
Secret Sharing, then the Common Information Method is incomplete. Therefore, we
focus on the problem of comparing the performances of abelian and linear schemes. We
show that the last problem is related to the Representation Theory of Matroids.