Network Coding and the Model Theory of Linear Information Inequalities

被引：0

作者：

Gomez, Arley ^{[1
]}

Mejia, Carolina ^{[1
]}

Andres Montoya, J. ^{[1
]}

机构：

[1] Univ Nacl Colombia, Fac Ciencias, Dept Matemat, Bogota, Colombia

来源：

2014 INTERNATIONAL SYMPOSIUM ON NETWORK CODING (NETCOD) | 2014年

关键词：

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let n >= 4, can the entropic region of order n be defined by a finite list of polynomial inequalities? This question was first asked by Chan and Grant. We show that if it were the case one could solve many algorithmic problems coming from Network Coding, Index Coding and Secret Sharing. Unfortunately, it seems that the entropic regions of order larger than four are not semialgebraic. Actually, we guess that it is the case and we provide strong evidence supporting our conjecture.

引用

页数：6

共 22 条

[1]

[Anonymous], 1997, Complexity and Real Computation

[2]

[Anonymous], NONSHANNON INFORM IN

[3]

[Anonymous], 2002, A first course in information theory

[4]

Baber R., 2013, NETCOD 2013 CALG CAN, P1

[5]

Bassoli R., NETWORK COD IN PRESS

[6] Secret Sharing and Non-Shannon Information Inequalities [J].

Beimel, Amos ;

Orlov, Ilan .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (09) :5634-5649

[7] Non-linear Information Inequalities [J].

Chan, Terence ;

Grant, Alex .

ENTROPY, 2008, 10 (04) :765-775

[8] The size of a share must be large [J].

Csirmaz, L .

JOURNAL OF CRYPTOLOGY, 1997, 10 (04) :223-231

[9]

Csirmaz L., 2013, ENTROPY REGION CONVO

[10] Six new non-Shannon information inequalities [J].

Dougherty, Randall ;

Freiling, Christopher ;

Zeger, Kenneth .

2006 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1-6, PROCEEDINGS, 2006, :233-+

← 1 2 3 →