Information Theory used to prove neat combinatorial statements?

Question

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?

Some examples I can think of are related to lower bounds for locally decodable codes, e.g., in this paper: suppose that for a bunch of binary strings $x_1,...,x_m$ of length $n$ it holds that for every $i$, for $k_i$ different pairs {$j_1,j_2$}, $$e_i = x_{j_1} \oplus x_{j_2}.$$ Then m is at least exponential in n, where the exponent depends linearly on the average ratio of $k_i/m$.

Another (related) example is some isoperimetric inequalities on the Boolean cube (feel free to elaborate on this in your answers).

Do you have more nice examples? Preferably, short and easy to explain.

Answer 1

Moser's proof of the constructive Lovasz Local Lemma. He basically shows that, under the conditions of the local lemma, the second-simplest algorithm for SAT you can think of works. (The first simplest might be to just try a random assignment until one works. The second simplest is took pick a random assignment, find an unsatisfied clause, satisfy it, then see what other clauses you broke, recurse, and repeat until done.) The proof that this runs in polynomial time is perhaps the most elegant use of information theory (or Kolmogorov complexity, whatever you want to call it in this case) I've ever seen.

Answer 2

My favorite example of this type is the entropy-based proof of Shearer's Lemma. (I learned of this proof and several other very pretty ones from Jaikumar Radhakrishnan's Entropy and Counting.)

Claim: Suppose you have $n$ points in $\mathbb{R}^3$ that have $n_x$ distinct projections on the $yz$-plane, $n_y$ distinct projections on the $xz$-plane and $n_z$ distinct projections on the $xy$-plane. Then, $n^2 \leq n_x n_y n_z$.

Proof: Let $p = (x,y,z)$ be a point uniformly chosen at random from the $n$ points. Let $p_x$, $p_y$, $p_z$ denote its projections onto the $yz$, $xz$ and $xy$ planes respectively.

On the one hand, $H[p] = \log n$, $H[p_x] \leq \log n_x$, $H[p_y] \leq \log n_y$ and $H[p_z] \leq \log n_z$, by basic properties of entropy.

On the other hand, we have $$H[p] = H[x] + H[y|x] + H[z | x,y]$$ and also $$H[p_x] = H[y] + H[z|y]$$ $$H[p_y] = H[x] + H[z|x]$$ $$H[p_z] = H[x] + H[y|x]$$ Adding the last three equations gives us: $H[p_x] + H[p_y] + H[p_z] =$ $2H[x] + H[y]+$ $H[y|x] +$ $H[z|x]$ $+ H[z|y]$ $\geq 2H[x] + 2H[y|x] + 2H[z|x,y] =$ $2H[p]$, where we used the fact that conditioning decreases the entropy (in general, $H[a] \geq H[a|b]$ for any random variables $a,b$).

Thus, we have $2 \log n \leq \log n_x + \log n_y + \log n_z$, or $n^2 \leq n_x n_y n_z$.

Answer 3

Radhakrishnan's entropy proof of Bregman's Theorem, that the number of perfect matchings $p$ in a bipartite graph $(L\cup R, E)$ is at most $\prod_{v \in L} (d(v)!)^{1/d(v)}$. The proof uses two very clever ideas. Here is a sketch of the proof:

• Select a perfect matching $M$ uniformly. The entropy of this variable is $H(M) = \log p$.
• For $v \in L$, let $X_v$ be the vertex in $R$ that is matched with $v$ in $M$.
• The variable $X = (X_v : v \in L)$ has the same information as $M$, so $H(M) = H(X)$.
• Clever Idea 1: By randomly (and uniformly) selecting an order $\leq$ on $L$, Radhakrishnan provides a "randomized chain rule" stating $H(X) = \sum_{v\in L} H(X_v | { X_u : u < v }, \leq)$.
• From the information in the conditions (${X_u : u < v}, \leq$) we can determine $N_v = |N(v) \setminus { X_u : u < v }|$ (roughly: the number of choices for matching $v$).
• Since $N_v$ is determined from this information, the conditioned entropy doesn't change in the equality $ H(X_v | { X_u : u < v }, \leq) = H(X_v | { X_u : u < v }, \leq, N_v)$.
• Clever Idea 2: By "forgetting" the information ${X_u : u < v}, \leq$, we can only increase the entropy: $H(X_v | { X_u : u < v }, \leq, N_v) \leq H(X_v | N_v)$.
• Crazy Fact: The variable $N_v$ is uniformly distributed on the set ${1,\dots, d(v)}$.
• Now, to compute the entropy $H(X_v | N_v)$, we sum over all values of $N_v$: $H(X_v | N_v) = \sum_{i=1}^{d(v)} \frac{1}{d(v)}H(X_v|N_v=i) \leq \frac{1}{d(v)}\sum_{i=1}^{d(v)}\log i = \log((d(v)!)^{1/d(v)}).$
• The result follows by combining all inequalities together and taking exponents.

