Compressibility and probabilistic proofs

DOI10.1007/978-3-319-58741-7_11MaRDI QIDQ2011640zbMATH OpenOpenAlexFDO

Authors A. Shen

Publication date 4 August 2017

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)

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

Cites work

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

Cited in

(3)

• scientific article; zbMATH DE number 1998343 (Why is no real title available?)
• 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)