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 2017 - 13th Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.101-111, ⟨10.1007/978-3-319-58741-7_11⟩. ⟨lirmm-01803530⟩
303 View
1 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More