Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma

DOI10.3233/FI-2014-1029zbMATH Open1317.68131arXiv1305.1535OpenAlexW1813874586WikidataQ124887239 ScholiaQ124887239MaRDI QIDQ2934869FDOQ2934869

A. Yu. Rumyantsev, A. Shen

Publication date: 22 December 2014

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appears with some positive probability in some random process. Can we use such arguments to prove the existence of a computable infinite object? Sometimes yes: following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lov'asz local lemma. (A survey of Moser-Tardos proof is included to make the paper self-contained.)

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

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (14)

• Measurable versions of the Lovász local lemma and measurable graph colorings
• Effectiveness of Hindman’s Theorem for Bounded Sums
• DEGREES OF RANDOMIZED COMPUTABILITY
• Constructive equivalence relations on computable probability measures
• A computable analysis of variable words theorems
• On the uniform computational content of the Baire category theorem
• Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
• Computable Measure Theory and Algorithmic Randomness
• Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem
• Thin set versions of Hindman's theorem
• Layerwise computability and image randomness
• Equivariant maps to subshifts whose points have small stabilizers
• ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY
• Diagonally non-computable functions and fireworks

This page was built for publication: Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma

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