Algorithmic Aspects of Information Theory

In this talk, we will give an overview of some fundamental concepts in database theory: relational schemas, queries, data dependencies and normal forms. Besides, we will present a connection between normalization theory and information theory.

The implication problem studies whether a set of conditional independence (CI) statements (antecedents) implies another CI (consequent), and has been extensively studied under the assumption that all CIs hold exactly. In this work, we drop this assumption, and define an approximate implication as a linear inequality between the degree of satisfaction of the antecedents and consequent. More precisely, we ask what guarantee can be provided on the inferred CI when the set of CIs that entailed it hold only approximately. We use information theory to define the degree of satisfaction, and prove several results. In the general case, no such guarantee can be provided. We prove that such a guarantee exists for the set of CIs inferred in directed graphical models, making the d-separation algorithm a sound and complete system for inferring approximate CIs. We also prove an approximation guarantee for independence relations derived from marginal and saturated CIs.

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined “authorized” sets of parties can reconstruct the secret $s$, and all other “unauthorized” sets learn nothing about $s$. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $2^{n-o(n)}$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan [1] have reduced the share size to $2^{0.994n+o(n)}$, and this was further improved by several follow-ups accumulating in an upper bound of ${1.5}^{n+o(n)}$ [2]. In this talk will survey the known results on secret-sharing schemes and present some ideas of the new constructions.

We study statistical models of jointly normal random variables defined by conditional independence (CI) constraints. These models are semialgebraic sets. In this talk I present a number of so-called “universality theorems” for these models:

1. 1.

   all real algebraic numbers are necessary to witness that a given set of conditional independence constraints is consistent;

2. 2.

   the problem of deciding consistency (or, equivalently, solving the conditional independence implication problem for Gaussians) is complete for the existential theory of the reals; and

3. 3.

   all homotopy types of semialgebraic sets are attained by oriented Gaussian CI models.

These results parallel the celebrated universality theorems in matroid theory due to MacLane, Mnëv and Sturmfels.

The information content of the marginals of (finitely many) jointly distributed random variables reveals many important properties of the distribution, such as functional dependency or (conditional) independence. The information content is measured by the entropy, and information inequalities compare these marginal entropies. The entropy region is the collection of the entropy vectors of these distributions indexed by the non-empty subsets of the variables. The main focus of the talk is on discrete distributions, but many of the methods and concepts apply, with some modification, for linear, continuous, Gaussian, or quantum distributions. Points in the entropy region satisfy the basic Shannon inequalities [3], and the entropy region is bounded by collection of these inequalities, known as the Shannon bound. Points within the Shannon-bound are the also called polymatroids. The first non-Shannon entropy inequality was discovered by Zhang and Yeung [4]. The method obtaining this inequality was formalized and generalized by [1]. The general idea is to find an operation which preserves entropic points, but does not preserve polymatroids in general. Typical operations are restricting, factoring, conditioning, tightening, etc. Unfortunately they preserve both entropic points [2] and polymatroids, but might help in reducing the computational complexity of obtaining bounds on (or parts of) the entropy region. The two-step process of an adequate operation, dubbed as Copy Lemma, can be phrased as follows: first extend the distribution by adding identical copies of some of the variables (this step does not work in the quantum setting because of the no-cloning theorem), and then redefine the distribution so that the new and old variables become conditionally independent given the remaining variables. A known set of inequalities for the larger set of variables (e.g., the basic Shannon inequalities) might imply additional constraints on the old variables. The Copy Lemma can be considered to be a special case of the Maximal Entropy Method. Fix some marginal distributions on $M>N$ random variables to be identical with certain marginal distributions on $N$ random variables, and take the distribution on $M$ with the maximal possible entropy. This distribution will have strong structural properties: depending on the fixed marginals several conditional independences hold. Harvesting them might yield new constrains on the entropies of the original distribution. The presentation concludes with several computational challenges.

1. 1.

   Obtaining additional information inequalities requires embedding a distribution on $N$ variables to a distribution on $M>N$ variables, and then applying known information inequalities on $M$ variables. For $M$ larger than 15 even working with the Shannon bounds is prohibitively expensive. Devise a method which simplifies this treatment.

2. 2.

   Look systematically for limitations of the above methods with small number of added variables.

3. 3.

   Study how the above technique can be applied for quantum information, and obtain new quantum-information inequalities.

4. 4.

   A repository of (discrete) distributions with four variables whose convex combination approximates the complete entropic region might be extremely useful in answering practical / theoretical questions.

Secret sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. The information ratio is an indicator of the efficiency of a secret sharing scheme; it is the size in bits of the largest share of the scheme divided by the size of the secret.

