Entropy compression

In mathematics and theoretical computer science, entropy compression is an information theoretic method for proving that a random process terminates, originally used by Robin Moser to prove an algorithmic version of the Lovász local lemma.

Description

To use this method, one proves that the history of the given process can be recorded in an efficient way, such that the state of the process at any past time can be recovered from the current state and this record, and such that the amount of additional information that is recorded at each step of the process is (on average) less than the amount of new information randomly generated at each step. The resulting growing discrepancy in total information content can never exceed the fixed amount of information in the current state, from which it follows that the process must eventually terminate. This principle can be formalized and made rigorous using Kolmogorov complexity.

Example

An example given by both Fortnow and Tao concerns the Boolean satisfiability problem for Boolean formulas in conjunctive normal form, with uniform clause size. These problems can be parameterized by two numbers $(k,t)$ where $k$ is the number of variables per clause and $t$ is the maximum number of different clauses that any variable can appear in. If the variables are assigned to be true or false randomly, then the event that a clause is unsatisfied happens with probability $2^{-k}$ and each event is independent of all but $r=k(t-1)$ other events. It follows from the Lovász local lemma that, if $t$ is small enough to make $r<2^{k}/e$ (where $e$ is the base of the natural logarithm) then a solution always exists. The following algorithm can be shown using entropy compression to find such a solution for inputs that obey a constraint on $r$ of a similar form.

• Choose a random truth assignment
• While there exists an unsatisfied clause $C$, call a recursive subroutine fix with $C$ as its argument. This subroutine chooses a new random truth assignment for the variables in $C$, and then recursively calls the same subroutine on all unsatisfied clauses (possibly including $C$ itself) that share a variable with $C$, until none are left.

This algorithm cannot terminate unless the input formula is satisfiable, so a proof that it terminates is also a proof that a solution exists. Each iteration of the outer loop reduces the number of unsatisfied clauses (it causes $C$ to become satisfied without making any other clause become unsatisfied) so the key question is whether the fix subroutine terminates or whether it can get into an infinite recursion.

To answer this question, consider on the one hand the number of random bits generated in each iteration of the fix subroutine ($k$ bits per clause) and on the other hand the number of bits needed to record the history of this algorithm in such a way that any past state can be generated. To record this history, we may store the current truth assignment ($n$ bits), the sequence of arguments to the outermost calls to the fix subroutine (at most $m\log _{2}m$ bits, where $m$ is the number of clauses in the input), and then a sequence of records that either indicate that a recursive call to fix returned or that it made a recursive call, and which of the $r+1$ clauses sharing a variable with the current clause was passed as an argument to that recursive call. There are $r+2$ possible outcomes per record, so the number of bits needed to store a record (using a compact encoding method such as arithmetic coding that allows storage using a fractional number of bits per record) is $\log _{2}(r+2)$.

This information is enough to recover the entire sequence of calls to fix, including the identity of the clause given as an argument to each call. To do so, progress forward through the call sequence using the stored outermost call arguments and stored records to infer the argument of each call in turn. Once the sequence of recursive calls and their arguments has been recovered, the truth assignments at each stage of this process can also be recovered from the same information. To do so, start from the final truth assignment and then progress backwards through the sequence of randomly reassigned clauses, using the fact that each clause was previously unsatisfiable to uniquely determine the values of all of its variables prior to its random reassignment. Thus, after $f$ calls to fix, the algorithm will have generated $fk$ random bits but its entire history (including those generated bits) can be recovered from a record that uses only $m\log _{2}m+n+f\log _{2}(r+2)$ bits. This is only possible when the number of stored bits is at least as large as the number of randomly generated bits. It follows that, when $r$ is small enough to make $\log _{2}(r+2)<k$, that is, when $r<2^{k}-2$, the fix subroutine can only perform $O(m\log _{2}m+n)$ recursive calls over the course of the whole algorithm.

History

The name "entropy compression" was given to this method in a blog posting by Terence Tao and has since been used for it by other researchers.

Moser's original version of the algorithmic Lovász local lemma, using this method, achieved weaker bounds than the original Lovász local lemma, which was originally formulated as an existence theorem without a constructive method for finding the object whose existence it proves. Later, Moser and Gábor Tardos used the same method to prove a version of the algorithmic Lovász local lemma that matches the bounds of the original lemma.

Since the discovery of the entropy compression method, it has also been used to achieve stronger bounds for some problems than would be given by the Lovász local lemma. For example, for the problem of acyclic edge coloring of graphs with maximum degree $\Delta$, it was first shown using the local lemma that there always exists a coloring with $64\Delta$ colors, and later using a stronger version of the local lemma this was improved to $9.62\Delta$. However, a more direct argument using entropy compression shows that there exists a coloring using only $4\Delta -4$ colors, and moreover this coloring can be found in randomized polynomial time.