Compressibility and Probabilistic Proofs
Abstract
We consider several examples of probabilistic existence proofs using compressibility arguments, including some results that involve Lovász local lemma.
Conference Papers
Year : 2017
Alexander Shen : Connect in order to contact the contributor
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01803530
Submitted on : Wednesday, May 30, 2018-2:40:20 PM
Last modification on : Monday, July 15, 2024-11:55:13 AM
Dates and versions
Identifiers
- HAL Id : lirmm-01803530 , version 1
- ARXIV : 1703.03342
- DOI : 10.1007/978-3-319-58741-7_11
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⟩
309
View
1
Download