  In this paper we investigate the extent to which the Lov\'asz Local Lemma (an
important tool in probabilistic combinatorics) can be adapted for the
measurable setting. In most applications, the Lov\'asz Local Lemma is used to
produce a function $f \colon X \to Y$ with certain properties, where $X$ is
some underlying combinatorial structure and $Y$ is a (typically finite) set.
Can this function $f$ be chosen to be Borel or $\mu$-measurable for some
probability Borel measure $\mu$ on $X$ (assuming that $X$ is a standard Borel
space)? In the positive direction, we prove that if the set of constraints put
on $f$ is, in a certain sense, "locally finite," then there is always a Borel
choice for $f$ that is "$\varepsilon$-close" to satisfying these constraints,
for any $\varepsilon > 0$. Moreover, if the combinatorial structure on $X$ is
"induced" by the $[0;1]$-shift action of a countable group $\Gamma$, then, even
without any local finiteness assumptions, there is a Borel choice for $f$ which
satisfies the constraints on an invariant conull set (i.e., with $\varepsilon =
0$). A direct corollary of our results is an upper bound on the measurable
chromatic number of the graph $G_n$ generated by the shift action of the free
group $\mathbb{F}_n$ that is asymptotically tight up to a factor of at most $2$
(which answers a question of Lyons and Nazarov). On the other hand, our result
for structures induced by measure-preserving group actions is, at least for
amenable groups, sharp in the following sense: a probability measure-preserving
action of a countably infinite amenable group satisfies the measurable version
of the Lov\'asz Local Lemma if and only if it admits a factor map to the
$[0;1]$-shift action. To prove this, we combine the tools of the
Ornstein--Weiss theory of entropy for actions of amenable groups with concepts
from computability theory, specifically, Kolmogorov complexity.
