<p>Moser's proof of the <a href="http://dx.doi.org/10.1145/1536414.1536462">constructive Lovasz Local Lemma</a>.  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.</p>

CC BY-SA 3.0
2014-02-12T00:30:10.867Z
@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: http://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
CC BY-SA 2.5
2010-11-03T02:02:51.057Z
The beautiful Kolmogorov complexity proof of Moser is explained here: http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html, but I have to admit I was looking more for an entropy/mutual-information/-calculation type of example...
Dana Moshkovitz
CC BY-SA 2.5
2010-11-03T04:52:00.367Z
There are some pretty interesting applications of Kolmogorov complexity given as answers to this question: http://cstheory.stackexchange.com/questions/286/
arnab
CC BY-SA 2.5
2010-11-03T08:32:36.757Z
Terry Tao also discussed Moser's argument on his blog: http://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression-argument/
Anthony Leverrier
CC BY-SA 2.5
2011-02-08T02:11:19.770Z
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
CC BY-SA 2.5
2010-11-03T01:55:06.330Z
2010-11-03T01:55:06.330Z
Joshua Grochow
<p>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 <a href="http://www.tcs.tifr.res.in/~jaikumar/Papers/EntropyAndCounting.pdf">Entropy and Counting</a>.)</p>

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

<p>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.  </p>

<p>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.</p>

<p>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$).</p>

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

CC BY-SA 2.5
2010-11-03T16:42:15.280Z
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:   http://www.ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf
Andy Drucker
CC BY-SA 2.5
2010-11-03T02:45:48.833Z
2010-11-03T02:45:48.833Z
arnab
<p>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.</p>

CC BY-SA 2.5
2010-11-03T14:28:26.327Z
Looks like a great reading list!
Dana Moshkovitz
CC BY-SA 2.5
2010-11-03T13:37:35.260Z
2010-11-03T13:37:35.260Z
Ugo
<p>Another great example is Terry Tao's <a href="http://arxiv.org/abs/math/0504472">alternate proof of the Szemerédi graph regularity lemma</a>.  He uses an information-theoretic perspective to prove a strong version of the regularity lemma, which turns out to be extremely useful in <a href="http://arxiv.org/abs/math.CO/0503572">his proof of the regularity lemma for hypergraphs</a>.  Tao's proof is, by far, the most concise proof for the hypergraph regularity lemma.</p>

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

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

<p>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.</p>

<p>The Szemeredi regularity lemma (informally) guarantees that for <em>any</em> 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).  </p>

CC BY-SA 2.5
2010-11-09T03:14:53.683Z
2010-11-09T03:57:54.460Z
2010-11-09T03:57:54.460Z
arnab
<p><a href="http://www.ingentaconnect.com/content/ap/ta/1997/00000077/00000001/art02727?crawler=true">Radhakrishnan's entropy proof</a> 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:</p>

<ul>
<li>Select a perfect matching $M$ uniformly.  The entropy of this variable is $H(M) = \log p$.</li>
<li>For $v \in L$, let $X_v$ be the vertex in $R$ that is matched with $v$ in $M$.</li>
<li>The variable $X = (X_v : v \in L)$ has the same information as $M$, so $H(M) = H(X)$.</li>
<li><strong>Clever Idea 1:</strong> 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 &lt; v }, \leq)$.</li>
<li>From the information in the conditions (${X_u : u &lt; v}, \leq$) we can determine $N_v = |N(v) \setminus { X_u : u &lt; v }|$ (roughly: the number of choices for matching $v$).</li>
<li>Since $N_v$ is determined from this information, the conditioned entropy doesn't change in the equality $ H(X_v | { X_u : u &lt; v }, \leq) =  H(X_v | { X_u : u &lt; v }, \leq, N_v)$.</li>
<li><strong>Clever Idea 2:</strong> By "forgetting" the information ${X_u : u &lt; v}, \leq$, we can only increase the entropy: $H(X_v | { X_u : u &lt; v }, \leq, N_v) \leq H(X_v | N_v)$.</li>
<li><strong>Crazy Fact:</strong> The variable $N_v$ is uniformly distributed on the set ${1,\dots, d(v)}$.</li>
<li>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)}).$</li>
<li>The result follows by combining all inequalities together and taking exponents.</li>
</ul>

