A Caltech Library Service

Oblivious channels

Langberg, Michael (2006) Oblivious channels. In: 2006 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, pp. 2739-2743. ISBN 1-4244-0505-X.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Let C = {x_1,...,x_N} ⊂ {0, 1}^n be an [n, N] binary error correcting code (not necessarily linear). Let e ∈ {0, 1}^n be an error vector. A codeword X ∈ C is said to be disturbed by the error e if the closest codeword to X ⴲ e is no longer x. Let A_e be the subset of codewords in C that are disturbed by e. In this work we study the size of A_e in random codes C (i.e. codes in which each codeword x_i is chosen uniformly and independently at random from {0, 1}^n). Using recent results of Vu [random structures and algorithms 20(3)] on the concentration of non-Lipschitz functions, we show that |A_e| is strongly concentrated for a wide range of values of N and ‖e‖. We apply this result in the study of communication channels we refer to as oblivious. Roughly speaking, a channel W(y|x) is said to be oblivious if the error distribution imposed by the channel is independent of the transmitted codeword x. For example, the well studied binary symmetric channel is an oblivious channel. In this work, we define oblivious and partially oblivious channels and present lower bounds on their capacity. The oblivious channels we define have connections to arbitrarily varying channels with state constraints.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Additional Information:© 2006 IEEE. I would like to thank Sidharth Jaggi for several helpful discussions and comments on the oblivious channel model. Research supported in part by NSF grant CCF-0346991.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20170509-171630900
Persistent URL:
Official Citation:M. Langberg, "Oblivious channels," 2006 IEEE International Symposium on Information Theory, Seattle, WA, 2006, pp. 2739-2743. doi: 10.1109/ISIT.2006.261560
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:77321
Deposited On:16 May 2017 20:56
Last Modified:15 Nov 2021 17:30

Repository Staff Only: item control page