  We study the complexity of the Channel Assignment problem. By applying the
meet-in-the-middle approach we get an algorithm for the $\ell$-bounded Channel
Assignment (when the edge weights are bounded by $\ell$) running in time
$O^*((2\sqrt{\ell+1})^n)$. This is the first algorithm which breaks the
$(O(\ell))^n$ barrier. We extend this algorithm to the counting variant, at the
cost of slightly higher polynomial factor.
  A major open problem asks whether Channel Assignment admits a $O(c^n)$-time
algorithm, for a constant $c$ independent of $\ell$. We consider a similar
question for Generalized T-Coloring, a CSP problem that generalizes \CA. We
show that Generalized T-Coloring does not admit a
$2^{2^{o\left(\sqrt{n}\right)}} {\rm poly}(r)$-time algorithm, where $r$ is the
size of the instance.
