  Following initial work by Gregoratti and Werner [J. Mod. Optics 50, 913-933,
2003 and quant-ph/0403092] and Hayden and King [quant-ph/0409026], we study the
problem of the capacity of a quantum channel assisted by a "friendly (channel)
environment" that can locally measure and communicate classical messages to the
receiver.
  Previous work [quant-ph/0505038] has yielded a capacity formula for the
quantum capacity under this kind of help from the environment. Here we study
the problem of the environment-assisted classical capacity, which exhibits a
somewhat richer structure (at least, it seems to be the harder problem). There
are several, presumably inequivalent, models of the permitted local operations
and classical communications between receiver and environment: one-way,
arbitrary, separable and PPT POVMs. In all these models, the task of decoding a
message amounts to discriminating a set of possibly entangled states between
the two receivers, by a class of operations under some sort of locality
constraint.
  After introducing the operational capacities outlined above, we show that a
lower bound on the environment-assisted classical capacity is always half the
logarithm of the input space dimension. Then we develop a few techniques to
prove the existence of channels which meet this lower bound up to terms of much
smaller order, even when PPT decoding measurements are allowed (assuming a
certain superadditivity conjecture).
