Compressibility and probabilistic proofs

2017/03/09 by Alexander Shen, Shen, Alexander
Computer Science · #Computability, Logic, AI Algorithms #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.1703.03342

Abstract

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

Related

• An introduction to the probabilistic method through the Lovász Local Lemma
• Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
• Infinite computable version of Lovasz Local Lemma
• The Local Action Lemma
• A local lemma via entropy compression