The generalization of this inequality is the Kahn-Lovász Theorem: The number of perfect matchings in any graph $G$ is at most $\prod_{v \in V(G)} (d(v)!)^{1/2d(v)}$. An entropy proof of this result was proven by Cutler and Radcliffe.

Answer 4

Very nice examples are contained in two papers by Pippenger An Information-Theoretic Method in Combinatorial Theory. J. Comb. Theory, Ser. A 23(1): 99-104 (1977) and Entropy and enumeration of boolean functions. IEEE Transactions on Information Theory 45(6): 2096-2100 (1999). Actually, several papers by Pippenger contain cute proofs of combinatorial facts by means of entropy/mutual information. Also, the two books: Jukna, Extremal Combinatorics With Applications in Computer Science and Aigner, Combinatorial Search have some nice examples. I also like the two papers Madiman et al. Information-theoretic Inequalities in Additive Combinatorics, and Terence Tao, Entropy sumset estimates (you can find them with Google Scholar). Hope it helps.

Answer 5

Another great example is Terry Tao's alternate proof of the Szemerédi graph regularity lemma. He uses an information-theoretic perspective to prove a strong version of the regularity lemma, which turns out to be extremely useful in his proof of the regularity lemma for hypergraphs. Tao's proof is, by far, the most concise proof for the hypergraph regularity lemma.

Let me try to explain at a very high level this information-theoretic perspective.

Suppose you have a bipartite graph $G$, with the two vertex sets $V_1$ and $V_2$ and the edge set E a subset of $V_1 \times V_2$. The edge density of $G$ is $\rho = |E|/|V_1||V_2|$. We say $G$ is $\epsilon$-regular if for all $U_1 \subseteq V_1$ and $U_2 \subseteq V_2$, the edge density of the subgraph induced by $U_1$ and $U_2$ is $\rho \pm \epsilon |U_1||U_2|/|V_1||V_2|$.

Now, consider selecting a vertex $x_1$ from $V_1$ and a vertex $x_2$ from $V_2$, independently and uniformly at random. If $\epsilon$ is small and $U_1, U_2$ are large, we can interpret $\epsilon$-regularity of $G$ as saying that conditioning $x_1$ to be in $U_1$ and $x_2$ to be in $U_2$ does not affect much the probability that $(x_1,x_2)$ forms an edge in $G$. In other words, even after we are given the information that $x_1$ is in $U_1$ and $x_2$ is in $U_2$, we haven't acquired much information about whether $(x_1,x_2)$ is an edge or not.

The Szemeredi regularity lemma (informally) guarantees that for any graph, one can find a partition of $V_1$ and a partition of $V_2$ into subsets of constant density such that for most such pairs of subsets $U_1 \subset V_1, U_2 \subset V_2$, the induced subgraph on $U_1 \times U_2$ is $\epsilon$-regular. Making the above interpretation, given any two high-entropy variables $x_1$ and $x_2$, and given any event $E(x_1,x_2)$, it is possible to find low-entropy variables $U_1(x_1)$ and $U_2(x_2)$ -- "low-entropy" because the subsets $U_1$ and $U_2$ are of constant density -- such that $E$ is approximately independent of $x_1 | U_1$ and $x_2 | U_2$, or that the mutual information between the variables is very small. Tao actually formulates a much stronger version of the regularity lemma using this setup. For example, he doesn't require that $x_1$ and $x_2$ be independent variables (though there hasn't yet been an application of this generalization, as far as I know).

Answer 6

There is basically an entire course devoted to this question:

https://catalyst.uw.edu/workspace/anuprao/15415/86751

The course is still ongoing. So not all notes are available as of writing this. Also, some examples from the course were already mentioned.

Answer 7

