We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.

We use the notion of polymatroid duality to define the formal dual of an information inequality. We use it to show that the closure of the entropy region for n ≥ 5 is not closed under polymatroid duality.

We show that the inequality H(A|B, X) + H(A|B, Y) ≤ H(A|B) for jointly distributed random variables A, B, X, Y, which does not hold in general case, holds under some natural condition on the support of the probability distribution of A, B, X, Y. This result generalizes a version of the conditional Ingleton inequality: if for some distribution I(X : Y|A) = H(A|X, Y) = 0, then I(A : B) ≤ I (A : B|X) + I(A : B|Y)+I(X : Y). We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K colors so that each two edges sharing a vertex have different colors and for each pair (left vertex x, right vertex y) there is at most one color a such both x and y are incident to edges with color a; assume further that the degree of each left vertex is at least L and the degree of each right vertex is at least R. Then K LR. The second application is a new method to prove lower bounds for biclique cover of bipartite graphs.

The capacity for multiterminal secret-key agreement inspires a natural generalization of Shannon's mutual information from two random variables to multiple random variables. Under a general source model without helpers, the capacity is shown to be equal to the normalized divergence from the joint distribution of the random sources to the product of marginal distributions minimized over partitions of the random sources. The mathematical underpinnings are the works on co-intersecting submodular functions and the principle lattices of partitions of the Dilworth truncation. We clarify the connection to these works and enrich them with information-theoretic interpretations and properties that are useful in solving other related problems in information theory as well as machine learning.

We consider a new group testing model wherein each item is a binary random variable defined by an a priori probability of being defective. We assume that each probability is small and that items are independent, but not necessarily identically distributed. The goal of group testing algorithms is to identify with high probability the subset of defectives via non-linear (disjunctive) binary measurements. Our main contributions are two classes of algorithms: (1) adaptive algorithms with tests based either on a maximum entropy principle, or on a Shannon-Fano/Huffman code; (2) non-adaptive algorithms. Under loose assumptions and with high probability, our algorithms only need a number of measurements that is close to the information-theoretic lower bound, up to an explicitly-calculated universal constant factor.

We compare two different techniques for proving non-Shannon-type information inequalities. The first one is the original Zhang-Yeung's method, commonly referred to as the copy/pasting lemma/trick. The copy lemma was used to derive the first conditional and unconditional non-Shannon-type inequalities. The second technique first appeared in Makarychev et al paper [6] and is based on a coding lemma from Ahlswede and Körner works. We first emphasize the importance of balanced inequalities and provide a simpler proof of a theorem of Chan's for the case of Shannon-type inequalities. We compare the power of various proof systems based on a single technique.

We study conditional linear information inequalities, i.e., linear inequalities for Shannon entropy that hold for distributions whose joint entropies meet some linear constraints. We prove that some conditional information inequalities cannot be extended to any unconditional linear inequalities. Some of these conditional inequalities hold for almost entropic points, while others do not. We also discuss some counterparts of conditional information inequalities for Kolmogorov complexity.

We show that two essentially conditional linear inequalities for Shannon's entropies (including the Zhang-Yeung'97 conditional inequality) do not hold for asymptotically entropic points. This means that these inequalities are non-robust in a very strong sense. This result raises the question of the meaning of these inequalities and the validity of their use in practice-oriented applications.

To split a secret s between several participants, we generate (for each value of s) shares for all participants. The goal: authorized groups of participants should be able to reconstruct the secret but forbidden ones get no information about it. We introduce several notions of non-perfect secret sharing, where some small information leak is permitted. We study its relation to the Kolmogorov complexity version of secret sharing (establishing some connection in both directions) and the effects of changing the secret size (showing that we can decrease the size of the secret and the information leak at the same time).

In 1997, Z. Zhang and R.W. Yeung found the first example of a conditional information inequality in four variables that is not “Shannon-type”. This linear inequality for entropies is called conditional (or constraint) since it holds only under condition that some linear equations are satisfied for the involved entropies. Later, the same authors and other researchers discovered several unconditional information inequalities that do not follow from Shannon's inequalities for entropy. In this paper we show that some non Shannon-type conditional inequalities are “essentially” conditional, i.e., they cannot be extended to any unconditional inequality. We prove one new essentially conditional information inequality for Shannon's entropy and discuss conditional information inequalities for Kolmogorov complexity.