This talk is focused on the following optimization problem: Given a family of subsets of parties $F$, find the infimum of the information ratio of all secret sharing schemes whose authorized subsets are the ones in $F$. Lower bounds on this optimal value can be computed by solving linear programming problems involving information inequalities.

We present improvements of this linear programming technique that use the Ahlswede-Körner lemma and the common information of random variables, avoiding the use of explicit non-Shannon information inequalities. Moreover, we show results of the application of this technique to the classification of representable matroids. The results presented in this talk were published in references.

This talk surveys work by IMU Abacus Medal winner Mark Braverman and others.

The basic question asked by information theory is how many bits of communication are needed to transmit information from $A$ to $B$. In contrast, communication complexity studies the amount of communication needed between two parties, $A$ and $B$, who want to compute a joint function of their inputs. Information complexity is an approach to communication complexity using information theory, specifically the notion of Information Complexity which is analogous to entropy. Using this approach, it is possible to compute asymptotically tight bounds on communication complexity. For example, Braverman, Garg, Pankratov and Weinstein [1] considered the fundamental problem of Set Disjointness, in which $A$ and $B$ each hold a subset of $\{\mathrm{\hspace{0.17em}1},\mathrm{\dots },n\}$, and their goal is to decide whether the two subsets are disjoint. They showed that the exact communication complexity of this function (with vanishing error) is roughly $0.4825\mathrm{\dots }n$, where $0.4825\mathrm{\dots }$ is an explicitly computable constant.

According to the traditional Tarski’s truth definition the semantics of first-order logic is defined with respect to an assignment of values to the free variables. In team semantics, truth is defined with respect to a set (or a probability distribution) of such assignments. This allows modeling concepts that inherently arise only in the presence of multitudes. Examples of concepts available in team semantics, but not in the Tarski semantics, include concepts of dependence and independence. In this talk we will take a brief look at how in team semantics one can analyze the relationships between relational and probabilistic dependencies as well as their interplay with logical operations.

The notion of entropy inequalities of Shannon and non-Shannon type have mostly been studied for formal power sets of random variables. Such power sets form Boolean lattices with inclusion as ordering. For applications in database theory and the study of Bayesian networks and similar graphical models of independence it is also relevant to study other lattices than the Boolean lattices. In general an element in a lattice should correspond to a set of variables, and one element in the lattice dominates another point if and only if the first corresponding set of variables determine the corresponding second set of variables. For any lattice one may ask which entropy inequalities that will hold for variables that are related in a way determined by the lattice. For certain classes of lattices all entropy inequalities are of the Shannon type and one goal of this research is to identify these lattices. There is also a link between entropy inequalities and inequalities for subgroups of a group. It turns out that this is related to the question of whether a specific lattice can be represented as the lattice of subgroups of a given group. This relation can be used see how certain codes used in cryptography and channel coding can be realized by the algebraic structure of certain groups.

The conditional independence implication problem is to decide whether several statements on the conditional independence among random variables implies another such statement. In this talk, we show that this problem is undecidable if we also allow imposing cardinality constraints (e.g., “$X$ is a binary random variable”). This is proved via a reduction from the domino problem about tiling the plane with a set of tiles. We will also briefly discuss a recent preprint which establishes the undecidability of the original conditional independence implication problem (without cardinality constraints) and related results, e.g., the undecidability of conditional information inequalities and network coding.

Cardinality estimation is one of the most important problems in database management. One aspect of cardinality estimation is to derive a good upper bound on the output size of a query, given a statistical profile of the inputs. In recent years, a promising information-theoretic approach was devised to address this problem, leading to robust cardinality estimators which are used in practice.

The information theoretic approach led to many interesting open questions surrounding optimizing a linear function on the almost-entropic or polymatroidal cones. This talk briefly introduces the problem, the approach, summarizes some known results, and lists open questions.

In this presentation, I introduce Term Coding (TC), which can be seen as an interface between Universal Algebra and Coding Theory. The work grew out of research related to Information flows and Information bottlenecks and the relationship to multiuser information theory [1, 2, 3, 4]. A large class of (finite) mathematical structures, e.g. universal algebras, can be defined by various equations. Traditionally, the main focus is on systems that satisfy the equations for all points in the domain. The concern in TC is finding structures (codes) that meet the defining equations for many but not necessarily all points. TC provide a general framework for (dynamic) network coding, index coding, and graph guessing games and is related to non-Shannon information inequalities and other advances in Information Theory [4].

