Compressibility and Probabilistic Proofs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2017

Compressibility and Probabilistic Proofs

Alexander Shen

Abstract

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

Dates and versions

lirmm-01803530 , version 1 (30-05-2018)

Identifiers

Cite

Alexander Shen. Compressibility and Probabilistic Proofs. CIE: Computability in Europe, Jun 2017, Turku, Finland. pp.101-111, ⟨10.1007/978-3-319-58741-7_11⟩. ⟨lirmm-01803530⟩
302 View
1 Download

Altmetric

Share

Gmail Facebook X LinkedIn More