Lossy broadcasting with complementary side information

A pair of strings (X,Y) put out by a memoryless source needs to be reliably communicated over a memoryless broadcast channel. Receiver 1 has Y as side information and must reconstruct X to within some distortion. Receiver 2 has X and must reconstruct Y to within some distortion. The problem is motivated by the broadcast phase (downlink) of the two-way relay channel. We characterize reliable communication for Gaussian sources with quadratic distortion functions; conditionally independent sources; deterministic distortion functions; and small distortions with Hamming distortion functions. The last result is obtained by solving a new version of the broadcast problem with Steinberg's common-reconstruction decoding constraint.