<p>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 <a href="http://www.math.unl.edu/~aradcliffe1/Papers/kahnlovasz.pdf">Cutler and Radcliffe</a>.</p>

CC BY-SA 2.5
2010-11-03T17:57:20.960Z
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
CC BY-SA 2.5
2010-11-03T18:07:14.413Z
You are absolutely correct and I've edited the answer to use an inequality.
Derrick Stolee
CC BY-SA 2.5
2010-11-03T16:54:32.430Z
2010-11-03T18:06:52.120Z
2010-11-03T18:06:52.120Z
Derrick Stolee
<p>There is basically an entire course devoted to this question:</p>

<p><a href="https://catalyst.uw.edu/workspace/anuprao/15415/86751">https://catalyst.uw.edu/workspace/anuprao/15415/86751</a></p>

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

CC BY-SA 2.5
2010-11-09T19:56:02.037Z
nice pointer: looks like a great class.
Suresh Venkat
CC BY-SA 2.5
2010-11-09T22:18:13.390Z
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
CC BY-SA 2.5
2010-11-09T19:12:14.327Z
2010-11-09T19:12:14.327Z
Moritz
<p>Suppose we have <span class="math-container">$n$</span> points in <span class="math-container">$\ell_2^d$</span> and want to do a dimension reduction. If we want pairwise distances change by at most <span class="math-container">$1 \pm \epsilon$</span>, then we can reduce our dimension from <span class="math-container">$d$</span> to <span class="math-container">$O(\log n / \epsilon^2)$</span>. This is <a href="https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma" rel="nofollow noreferrer">Johnson-Lindenstrauss Lemma</a>. For a decade the best known <em>lower bound</em> for a dimension was <span class="math-container">$\Omega(\log n / (\epsilon^2 \log(1 / \epsilon)))$</span> by Alon, so there was a gap of size <span class="math-container">$\sim \log(1 / \epsilon)$</span>. Recently, Jayram and Woodruff <a href="https://web.archive.org/web/20110107060947/http://www.almaden.ibm.com/cs/people/dpwoodru/jw11.pdf" rel="nofollow noreferrer">closed</a> 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.</p>

CC BY-SA 3.0
2011-12-06T00:01:21.543Z
Another example in metric embeddings: Regev [has recently shown](http://arxiv.org/abs/1108.1283) a very short proof of the best bounds for embedding into $\ell_1^d$, using entropy arguments.
arnab
CC BY-SA 3.0
2011-12-06T00:06:35.427Z
It seems very natural and nice that these purely geometric results were proved by TCS people!
ilyaraz
CC BY-SA 4.0
2011-12-05T23:50:22.427Z
2022-07-15T11:02:44.000Z
2022-07-15T11:02:44.000Z
ilyaraz
<p>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).</p>

<p>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. </p>

<p>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}$.</p>

<p>Tight bounds are not known if we want to store two elements and $t &gt; 1$.  See <a href="http://dx.doi.org/10.1007/978-3-642-15781-3_14">here</a> for the best results in this direction.</p>

CC BY-SA 2.5
2011-02-05T06:59:43.723Z
2011-02-06T15:54:07.260Z
2011-02-06T15:54:07.260Z
arnab
<p>A great example is the paper "<a href="http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/papers/entropy.pdf" rel="nofollow">Sorting and Entropy</a>" 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$. </p>

CC BY-SA 3.0
2012-12-28T07:15:04.583Z
2012-12-28T09:18:06.950Z
2012-12-28T09:18:06.950Z
Gil Kalai
<p><a href="http://scholar.google.com/scholar?cluster=15743380286314506869&amp;hl=en&amp;as_sdt=0,5" rel="nofollow">Average-Case Analysis of Algorithms Using Kolmogorov Complexity</a> by Jiang, Li, Vitanyi. </p>

<p>'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.' </p>

<p>See also e.g. <a href="http://scholar.google.com/scholar?cluster=15703903265451195965&amp;hl=en&amp;as_sdt=0,5" rel="nofollow">Kolmogorov Complexity and a Triangle Problem of the Heilbronn Type</a>.</p>

