Compressibility and probabilistic proofs

DOI10.1007/978-3-319-58741-7_11zbMATH Open1489.68097arXiv1703.03342OpenAlexW2597515791MaRDI QIDQ2011640FDOQ2011640

Authors: A. Shen 

Publication date: 4 August 2017

Abstract: We consider several examples of probabilistic existence proofs using compressibility arguments, including some results that involve Lov'asz local lemma.

Full work available at URL: https://arxiv.org/abs/1703.03342

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• A constructive proof of the general Lovász local lemma
• Further applications of a power series method for pattern avoidance
• Application of entropy compression in pattern avoidance
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• Two notes on subshifts

Cited In (3)

• Title not available (Why is that?)
• Compressibility and resource bounded measure
• Compressibility and resource bounded measure

This page was built for publication: Compressibility and probabilistic proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011640)