This thesis brings together a variety of results on information-theoretic characterizations of communication tasks in classical and quantum information.

We investigate shared-randomness-assisted simulation of classical point-to-point channels, which is equivalent to universal strong coordination. We also study the natural quantum generalization of this task - shared-entanglement-assisted simulation of point-to-point quantum channels. Starting with quantum state splitting as a primitive, we characterize quantum state merging, quantum source coding, and quantum channel simulation in finite blocklength settings.

Next, we investigate classical broadcast channel simulation under shared-randomness assistance between the sender and each receiver. In contrast to the elusive broadcast channel capacity problem, we show that the problem of broadcast channel simulation allows for a single-letter characterization of the asymptotic rate region. This finding together with standard bounds on the broadcast channel capacity implies that classical channel interconversion under shared-randomness assistance is asymptotically irreversible.

Moving to the quantum broadcast setting, we obtain one-shot results for state splitting by sequentially applying the point-to-point results. We cannot solve the broadcast channel simulation problem due to the longstanding open problem of joint smoothing of max-relative entropies. Instead, we define an alternative version of point-to-point channel simulation that works reliably on a subspace of the input space of the channel. In the asymptotic limit, we can choose the ratio of the dimension of the subspace and the dimension of the entire input space of the channel to be arbitrarily close to 1. Operationally, this simulation cost bounds the rate of a randomly chosen entanglement-assisted coding scheme with high probability.

The final part of the thesis deals with efficient algorithms to compute the information-theoretic quantities one obtains in the asymptotic limit for various operational tasks. We provide quantum versions of the well-known Blahut-Arimoto algorithms and show that these iterative algorithms can efficiently compute optimization problems involving entropic quantities.