Common information, matroid representation, and secret sharing for matroid ports
- PDF / 467,985 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 65 Downloads / 197 Views
Common information, matroid representation, and secret sharing for matroid ports Michael Bamiloshin1 · Aner Ben-Efraim2 · Oriol Farràs1
· Carles Padró3
Received: 18 February 2020 / Revised: 8 October 2020 / Accepted: 10 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Linear information and rank inequalities as, for instance, Ingleton inequality, are useful tools in information theory and matroid theory. Even though many such inequalities have been found, it seems that most of them remain undiscovered. Improved results have been obtained in recent works by using the properties from which they are derived instead of the inequalities themselves. We apply here this strategy to the classification of matroids according to their representations and to the search for bounds on secret sharing for matroid ports. Keywords Matroid representation · Secret sharing · Information inequalities · Common information · Linear programming Mathematics Subject Classification 68P30 · 52B40 · 94A62 · 94A60
Communicated by C. Blundo. Michael Bamiloshin and Oriol Farràs were supported by the grant 2017 SGR 705 from the Government of Catalonia and Grant RTI2018-095094-B-C21 “CONSENT” from the Spanish Government. Also, Michael Bamiloshin has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 713679 and from the Universitat Rovira i Virgili. Aner Ben-Efraim was supported by ISF Grant 152/17. Carles Padró was supported by the Spanish Government through Grant MTM2016-77213-R.
B
Oriol Farràs [email protected] Michael Bamiloshin [email protected] Aner Ben-Efraim [email protected] Carles Padró [email protected]
1
Universitat Rovira i Virgili, Tarragona, Spain
2
Ariel University, Ariel, Israel
3
Universitat Politècnica de Catalunya, Barcelona, Spain
123
M. Bamiloshin et al.
1 Introduction Some of the concepts appearing next are defined in Sect. 2. The reader is referred to the books [46,59] on matroid theory and [60] on information theory, and the surveys [4,47] on secret sharing for additional information about these topics.
1.1 Matroid representation Relevant applications in information theory, especially in secret sharing and network coding, brought to light the class of entropic matroids, which contains the well-known class of linear matroids. An entropic vector is formed by the joint Shannon entropies of all subsets of a finite set of discrete random variables. Every entropic vector is the rank function of a polymatroid. A polymatroid is entropic if its rank function is a multiple of an entropic vector. Limits of entropic polymatroids are called almost entropic. Both representation by partitions [37] and by almost affine codes [54] are characterizations of entropic matroids. In the same way that linear matroids are defined from configurations of vectors in a vector space, configurations of vector subspaces determine linear polymatroids. A folded linear matroid is such that so
Data Loading...