  The aim of this paper is to prove the achievability of several coding
problems by using sparse matrices (the maximum column weight grows
logarithmically in the block length) and maximal-likelihood (ML) coding. These
problems are the Slepian-Wolf problem, the Gel'fand-Pinsker problem, the
Wyner-Ziv problem, and the One-helps-one problem (source coding with partial
side information at the decoder). To this end, the notion of a hash property
for an ensemble of functions is introduced and it is proved that an ensemble of
$q$-ary sparse matrices satisfies the hash property. Based on this property, it
is proved that the rate of codes using sparse matrices and maximal-likelihood
(ML) coding can achieve the optimal rate.
