Probabilistic constructions of computable objects and a computable version of Lovász local lemma

DOI10.3233/FI-2014-1029MaRDI QIDQ2934869zbMATH OpenOpenAlexWikidataFDO

Authors A. Yu. Rumyantsev, A. Shen

Publication date 22 December 2014

Published in Fundamenta Informaticae (Search for Journal in Brave)

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)

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.)

Recommendations

• A constructive proof of the general Lovász local lemma
• scientific article; zbMATH DE number 1775440
• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• Algorithmic improvements of the Lovász local lemma via cluster expansion

Cited in

(14)

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

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)