Information and Coding Theory Seminar  

Abstracts of talks

Fall 2010

09/23 Dr. Maxim Raginsky (Duke University), Empirical Processes, Typical Sequences and Coordinated Actions in Standard Borel Spaces

Recent work by Cuff, Permuter and Cover on coordination via communication has revealed a fascinating aspect of strongly typical sequences --- they can be thought of as a means of reproducing relative frequencies of symbols emitted by stationary memoryless sources using finite communication resources. This viewpoint has a number of useful and far-reaching implications in such settings as distributed control and decision-making, network security, and statistical learning. However, strong typicality, as it pertains to approximating source distributions by relative frequencies in the sense of total variation, is not appropriate for continuous alphabet sources. In this talk, I will present a generalization of typicality that works for a wide class of abstract alphabets (so-called standard Borel spaces, which include all conceivable alphabets of practical interest). This new notion makes fundamental use of an object known in modern mathematical statistics as the empirical process, which is used to characterize the fluctuations of sample averages of functions in a given class around their true expectations. The proposed new notion of typicality possesses a minimal set of properties that make it useful in the context of abstract alphabets. To show this, I will use it to derive single-letter expressions for the minimal achievable rates in two source coding scenarios that can be viewed as generation of coordinated actions in a two-node network. One feature of note is that the achievability proofs are as transparent as in the finite-alphabet case.

10/07 Arya Mazumdar (UMD), Codes for High Density Magnetic Recording on a 1-d Granular Medium

In terabit-density magnetic recording, several bits of data can be replaced by the values of their neighbors in the storage medium. As a result, errors in the medium are dependent on each other and also on the data written.Here we study a simple one-dimensional model of this situation. In our model binary data is sequentially written on the medium and a bit can erroneously change to the immediately preceding value. We define a probabilistic finite-state channel model of the storage medium and derive estimates of its capacity. To derive a lower bound we consider a uniform input distribution, and find an exact expression of the symmetric capacity of the channel. An upper bound is found by showing that the original channel is a stochastic degradation of another, related channel model whose capacity we compute explicitly.
This is a joint work with Alexander Barg and Navin Kashyap.

10/28 Woomyoung Park (UMD), Linear Ordered Codes, Shape Enumerators, and Parallel Channels

We consider linear codes in Hamming-like metric spaces with the metric derived from a partial order of coordinates of codewords.
In the first part, we will discuss a matroid-theoretic perspective of linear ordered codes; introducing the (multivariate) Tutte polynomial and extending the Greene's theorem for an ordered metric. The relation between the higher weight distributions and the Tutte polynomial is presented.
The ordered metric is known to describe the noise process in a wireless fading system studied by Tavildar and Viswanath (2006). We define a probabilistic model of the channel in the system termed by the ordered symmetric channel. As an application of these results, the extension of Wyner's wire-tap channel I and Ozarow-Wyner's wire-tap channel II model are discussed.
This is a joint work with Alexander Barg.

11/04 Ersen Ekrem (UMD), An Alternative Proof for the Capacity Region of the Degraded Gaussian MIMO Broadcast Channel (I)

We provide an alternative proof for the capacity region of the degraded Gaussian multiple-input multiple-output (MIMO) broadcast channel. Our proof does not use the channel enhancement technique as opposed to the original proof of Weingertan et. al and the alternative proof of Liu {\it et. al}. Our proof starts with the single-letter description of the capacity region of the degraded broadcast channel, and directly evaluates it for the degraded Gaussian MIMO broadcast channel by using two main technical tools. The first one is the generalized de Bruijn identity due to Palomar~\emph{et. al.} which provides a connection between the differential entropy and the Fisher information matrix. The second tool we use is an inequality due to Dembo which lower bounds the differential entropy in terms of the Fisher information matrix.
This is joint work with Sennur Ulukus.

11/11 Ersen Ekrem (UMD), An Alternative Proof for the Capacity Region of the Degraded Gaussian MIMO Broadcast Channel (II)

12/02 Anna Pantelidou (University of Oulu, Finland), Single-hop Versus Multi-hop Transmission for Energy-efficient Multicasting

In this talk we will consider the problem of multicasting from a single source to a set of destinations. We will assume that the source can either reach the destinations directly or forward its traffic through a set of assisting relays. Due to the non-linear attenuation of the signal with distance, employing the relays can help to improve the signal quality at the destinations. Meanwhile, relays also consume energy for retransmission of the received information and can decrease the rate of communication due to the multi-hop transmission. Under the performance objective of maximizing the common amount of information (number of bits) that the source sends to all destinations per Joule of the total energy spent, we wish to identify whether direct transmission from the source to the destinations is preferable as opposed to multi-hop forwarding through the relays. In the latter case, we also wish to identify a) which subset of the relays should be activated, b) for how long, and c) the respective destinations that each relay has to serve.
This is a joint work with the Ph.D. student, Q. Xue, at the University of Oulu, Finland.

12/09 Arya Mazumdar (UMD), Combinatorial Non-Adaptive Group Testing

Suppose we have a set U of n elements and among them there are d defectives, d << n. The objective is to identify the defective items. A test is performed on a subset T1 of U, with a positive output if and only if there exists at least one defective item in T1. We would like to know the minimum number of tests required such that the objective is achieved. We will discuss only the non-adaptive setting where all the tests are done simultaneously.
This problem and its variations form an area of research, that is active for at least past sixty years. In this talk I will summarize the best known lower and upper (constructions) bounds on this Group Testing problem. In the process we will review superimposed codes, disjunct matrices and concatenated codes among other topics.