MAK Crypto Seminar

Given some random variables X_1, ... , X_n, one can form a vector of size 2^n-1 with the entropies of subsets of variables: [H(X_1), H(X_2), H(X_1,X_2), ... , H(X_1,...,X_n)]. The set of all possible such vectors is an object in the Euclidean space delimited by hyperplanes: information inequalities. Perhaps the most famous inequality is Shannon's basic inequality H(A,C) + H(B,C) = H(A) + H(A,B,C). We will see which role do these inequalities play in problems like secret sharing. I will also discuss a recent result on the geometry of inequalities based on duality of polymatroid.