Channels with nosy "noise"
Proceedings of the 2007 Infernational Symposium on Information Theory (ISIT 2007), Nice, France, June 2007.
Download
The version of the paper here is a corrected version of the
paper that appeared in the Proceedings.
Adobe Portable Document Format - [PDF]
PostScript - [PS]
Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Abstract
Coding over channels whose state can depend non-causally on the entire transmitted codeword and message are studied. The channel model is a variation on the arbitrarily varying channel (AVC) with state constraints. The randomized coding capacity of this channel is shown to be equal to the minimum of the capacities of channels in the row-convex closure of the AVC. Common randomness of $O(\log n)$ bits is sufficient to achieve this capacity.
Notes
The version of this paper that appeared in the proceedings of the conference has a rather significant error. A corrected version is posted here with the error fixed.