CC BY-SA 3.0
2012-12-30T06:55:29.897Z
2012-12-30T06:55:29.897Z
Neal Young
<p><a href="http://arxiv.org/abs/1009.5104" rel="nofollow">The equivalence of sampling and searching</a> 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.  </p>

<p>He emphasizes:<br>
"<em>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 ..</em>"</p>

CC BY-SA 3.0
2012-12-31T06:08:40.063Z
2012-12-31T06:08:40.063Z
DurgaDatta
<p>The work of Gilmer toward Frankl's example uses information theory. <a href="https://arxiv.org/abs/2211.09055" rel="nofollow noreferrer">A constant lower bound for the union-closed sets conjecture</a> by Justin Gilmer</p>

CC BY-SA 4.0
2022-12-22T09:07:26.217Z
2022-12-22T09:07:26.217Z
Gil Kalai
<p>This one's simple and also an approximation: how many combinations of 10<sup>6</sup> things out of 10<sup>9</sup>, allowing duplicates?  The correct formula is</p>

<blockquote>
  <p>N = (10<sup>6</sup> + 10<sup>9</sup>)! / (10<sup>6</sup>! 10<sup>9</sup>!) ~= 2<sup>11409189.141937481</sup></p>
</blockquote>

<p>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<sup>9</sup> "step to the next bucket" instructions and 10<sup>6</sup> "drop a marble" instructions.  The total information is</p>

<blockquote>
  <p>log<sub>2</sub>(N) ~= -10<sup>6</sup> log<sub>2</sub>(10<sup>6</sup> / (10<sup>6</sup> + 10<sup>9</sup>)) - 10<sup>9</sup> log<sub>2</sub>(10<sup>9</sup> / (10<sup>6</sup> + 10<sup>9</sup>)) ~= 11409200.432742426</p>
</blockquote>

<p>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 </p>

<blockquote>
  <p>(a+b)! / a! b!  ~=  (a+b)<sup>(a+b)</sup> / a<sup>a</sup> b<sup>b</sup></p>
</blockquote>

<p>which is like using Stirling's approximation, canceling, and missing something.</p>

CC BY-SA 3.0
2014-08-28T21:52:49.467Z
This may be more readable if you do the general bound rather than specific numbers. I think you are talking about the entropy-based approximation of the volume of a Hamming ball.
Sasho Nikolov
CC BY-SA 3.0
2014-08-28T20:32:53.713Z
2014-08-28T20:32:53.713Z
FutureNerd
<p>A very nice recent application to give upper bounds for high-dimensional permutations by Linial and Luria is here: <a href="http://www.cs.huji.ac.il/~nati/PAPERS/hd_permutations.pdf" rel="nofollow">http://www.cs.huji.ac.il/~nati/PAPERS/hd_permutations.pdf</a></p>

CC BY-SA 3.0
2014-11-27T20:02:13.577Z
2014-11-27T20:02:13.577Z
Gil Kalai
<p>What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?</p>

<p>Some examples I can think of are related to lower bounds for locally decodable codes, e.g., in <a href="http://www.wisdom.weizmann.ac.il/~oded/p_2q-ldc.html">this</a> 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$. </p>

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

<p>Do you have more nice examples? Preferably, short and easy to explain.</p>

CC BY-SA 3.0
2013-01-05T00:58:50.290Z
can someone give a ref on "Another (related) example is some isoperimetric inequalities on the Boolean cube"?
vzn
<co.combinatorics><big-list><it.information-theory>
Information Theory used to prove neat combinatorial statements?
Dana Moshkovitz
# Information Theory used to prove neat combinatorial statements?

