In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for
solving the integer least-squares problem. In digital communication the problem
is equivalent to performing Maximum Likelihood (ML) detection in Multiple-Input
Multiple-Output (MIMO) systems. While the use of MCMC methods for such problems
has already been proposed, our method is novel in that we optimize the
"temperature" parameter so that in steady state, i.e. after the Markov chain
has mixed, there is only polynomially (rather than exponentially) small
probability of encountering the optimal solution.

It is well known that there is a one-to-one correspondence between the
entropy vector of a collection of n random variables and a certain
group-characterizable vector obtained from a finite group and n of its
subgroups. However, if one restricts attention to abelian groups then not all
entropy vectors can be obtained. This is an explanation for the fact shown by
Dougherty et al that linear network codes cannot achieve capacity in general
network coding problems (since linear network codes form an abelian group).