  For general memoryless systems, the typical information theoretic solution -
when exists - has a "single-letter" form. This reflects the fact that optimum
performance can be approached by a random code (or a random binning scheme),
generated using independent and identically distributed copies of some
single-letter distribution. Is that the form of the solution of any
(information theoretic) problem? In fact, some counter examples are known. The
most famous is the "two help one" problem: Korner and Marton showed that if we
want to decode the modulo-two sum of two binary sources from their independent
encodings, then linear coding is better than random coding. In this paper we
provide another counter example, the "doubly-dirty" multiple access channel
(MAC). Like the Korner-Marton problem, this is a multi-terminal scenario where
side information is distributed among several terminals; each transmitter knows
part of the channel interference but the receiver is not aware of any part of
it. We give an explicit solution for the capacity region of a binary version of
the doubly-dirty MAC, demonstrate how the capacity region can be approached
using a linear coding scheme, and prove that the "best known single-letter
region" is strictly contained in it. We also state a conjecture regarding a
similar rate loss of single letter characterization in the Gaussian case.
