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

DOI10.3233/FI-2014-1029zbMath1317.68131arXiv1305.1535OpenAlexW1813874586WikidataQ124887239 ScholiaQ124887239MaRDI QIDQ2934869

A. Yu. Rumyantsev, Alexander 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

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

Related Items (13)

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

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