It is known that the mutual information of a pair of objects $x$ and $y$ is equal to the size of the largest shared secret key that two parties (holding as their inputs $x$ and $y$ respectively) can establish via a communication protocol with interaction on a public channel. We discuss communication complexity of this problem and show show that a tight lower bound on the communication complexity can be proven with help of the expander mixing lemma combined with information inequalities.

Linear information inequalities valid for entropy functions induced by discrete random variables play an important role in the task to characterize discrete conditional independence structures [3, 4, 5]. Specifically, the so-called conditional Ingleton inequalities in the case of 4 random variables are in the center of interest: these are valid under conditional independence assumptions on the inducing random variables. The four inequalities of this form were earlier revealed: by Yeung and Zhang in 1997 [7], by Matúš in 1999 [5] and by Kaced and Romashchenko in 2013 [2]. In a recent 2021 paper [6] the fifth inequality of this type was found. These five information inequalities can be used to characterize all conditional independence structures induced by four discrete random variables. One of open problems in that 2021 paper was whether the list of conditional Ingleton inequalities over 4 random variables is complete: the analysis can be completed by a recent finding of Boege [1] answering that question.

The beginning of the tutorial was a brief overview of classic results on conditional independence inference. Then basic concepts were introduced: discrete random vector and conditional independence concept. Basic observation about discrete structures is that they form a finite lattice and can be characterized in terms of the so-called Horn clauses. After that the concept of a semi-graphoid was introduced and relevant partial axiomatizability results recalled: this concerns marginal and saturated independence [4], functional dependence [6] and relative two-antecedental completeness of semi-graphoidal inference [9]. The inspiration from the theory of relational databases for these results was explained [1, 8]. Basic information-theoretical measures were defined and their relation to the entropic function and the multiinformation functions recalled. A substantial part of the talk was devoted to algorithmic aspects of conditional independence inference, where the concept of a structural semi-graphoid plays the crucial role [7, 3]. The last part of the talk dealt with special conditional independence implications valid in case of Gaussian conditional independence structures [5, 2].

A max-information inequality is an inequality involving linear expressions of entropic terms, and one occurrence of $\max$. We consider the problem: given a max-information inequality, check if it holds for all entropic vectors. E.g. $\max (H(XY),H(YZ),H(ZX))\ge 2/3H(XYZ)$ is valid. It is open whether this problem is decidable.

We say that a structure $B$ “dominates” a structure $A$, if, for any other structure $C$, the number of homomorphisms $A\to C$ is less than or equal to the number of homomorphisms $B\to C$. We consider the problem: given two structures $A$, $B$, where $B$ is acyclic, check whether $B$ dominates $A$. The domination problem is equivalent to the “conjunctive query containment problem under bag semantics”, which is of interest in database theory. It is open whether this problem is decidable.

We prove that these two problems are computationally equivalent. In particular, any progress on the decidability or undecidability of one of these problems will automatically carry over to the other problem.

We show that the inequality 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\mid A)=H(A\mid X,Y)=0$, then .

We present one application of this result. Assume that a family $ℱ$ of pair-wise disjoint “squares” $S\times S\subset U\times V$ is given ($U$, $V$ are fixed finite sets). Assume that for each $u\in U$ there are at least $L$ squares in $ℱ$, whose first projection covers $u$, and similarly, for each $v\in V$ there are at least $R$ squares in $F$, whose second projection covers $v$. Then $|ℱ|\ge LR$.

Exhaustively determining the entropy region, and the information inequalities that describe it, form a tantalizingly fundamental problem in multi-terminal information theory. Among other equivalences, determining all information inequalities has been shown to be equivalent to determining the capacity regions of all networks under network coding, as well as determining all inequalities linking sizes of intersections of subgroups of a common group. Faces of the entropy region, in turn, dictate fundamental possible conditional independence relations among a series of random variables.

A key observation, however, is that many of these ultimate uses of the entropy region, both fundamental and applied, need only study the relationship between entropies of subsets that lie within a very small subfamily of the powerset of all subsets of the inscribed random variables. That is to say, were one able to exhaustively characterize the projection of the entropy region onto only the (sub)family of exclusively subsets involved in a problem of interest, one may provide the fundamental limits in that problem while the harder problem of determining the entire entropy region on the powerset remains unsolved. A natural question one may then ask is, which types of systems of subsets enable one to provide an exhaustive characterization of the associated projection of the entropy region onto only these subsets? Furthermore, which types of such systems of subsets yield the closure of the projected entropy region to be polyhedral? Which of those systems of subsets yield polyhedra enable a description complexity, as measured by the total number of involved inequalities, which scales nicely, even linearly, in the size of the problem, measured as the number of random variables?