(Asked by: username_0 on 2010-11-03)

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](http://www.wisdom.weizmann.ac.il/~oded/p_2q-ldc.html) 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.

**Tags:** co.combinatorics, big-list, it.information-theory
> **Comments:**
> **username_1**: can someone give a ref on "Another (related) example is some isoperimetric inequalities on the Boolean cube"?  

---

## 14 answers

### Answer by username_2 on 2010-11-03. Score: 43

Moser's proof of the [constructive Lovasz Local Lemma](http://dx.doi.org/10.1145/1536414.1536462). 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.

> **Comments:**
> **username_0**: The beautiful Kolmogorov complexity proof of Moser is explained here: http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html, but I have to admit I was looking more for an entropy/mutual-information/-calculation type of example...  
> **username_3**: There are some pretty interesting applications of Kolmogorov complexity given as answers to this question: http://cstheory.stackexchange.com/questions/286/  
> **username_4**: Terry Tao also discussed Moser's argument on his blog: http://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression-argument/  
> **username_5**: 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.  
> **username_2**: @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: http://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.  

---

### Answer by username_3 on 2010-11-03. Score: 37

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](http://www.tcs.tifr.res.in/~jaikumar/Papers/EntropyAndCounting.pdf).)

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

> **Comments:**
> **username_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:   http://www.ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf  

---

### Answer by username_8 on 2010-11-03. Score: 26

[Radhakrishnan's entropy proof](http://www.ingentaconnect.com/content/ap/ta/1997/00000077/00000001/art02727?crawler=true) 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](http://www.math.unl.edu/~aradcliffe1/Papers/kahnlovasz.pdf).

> **Comments:**
> **username_9**: 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$.  
> **username_8**: You are absolutely correct and I've edited the answer to use an inequality.  

---

### Answer by username_7 on 2010-11-03. Score: 21

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.

> **Comments:**
> **username_0**: Looks like a great reading list!  

---

### Answer by username_3 on 2010-11-09. Score: 18

Another great example is Terry Tao's [alternate proof of the Szemerédi graph regularity lemma](http://arxiv.org/abs/math/0504472). 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](http://arxiv.org/abs/math.CO/0503572). 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 by username_10 on 2010-11-09. Score: 15

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.

> **Comments:**
> **username_11**: nice pointer: looks like a great class.  
> **username_0**: 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).  

---

### Answer by username_12 on 2011-12-05. Score: 8

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](https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_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](https://web.archive.org/web/20110107060947/http://www.almaden.ibm.com/cs/people/dpwoodru/jw11.pdf) 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.

> **Comments:**
> **username_3**: Another example in metric embeddings: Regev [has recently shown](http://arxiv.org/abs/1108.1283) a very short proof of the best bounds for embedding into $\ell_1^d$, using entropy arguments.  
> **username_12**: It seems very natural and nice that these purely geometric results were proved by TCS people!  

---

### Answer by username_3 on 2011-02-05. Score: 6

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](http://dx.doi.org/10.1007/978-3-642-15781-3_14) for the best results in this direction.


---

### Answer by username_13 on 2012-12-28. Score: 6

A great example is the paper "[Sorting and Entropy](http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/papers/entropy.pdf)" 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 by username_14 on 2012-12-30. Score: 4

[Average-Case Analysis of Algorithms Using Kolmogorov Complexity](http://scholar.google.com/scholar?cluster=15743380286314506869&hl=en&as_sdt=0,5) 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](http://scholar.google.com/scholar?cluster=15703903265451195965&hl=en&as_sdt=0,5).


---

### Answer by username_15 on 2012-12-31. Score: 4

[The equivalence of sampling and searching](http://arxiv.org/abs/1009.5104) 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 by username_13 on 2022-12-22. Score: 2

The work of Gilmer toward Frankl's example uses information theory. [A constant lower bound for the union-closed sets conjecture](https://arxiv.org/abs/2211.09055) by Justin Gilmer


---

### Answer by username_16 on 2014-08-28. Score: 0

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

> N = (106 + 109)! / (106! 109!) ~= 211409189.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 ~109 "step to the next bucket" instructions and 106 "drop a marble" instructions. The total information is

> log2(N) ~= -106 log2(106 / (106 + 109)) - 109 log2(109 / (106 + 109)) ~= 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) / aa bb

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

> **Comments:**
> **username_17**: This may be more readable if you do the general bound rather than specific numbers. I think you are talking about the entropy-based approximation of the volume of a Hamming ball.  

---

### Answer by username_13 on 2014-11-27. Score: 0

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>


---

