  We address the problem of coding for classical broadcast channels, which
entails maximizing the success probability that can be achieved by sending a
fixed number of messages over a broadcast channel. For point-to-point channels,
Barman and Fawzi found in~\cite{BF18} a $(1-e^{-1})$-approximation algorithm
running in polynomial time, and showed that it is \textrm{NP}-hard to achieve a
strictly better approximation ratio. Furthermore, these algorithmic results
were at the core of the limitations they established on the power of
non-signaling assistance for point-to-point channels. It is natural to ask if
similar results hold for broadcast channels, exploiting links between
approximation algorithms of the channel coding problem and the non-signaling
assisted capacity region.
  In this work, we make several contributions on algorithmic aspects and
non-signaling assisted capacity regions of broadcast channels. For the class of
deterministic broadcast channels, we describe a $(1-e^{-1})^2$-approximation
algorithm running in polynomial time, and we show that the capacity region for
that class is the same with or without non-signaling assistance. Finally, we
show that in the value query model, we cannot achieve a better approximation
ratio than $\Omega\left(\frac{1}{\sqrt{m}}\right)$ in polynomial time for the
general broadcast channel coding problem, with $m$ the size of one of the
outputs of the channel.