Suppose we have $n$ points in $\ell_2^d$ and want to do a dimension reduction. If we want pairwise distances change by at most $1 \pm \epsilon$, then we can reduce our dimension from $d$ to $O(\log n / \epsilon^2)$. This is Johnson-Lindenstrauss Lemma. For a decade the best known lower bound for a dimension was $\Omega(\log n / (\epsilon^2 \log(1 / \epsilon)))$ by Alon, so there was a gap of size $\sim \log(1 / \epsilon)$. Recently, Jayram and Woodruff closed this gap by improving Alon's lower bound. Their proof barely relies on geometrical structure. What they do is they prove that if a better bound was possible, it would violate one particular communication complexity lower bound. And this bound is proved using information-theoretical tools.

Answer 8

Consider the following rather fundamental problem in the world of data structures. You have a universe of size $m$. You want to store an element $u \in [m]$ as a static data structure, so that when a user wants to know if for some $x \in [m]$ whether $x=u$, only $t$ bit probes into the data structure are needed, where $t$ is some fixed constant. The goal is to minimize the space complexity of the data structure (in terms of number of bits stored).

One can construct such a data structure of size $O(m^{1/t})$. The idea is simple. Divide the $\log m$ bits needed to describe $u$ into $t$ blocks. For each $i \in [t]$ and for each possible bistring of length $(\log m)/t$, store in the data structure whether the $i$'th block of $u$ equals that bitstring.

Now, for the lower bound. Let $X$ be an element uniformly chosen at random from $[m]$. Clearly, $H[X] = \log m$. If $X_1, \dots, X_t$ are the $t$ bits probed in the data structure (possibly adaptively) in that sequence, then: $H[X] = H[X_1] + H[X_2 | X_1] + \cdots + H[X_t | X_1, \dots, X_{t-1}] \leq t \log s$, where $s$ is the size of the data structure. This gives: $s \geq m^{1/t}$.

Tight bounds are not known if we want to store two elements and $t > 1$. See here for the best results in this direction.

Answer 9

A great example is the paper "Sorting and Entropy" by Kahn and Kim. The entropy method is used to find an algorithm that given a known poset $P$ and an unknon linear extension of $P$, find the linear extension by $O(\log |X|)$ queries where $X$ is the set of linear extensions of $P$.

Answer 10

Average-Case Analysis of Algorithms Using Kolmogorov Complexity by Jiang, Li, Vitanyi.

'Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science. In the past few years we have demonstrated that Kolmogorov complexity is an important tool for analyzing the average-case complexity of algorithms. We have developed the incompressibility method [7]. In this paper we use several simple examples to further demonstrate the power and simplicity of such method. We prove bounds on the average-case number of stacks (queues) required for sorting sequential or parallel Queueusort or Stacksort.'

See also e.g. Kolmogorov Complexity and a Triangle Problem of the Heilbronn Type.

Answer 11

The equivalence of sampling and searching by Scott Aaronson. Here he shows the equivalence of sampling and searching problem in complexity theory in regards to validity of Extended Church-Turing Thesis. Standard information theory, algorithmic information theory and Kolmogorov complexity are used in a fundamental way.

He emphasizes:
"Let us stress that we are not using Kolmogorov complexity as just a technical convenience, or as shorthand for a counting argument. Rather, Kolmogorov complexity seems essential even to define a search problem .."

Answer 12

The work of Gilmer toward Frankl's example uses information theory. A constant lower bound for the union-closed sets conjecture by Justin Gilmer

Answer 13

This one's simple and also an approximation: how many combinations of 10⁶ things out of 10⁹, allowing duplicates? The correct formula is

N = (10⁶ + 10⁹)! / (10⁶! 10⁹!) ~= 2^{11409189.141937481}

But imagine giving instructions to walk along a row of a billion buckets, dropping a million marbles into the buckets along the way. There will be ~10⁹ "step to the next bucket" instructions and 10⁶ "drop a marble" instructions. The total information is

log₂(N) ~= -10⁶ log₂(10⁶ / (10⁶ + 10⁹)) - 10⁹ log₂(10⁹ / (10⁶ + 10⁹)) ~= 11409200.432742426

which is a funny, but pretty good way to approximate the (log of the) count. I like it because it works if I forget how to do combinatorics. It's equivalent to saying that

(a+b)! / a! b! ~= (a+b)^(a+b) / a^a b^b

which is like using Stirling's approximation, canceling, and missing something.

Answer 14

A very nice recent application to give upper bounds for high-dimensional permutations by Linial and Luria is here: http://www.cs.huji.ac.il/~nati/PAPERS/hd_permutations.pdf