In this talk, we set about characterizing some of these families of subsets with scalable complexity through the idea of pasting the entropy regions of small, overlapping, subsets to obtain bounds on associate projections of the entropy region on their union. A straightforward argument shows that this pasting construction easily yields outer bounds, and as such, attention shifts to when these outer bounds are tight. Examples of infinite families of subsets where the pasted entropy regions exhaustively characterize the associated projection of the larger entropy region are detailed. Among these are included cases where the associated projection of the entropy region has a number of required minimal inequalities that scales linearly with the number of random variables. Moreover, a construction proves cases where such pasted outer bounds are guaranteed to be loose.

Bearing these cases where pasting small entropy regions together only yields a loose outer bound for the true entropy region in mind, attention then shifts to finding inner bound constructions whose inner bound property is preserved under pasting. Of particular interest is in the inner bound to the entropy region formed by the set of inequalities linking linear ranks which dictates the part of the entropy region reachable by time sharing linear codes, as well as those linked with quasi-uniform distributions. A first inner-bound preserving technique pastes together integral polyhedral quasi-uniform bound on a chain of sets in the overlap of their ground set. A second inner-bound preserving pasting technique based on requiring the existence of consistent common informations is then also provided for these types of inner bounds. These constructions, together with the constructions that correctly characterize the associated projections of the entropy region, form a substantial family of composable constructions that can be used to create inner bounds for the entropy region of controllable complexity.

We introduce the notion of information ratio $\mathrm{Ir}(H/G)$ between two (simple, undirected) graphs $G$ and $H$, defined as the supremum of ratios $k/n$ such that there exists a mapping between the strong products $G^k$ to $H^n$ that preserves non-adjacency. Operationally speaking, the information ratio is the maximal number of source symbols per channel use that can be reliably sent over a channel with a confusion graph $H$, where reliability is measured w.r.t. a source confusion graph $G$. Various results are provided, including in particular lower and upper bounds on $\mathrm{Ir}(H/G)$ in terms of different graph properties, inequalities and identities for behavior under strong product and disjoint union, relations to graph cores, and notions of graph criticality. Informally speaking, $\mathrm{Ir}(H/G)$ can be interpreted as a measure of similarity between $G$ and $H$. We make this notion precise by introducing the concept of information equivalence between graphs, a more quantitative version of homomorphic equivalence. We then describe a natural partial ordering over the space of information equivalence classes, and endow it with a suitable metric structure that is contractive under the strong product. Various examples and open problems are discussed.

This talk discusses some recent results obtained jointly with Lukas Kühne and announces one new theorem. There is no algorithm which, given a matroid $M$,

1. 1.

   Decides whether $M$ is entropic.

2. 2.

   Decides whether $M$ is multilinear.

3. 3.

   Decides whether $M$ is almost-multilinear.

4. 4.

   Decides whether $M$ is almost-entropic.

(The last theorem was proved during the conference after an inspiring discussion with Janneke Bolt, Andrej Romashchenko, and Alexander Shen.)

Here a matroid $M$ is a polymatroid with values in the natural numbers (including 0) and satisfying that every singleton has rank at most 1. It is entropic if, as a polymatroid, its ray intersects the entropic cone. It is almost-entropic if it is in the closure of the entropic cone. The multilinear variants are about the analogous cones of linear rank functions.

A corollary of these theorems is that the conditional independence problem and its “approximate” variant are undecidable. Closely related results in the non-approximate setting have been obtained by Cheuk-Ting Li (preceding ours by some weeks) and have also been presented at this conference.

The entropy function plays a central role in information theory. Constraints on the entropy function in the form of inequalities, viz. entropy inequalities (often conditional on certain Markov conditions imposed by the problem under consideration), are indispensable tools for proving converse coding theorems. In this talk, I will give an overview of the development of machine-proving of entropy inequalities for the past 25 years. To start with, I will present a geometrical framework for the entropy function, and explain how an entropy inequality can be formulated, with or without constraints on the entropy function. Among all entropy inequalities, Shannon-type inequalities, namely those implied by the nonnegativity of Shannon’s information measures, are best understood. We will focus on the proving of Shannon-type inequalities, which in fact can be formulated as a linear programming problem. I will discuss ITIP, a software package originally developed for this purpose in the mid-1990s, as well as some of its later variants. In 2014, Tian successfully characterized the rate region of a class of exact-repair regenerating codes by means of a variant of ITIP. This is the first nontrivial converse coding theorem proved by a machine. At the end of the talk, I will discuss some recent progress in speeding up the proving of entropy inequalities.