A string $p$ is called a program to compute $y$ given $x$ if $U(p,x)=y$, where $U$ denotes universal programming language. Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$ is defined as minimum length of a program to compute $y$ given $x$. Let $K(x)$ denote $K(x|\text{empty string})$ (Kolmogorov complexity of $x$) ... more >>>

We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate a value with distribution exactly D. Alice and Bob are allowed to share random bits generated ... more >>>