**Information
and Coding Theory Seminar** **
**

**Abstracts
of talks**

*Fall 2006*

**9/20 Prakash Narayan (UMD),
Slepian-Wolf Data Compression and Linear Channel Codes**

ABSTRACT:

It has long been known that Slepian-Wolf data compression, i.e., compression
of a source sequence when the decoder is aided by additional access to correlated
side-information, can be performed at the optimal rate using a linear encoder
[Csiszar, 1982]. For the special case in which the source sequence and the decoder's
side-information are connected by a virtual additive noise channel, Wyner [1978]
had shown earlier how the source sequence could be compressed at the optimal
(Slepian-Wolf) rate using a suitable linear code for this virtual channel. In
a recent paper in the Proceedings of the 2006 IEEE International Symposium on
Information Theory, Da-ke He and En-Hui Yang have examined the duality between
Slepian-Wolf data compression and linear channel codes for the general situation
in which the source sequence and the decoder's side-information are arbitrarily
correlated.

This body of work, culminating in the recent
He-Yang result, will be discussed.

Reference: He-Yang

**9/27 Alexander Barg (UMD), Two topics
in error-correcting codes: Locally testable codes and the Gilbert-Varshamov
bound**

ABSTRACT:

1) Locally testable codes: given a linear binary code C of length n, we would
like to provide an algorithm that will tell whether a given vector y in {0,1}^n
is in C or is (epsilon n) away from C. An algorithm is called a tester if it
gives a correct answer with probability close to 1 by looking at a constant
number of randomly chosen bits of y. The notion of locally testable codes (for
Hadamard codes, or Reed-Muller codes of the first order) first arose in (relation
to) the proof of the celebrated PCP theorem Following N. Alon et al. (IEEE IT,
Nov. '05), we will prove that Reed-Muller codes of any order are locally testable.
Related results and an open problem will be mentioned.

2) The Gilbert-Varshamov bound: Jiang and Vardy ('04) have shown that it is possible to construct binary linear codes that are better than the GV bound by a factor \Omega(n). Gaborit and Zemor have recently shown the same for double circulant codes. We will prove their result and mention an application of these works to sphere packing.

Reference: Gaborit-Zemor

**10/4 Nuno Martins (UMD), Coding
for Additive White Noise Channels with Feedback Corrupted by Uniform Quantization
or Bounded Noise**

ABSTRACT:**
** We present simple coding strategies, which are
variants of the Schalkwijk-Kailath scheme, for communicating reliably over additive
white noise channels in the presence of corrupted feedback. More specifically,
we consider a framework comprising an additive white forward channel and a backward
link which is used for feedback. We consider two types of corruption mechanisms
in the backward link. The first is quantization noise, i.e., the encoder receives
the quantized values of the past outputs of the forward channel. The quantization
is uniform, memoryless and time invariant (that is, symbol-by-symbol scalar
quantization), with bounded quantization error. The second corruption mechanism
is an arbitrarily distributed additive bounded noise in the backward link. Here
we allow symbol-by-symbol encoding at the input to the backward channel. We
propose simple explicit schemes that guarantee positive information rate, in
bits per channel use, with positive error exponent. If the forward channel is
additive white Gaussian then our schemes achieve capacity, in the limit of diminishing
amplitude of the noise components at the backward link, while guaranteeing that
the probability of error converges to zero as a doubly exponential function
of the block length. Furthermore, if the forward channel is additive white Gaussian
and the backward link consists of an additive bounded noise channel, with signal-to-noise
ratio (SNR) constrained symbol-by-symbol encoding, then our schemes are also
capacity-achieving in the limit of high SNR.

Joint work with Tsachy Weissman.

Reference: Martins-Weissman (submitted to IEEE Trans. on IT, abridged version published in Allerton '06)

**10/11
****Vijay Gupta (UMD),
Data Transmission over Networks for Estimation
and Control**

ABSTRACT:**
** We will
consider the problem of estimation of a linear dynamic process across an arbitrary
network of communication links that drop packets stochastically. We will identify
the optimal information processing strategy at each node that allows the estimator
to calculate the best possible estimate in the minimum mean squared error sense.
For the case when the drop probabilities are memoryless and independent across
links, we will analyze the stability and performance for our algorithm.

Reference: Gupta et al., Dana et al.

**10/25 N. Prasanth
Anthapadmanabhan (UMD), Capacity of binary fingerprinting
with two pirates**

ABSTRACT:

Digital fingerprinting is a technique to prevent the piracy of copyrighted content.
It is accomplished by assigning to each licensed user a unique mark, called
a "fingerprint", which is hidden within the content. A coalition of
users, termed "pirates", may compare their copies to identify some
fingerprint positions and create a pirated copy with a modified fingerprint.
The objective is to assign fingerprints in a way that enables the distributor
to identify at least one of the members of the coalition to have created the
pirated copy as long as the coalition size does not exceed a certain threshold
t, which is a parameter of the problem. A single-letter expression (involving
mutual information terms) is obtained as an upper bound on the capacity (maximal
rate) of fingerprinting codes secure against coalitions of size two by modeling
fingerprinting as a communication problem and using an information-theoretic
approach. For the special case of fingerprinting with two pirates over the binary
alphabet, we obtain a random coding lower bound which matches with the previous
upper bound and establishes the exact value of capacity for this case as 0.25.

(Joint work with A. Barg, I. Dumer and P. Narayan)

**11/1 Sirin Nitinawarat (UMD),
A Graph-based Framework for Transmission of Correlated Sources over
Multiple Access Channels**

ABSTRACT:**
** The problem of finding a necessary and
sufficient condition for reliable transmission of correlated sources over a
multiple access channel has remained open since its formulation in the early
'70. It had been realized shortly after that a naive way to communicate in this
setting: firstly perform lossless source encoding; and secondly encode each
codebooks separately by the MAC channel code, can be strictly suboptimal. In
this article, the authors are working towards giving a new sufficient condition
to this problem. The authors persist on using the above separation, namely first
coding for the source and then coding for the MAC channel. A novel idea is to
introduce a new discrete object between this separation which they call semi
regular bipartite graph. Motivation will be discussed as to why this object
arises as a natural candidate to this problem. The results are then presented.
Lastly, we comment on the prospect of realizing the final goal: establishing
a new sufficient condition for the problem.

Reference:

"A
graph-based framework for transmission of correlated sources over multiple access
channels", S. S. Pradhan, S. Choi and K. Ramchandran, Submitted to
IEEE Transactions on Information Theory, January, 2006.

**11/8 Armand Makowski (UMD), Geometric
random graphs on the unit interval (Part I)**

ABSTRACT:

We consider the simplest of geometric random
graphs, namely the one generated by independent nodes which are uniformly distributed
on the unit interval. We study its connectivity properties, namely the corresponding
zero-one laws and underlying phase transitions. The presentation will be self-contained!

**11/14 Rudolf
Ahlswede (Universität Bielefeld), Identification
Entropy (joint
with HyNet Colloquium)**

ABSTRACT: click here

Suggested advance reading: identropy1, identropy2, identification

**12/4 Armand Makowski (UMD), Geometric
random graphs on the unit interval (Part II)**

ABSTRACT:

We consider the simplest of geometric random
graphs, namely the one generated by independent nodes which are uniformly distributed
on the unit interval. We study its connectivity properties, namely the corresponding
zero-one laws and underlying phase transitions. The presentation will be self-contained!

**12/6 Nan Liu (UMD), Dense
Gaussian Sensor Networks: Minimum Achievable Distortion and the Order Optimality
of Separation**

ABSTRACT: **
**We investigate the optimal performance
of dense sensor networks by studying the joint source-channel coding problem.
The overall goal of the sensor network is to take measurements from an underlying
random process, code and transmit those measurement samples to a collector node
in a cooperative multiple access channel with potential feedback, and reconstruct
the entire random process at the collector node. We provide lower and upper
bounds for the minimum achievable expected distortion when the underlying random
process is Gaussian. When the Gaussian random process satisfies some general
conditions, we evaluate the lower and upper bounds explicitly, and show that
they are of the same order for a wide range of power constraints. Thus, for
these random processes, under these power constraints, we express the minimum
achievable expected distortion as a function of the power constraint. Further,
we show that the achievability scheme that achieves the lower bound on the distortion
is a separation-based scheme that is composed of multi-terminal rate-distortion
coding and amplify-and-forward channel coding. Therefore, we conclude that separation
is order-optimal for the dense Gaussian sensor network scenario under consideration,
when the underlying random process satisfies some general conditions.

Joint work with S. Ulukus, submitted to IEEE Trans. on IT. (Liu-Ulukus)

**12/13 Brooke Shrader (UMD), Fountain
Codes and Fountain Capacity**

ABSTRACT: **
**We will discuss the use of fountain
codes for distribution of data over the erasure channel. We will examine two
different types of fountain codes (LT codes and Raptor codes) with an emphasis
on the encoding/decoding complexity. We will then discuss a new formulation
of capacity for fountain coding.

Reference: Shokrollahi, Shamai et al