Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
can someone give a ref on "Another (related) example is some isoperimetric inequalities on the Boolean cube"? –  vzn Jan 5 '13 at 0:58
add comment

11 Answers 11

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.

share|improve this answer
1  
The beautiful Kolmogorov complexity proof of Moser is explained here: blog.computationalcomplexity.org/2009/06/…, but I have to admit I was looking more for an entropy/mutual-information/-calculation type of example... –  Dana Moshkovitz Nov 3 '10 at 2:02
    
There are some pretty interesting applications of Kolmogorov complexity given as answers to this question: cstheory.stackexchange.com/questions/286 –  arnab Nov 3 '10 at 4:52
    
Terry Tao also discussed Moser's argument on his blog: terrytao.wordpress.com/2009/08/05/… –  Anthony Leverrier Nov 3 '10 at 8:32
3  
Actually, in his second paper (with Tardos) you no longer need recourse to recursion. You just look for an unsatisfied clause, pick a random assignment for its variables, and iterate. That's it. For some reason the simpler algorithm (having the same analysis) hasn't stuck. –  Yuval Filmus Feb 8 '11 at 2:11
    
@DanaMoshkovitz: I don't know why this didn't occur to me to say sooner in response to your comment: Kolmogorov complexity and entropy are, in many ways, essentially equivalent. See e.g. Hammer-Romaschenko-Shen-Vershchagin: dx.doi.org/10.1006/jcss.1999.1677. For example, based on [HRSV], the proof of Shearer's Lemma in arnab's answer can be proved with essentially the same proof using Kolmogorov complexity in place of entropy. The difference is just viewpoint: K is about description length, H is about $\sum p_i \log p_i$... Sometimes one is easier/more natural than the other. –  Joshua Grochow Feb 12 at 0:30
add comment

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$.

share|improve this answer
6  
A related paper to check out is 'Hypergraphs, Entropy, and Inequalities' by Ehud Friedgut. It shows how an entropy perspective, specifically a generalized Shearer's Lemma, can easily recover many standard inequalities, and also some nonstandard, complicated-looking ones. I think it gives an illuminating perspective. Link: ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf –  Andy Drucker Nov 3 '10 at 16:42
add comment

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.

share|improve this answer
1  
Great example! A small point: When you estimate $H(X_v\mid N_v)$, you probably can only say that $H(X_v\mid N_v = i)$ is upper bounded by $\log i$. –  Srikanth Nov 3 '10 at 17:57
    
You are absolutely correct and I've edited the answer to use an inequality. –  Derrick Stolee Nov 3 '10 at 18:07
add comment

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.

share|improve this answer
    
Looks like a great reading list! –  Dana Moshkovitz Nov 3 '10 at 14:28
add comment

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).

share|improve this answer
add comment

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.

share|improve this answer
3  
nice pointer: looks like a great class. –  Suresh Venkat Nov 9 '10 at 19:56
1  
As far as I can tell, this offering is half course, with notes containing some examples that make good answers to my question, and half seminar, covering examples like communication lower bounds, extractors, parallel repetition, etc, that require much more than just information theory (here there are no notes, just links to the original papers). –  Dana Moshkovitz Nov 9 '10 at 22:18
add comment

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.

share|improve this answer
3  
Another example in metric embeddings: Regev has recently shown a very short proof of the best bounds for embedding into $\ell_1^d$, using entropy arguments. –  arnab Dec 6 '11 at 0:01
    
It seems very natural and nice that these purely geometric results were proved by TCS people! –  ilyaraz Dec 6 '11 at 0:06
add comment

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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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 .."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.