Skip to Main content Skip to Navigation
Conference papers

Compressibility and Probabilistic Proofs

Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We consider several examples of probabilistic existence proofs using compressibility arguments, including some results that involve Lovász local lemma.
Document type :
Conference papers
Complete list of metadata
Contributor : Alexander Shen <>
Submitted on : Wednesday, May 30, 2018 - 2:40:20 PM
Last modification on : Friday, May 21, 2021 - 8:22:02 PM




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⟩