Alexander Shen

Compressibility and probabilistic proofs

Abstract:

We consider several examples of probabilistic existence proofs using compressibility arguments, including some results that involve Lovasz local lemma.