Compressibility and Probabilistic Proofs
Résumé
We consider several examples of probabilistic existence proofs using compressibility arguments, including some results that involve Lovász local lemma.
Communication Dans Un Congrès
Année : 2017
Alexander Shen : Connectez-vous pour contacter le contributeur
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01803530
Soumis le : mercredi 30 mai 2018-14:40:20
Dernière modification le : lundi 15 juillet 2024-11:55:13
Dates et versions
Identifiants
- HAL Id : lirmm-01803530 , version 1
- ARXIV : 1703.03342
- DOI : 10.1007/978-3-319-58741-7_11
Citer
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⟩
315
Consultations
1
Téléchargements